Algorithmic and game-theoretic perspectives on scheduling

(cont.) Second, for almost all 0-1 bipartite instances, we give a lower bound on the integrality gap of various linear programming relaxations of this problem. Finally, we show that for almost all 0-1 bipartite instances, all feasible schedules are arbitrarily close to optimal. Finally, we consider the problem of minimizing the sum of weighted completion times in a concurrent open shop environment. We present some interesting properties of various linear programming relaxations for this problem, and give a combinatorial primal-dual 2-approximation algorithm.

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2008

Author dc:creator

• Uhan, Nelson A. (Nelson Alexander)

Advisor dc:contributor.advisor

• Andreas S. Schulz.

• Operations Research Center.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/45607

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/45607