Approximation algorithms for packing and scheduling problems
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2004.
| 主要作者: | |
|---|---|
| 其他作者: | |
| 格式: | Thesis |
| 语言: | eng |
| 出版: |
Massachusetts Institute of Technology
2005
|
| 主题: | |
| 在线阅读: | http://hdl.handle.net/1721.1/17720 |
| _version_ | 1826188643848421376 |
|---|---|
| author | Correa, José Rafael, 1975- |
| author2 | Michael X. Goemans and Andreas S. Schulz. |
| author_facet | Michael X. Goemans and Andreas S. Schulz. Correa, José Rafael, 1975- |
| author_sort | Correa, José Rafael, 1975- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2004. |
| first_indexed | 2024-09-23T08:02:49Z |
| format | Thesis |
| id | mit-1721.1/17720 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:02:49Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/177202019-04-09T16:17:34Z Approximation algorithms for packing and scheduling problems Correa, José Rafael, 1975- Michael X. Goemans and Andreas S. Schulz. Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center. Operations Research Center. Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2004. Includes bibliographical references (p. 149-161). In this thesis we consider three combinatorial optimization problems. Specifically, we study packing and scheduling questions of relevance in several areas of operations research, including interconnection networks and switch scheduling, VLSI design, and processor scheduling. The first chapter studies a natural edge-coloring question arising from the problem of scheduling packets through an interconnection network. The theoretical model we consider can be seen as a weighted extension of Konig's theorem that states that the minimum number of colors needed to color all edges of a bipartite graph equals the maximum vertex degree. For the weighted generalization, a longstanding open question is to determine the minimum number of colors as a function of n, the maximum total weight adjacent to any vertex. Our main contribution is to show that 2.557n + o(n) colors are sufficient, improving upon earlier work. In the second chapter, we consider the following variant of the classical bin-packing problem: Place a given list of rectangles into the minimum number of unit square bins. In the restricted case where all rectangles are squares, we design an algorithm with an asymptotic performance guarantee arbitrarily close to optimal. In the general case, we give an algorithm that outputs a near-optimal solution, provided it is allowed to use slightly larger bins. Moreover, we extend these algorithmic ideas to handle a number of multidimensional packing problems, obtaining best-known results for several of these. (cont.) Finally, in the third chapter, we discuss a standard sequencing problem, namely, scheduling precedence-constrained jobs on a single machine to minimize the sum of weighted completion times. We look at the problem from a polyhedral perspective, obtaining, as one of our main results, a generalization of a classical result by Sidney. This new insight allows us to reason that all known 2-approximation algorithms behave similarly. Furthermore, we present a new integer programming model that suggests a strong connection between the scheduling problem and the vertex cover problem. by José Rafael Correa. Ph.D. 2005-06-02T18:23:11Z 2005-06-02T18:23:11Z 2004 2004 Thesis http://hdl.handle.net/1721.1/17720 56430193 eng 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. http://dspace.mit.edu/handle/1721.1/7582 161 p. 6124424 bytes 10998617 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Correa, José Rafael, 1975- Approximation algorithms for packing and scheduling problems |
| title | Approximation algorithms for packing and scheduling problems |
| title_full | Approximation algorithms for packing and scheduling problems |
| title_fullStr | Approximation algorithms for packing and scheduling problems |
| title_full_unstemmed | Approximation algorithms for packing and scheduling problems |
| title_short | Approximation algorithms for packing and scheduling problems |
| title_sort | approximation algorithms for packing and scheduling problems |
| topic | Operations Research Center. |
| url | http://hdl.handle.net/1721.1/17720 |
| work_keys_str_mv | AT correajoserafael1975 approximationalgorithmsforpackingandschedulingproblems |