Lift-and-round to improve weighted completion time on unrelated machines. (English) Zbl 1373.68151
Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 156-167 (2016).
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W25 | Approximation algorithms |
| 90B35 | Deterministic scheduling theory in operations research |
| 90C22 | Semidefinite programming |
References:
| [1] | Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, and Maxim Sviridenko. Approximation schemes for minimizing average weighted completion time with release dates. In Foundations of Computer Science, FOCS, pages 32-44, 1999. |
| [2] | Alexander A. Ageev and Maxim Sviridenko. Approximation algorithms for maximum coverage and max cut with given sizes of parts. In Integer Programming and Combinatorial Optimization IPCO, pages 17-30, 1999. · Zbl 0948.90122 |
| [3] | Sanjeev Arora, Alan M. Frieze, and Haim Kaplan. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Math. Program., 92(1):1-36, 2002. · Zbl 1154.90602 |
| [4] | Arash Asadpour, Uriel Feige, and Amin Saberi. Santa Claus meets hypergraph matchings. ACM Transactions on Algorithms, 8(3):24, 2012. 10.1145/2229163.2229168 · Zbl 1295.05165 |
| [5] | 4 This bound is loose and can also be obtained using independent randomized rounding instead of our negative-correlation rounding. The importance of the new rounding appears in the other case. |
| [6] | Arash Asadpour and Amin Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. In Symposium on Theory of Computing, STOC, pages 114-121, 2007. 10.1145/1250790.1250808 · Zbl 1232.68178 |
| [7] | Yossi Azar and Amir Epstein. Convex programming for scheduling unrelated parallel machines. In Symposium on Theory of Computing, pages 331-337, 2005. 10.1145/1060590.1060639 · Zbl 1192.90059 |
| [8] | Nikhil Bansal and Maxim Sviridenko. The santa claus problem. In Symposium on Theory of Computing, STOC, pages 31-40, 2006. 10.1145/1132516.1132522 · Zbl 1301.90057 |
| [9] | Deeparnab Chakrabarty, Julia Chuzhoy, and Sanjeev Khanna. On allocating goods to maximize fairness. In Foundations of Computer Science, FOCS, pages 107-116, 2009. · Zbl 1292.91102 |
| [10] | Chandra Chekuri and Sanjeev Khanna. A PTAS for minimizing weighted completion time on uniformly related machines. In ICALP, pages 848-861, 2001. · Zbl 0986.68503 |
| [11] | Chandra Chekuri and Sanjeev Khanna. Approximation algorithms for minimizing averageweighted completion time. In Handbook of Scheduling - Algorithms, Models, and Performance Analysis. 2004. |
| [12] | Chandra Chekuri, Rajeev Motwani, B. Natarajan, and Clifford Stein. Approximation techniques for average completion time scheduling. SIAM J. Comput., 31(1):146-166, 2001. 10.1137/S0097539797327180 · Zbl 0992.68066 |
| [13] | Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Multi-budgeted matchings and matroid intersection via dependent rounding. In Symposium on Discrete Algorithms, SODA, pages 1080-1097, 2011. · Zbl 1377.90071 |
| [14] | F. A. Chudak. A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines. Journal of Scheduling, 2(2):73-77, 1999. · Zbl 0963.90028 |
| [15] | Uriel Feige. On allocations that maximize fairness. In Symposium on Discrete Algorithms, SODA, pages 287-293, 2008. · Zbl 1192.91083 |
| [16] | Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. J. ACM, 53(3):324-360, 2006. 10.1145/1147954.1147956 · Zbl 1312.68233 |
| [17] | Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz, Martin Skutella, and Yaoguang Wang. Single machine scheduling with release dates. SIAM J. Discrete Math., 15(2):165-192, 2002. 10.1137/S089548019936223X · Zbl 1009.90096 |
| [18] | Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, and Joel Wein. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Mathematics of Operations Research, 22(3):513-544, 1997. · Zbl 0883.90064 |
| [19] | Leslie A. Hall, David B. Shmoys, and Joel Wein. Scheduling to minimize average completion time: Off-line and on-line algorithms. In Symposium on Discrete Algorithms, SODA, pages 142-151, 1996. · Zbl 0845.90071 |
| [20] | Han Hoogeveen, Petra Schuurman, and Gerhard J. Woeginger. Non-approximability results for scheduling problems with minsum criteria. In Integer Programming and Combinatorial Optimization, IPCO, pages 353-366, 1998. · Zbl 0911.90208 |
| [21] | Jeff Kahn and P. Mark Kayll. On the stochastic independence properties of hard-core distributions. Combinatorica, 17(3):369-391, 1997. · Zbl 0902.05055 |
| [22] | V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. Minimum weighted completion time. In Encyclopedia of Algorithms. 2008. |
| [23] | V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. A unified approach to scheduling on unrelated parallel machines. J. ACM, 56(5), 2009. 10.1145/1552285.1552289 · Zbl 1325.90044 |
| [24] | Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Math. Program., 46:259-271, 1990. 10.1007/BF01585745 · Zbl 0715.90063 |
| [25] | Konstantin Makarychev and Maxim Sviridenko. Solving optimization problems with diseconomies of scale via decoupling. In Foundations of Computer Science, FOCS, pages 571-580, 2014. 10.1109/FOCS.2014.67 |
| [26] | Cynthia A. Phillips, Clifford Stein, and Joel Wein. Task scheduling in networks. SIAM J. Discrete Math., 10(4):573-598, 1997. 10.1137/S0895480194279057 · Zbl 0885.68020 |
| [27] | Cynthia A. Phillips, Clifford Stein, and Joel Wein. Minimizing average completion time in the presence of release dates. Math. Program., 82:199-223, 1998. · Zbl 0920.90074 |
| [28] | Andreas S. Schulz and Martin Skutella. Scheduling unrelated machines by randomized rounding. SIAM J. Discrete Math., 15(4):450-469, 2002. 10.1137/S0895480199357078 · Zbl 1055.90040 |
| [29] | Petra Schuurman and Gerhard Woeginger. Polynomial time approximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling, 2(5):203-213, 1999. · Zbl 0938.90032 |
| [30] | Jay Sethuraman and Mark S. Squillante. Optimal scheduling of multiclass parallel machines. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 963-964, 1999. · Zbl 1009.90052 |
| [31] | Martin Skutella. Personal communication. Oct 2015. |
| [32] | Martin Skutella. Convex quadratic and semidefinite programming relaxations in scheduling. J. ACM, 48(2):206-242, 2001. 10.1145/375827.375840 · Zbl 1323.90024 |
| [33] | Martin Skutella and Gerhard J. Woeginger. A PTAS for minimizing the weighted sum of job completion times on parallel machines. In Symposium on Theory of Computing, STOC, pages 400-407, 1999. 10.1145/301250.301356 · Zbl 1345.90045 |
| [34] | W. E. Smith. Various optimizers for single-stage production. Naval Research Logistics, 3:59 ˝ U66, 1956. |
| [35] | Ola Svensson. Santa Claus schedules jobs on unrelated machines. SIAM J. Comput., 41(5):1318-1341, 2012. · Zbl 1257.68083 |
| [36] | Maxim Sviridenko and Andreas Wiese. Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines. In IPCO, pages 387-398, 2013. 10.1007/978-3-642-36694-9_33 · Zbl 1377.90034 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
