Performance Guarantees of Local Search for Multiprocessor Scheduling

References

• Ahuja R. K., Orlin J. B., Sharma D. New neighborhood search structures for the capacitated minimum spanning tree problem. Math. Programming (2001) 91:71–97Crossref, Google Scholar
• Arkin E. M., Hassin R. On local search for weighted k-set packing. Math. Oper. Res. (1998) 23:640–648Link, Google Scholar
• Arya V., Garg N., Khandekar R., Meyerson A., Munagala K., Pandit V. Local search heuristic for k-median and facility location problems. SIAM J. Comput. (2004) 33:544–562Crossref, Google Scholar
• Ausiello G., Protasi M. Local search, reducibility and approximability of NP optimization problems. Inform. Processing Lett. (1995) 54:73–79Crossref, Google Scholar
• Boykov Y., Veksler O., Zabih R. A new algorithm for energy minimization with discontinuities. Internat. Workshop Energy Minimization Methods Comput. Vision and Pattern Recognition (1999) (Springer, Berlin, Germany) 205–220Crossref, Google Scholar
• Brucker P., Hurink J., Werner F. Improving local search heuristics for some scheduling problems I. Discrete Appl. Math. (1996) 65:97–122Crossref, Google Scholar
• Brucker P., Hurink J., Werner F. Improving local search heuristics for some scheduling problems II. Discrete Appl. Math. (1997) 72:47–69Crossref, Google Scholar
• Brüggemann T., Monnot J., Woeginger G. J. Local search for the minimum label spanning tree problem with bounded color classes. Oper. Res. Lett. (2003) 31:195–201Crossref, Google Scholar
• Charikar M., Guha S. Improved combinatorial algorithms for the facility location and k-median problems. Proc. 40th Annual IEEE Sympos. Foundations Comput. Sci. (1999) 378–388Crossref, Google Scholar
• Cho Y., Sahni S. Bounds for list schedules on uniform processors. SIAM J. Comput. (1980) 9:91–103Crossref, Google Scholar
• Chudak F. A., Williamson D. P. Improved approximation algorithms for capacitated facility location problems. Math. Programming (2005) 102:207–222Crossref, Google Scholar
• De Bontridder K. M. J., Halldórsson B. V., Halldórsson M. M., Hurkens C. A. J., Lenstra J. K., Ravi R., Stougie L. Approximation algorithms for the test cover problem. Math. Programming (2003) 98:477–491Crossref, Google Scholar
• Feige U., Karpinski M., Langberg M. Improved approximation of Max-Cut on graphs of bounded degree. J. Algorithms (2002) 43:201–219Crossref, Google Scholar
• Finn G., Horowitz E. A linear time approximation algorithm for multiprocessor scheduling. BIT (1979) 19:312–320Crossref, Google Scholar
• Frangioni A., Necciari E., Scutellà M. G. A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems. J. Combin. Optim. (2004) 8:195–220Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (Freeman, San Francisco, CA) Google Scholar
• Goemans M. X., Williamson D. P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM (1995) 42:1115–1145Crossref, Google Scholar
• Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. (1979) 5:287–326Crossref, Google Scholar
• Gupta A., Tardos É. A constant factor approximation algorithm for a class of classification problems. Proc. 32nd ACM Sympos. Theory Comput. (2000) 652–658Crossref, Google Scholar
• Hochbaum D. S., Shmoys D. B. Using dual approximation algorithms for scheduling problems: Theoretical and practical results. J. ACM (1987) 34:144–162Crossref, Google Scholar
• Hochbaum D. S., Shmoys D. B. A polynomial approximation scheme for machine scheduling on uniform processors: Using the dual approximation approach. SIAM J. Comput. (1988) 17:539–551Crossref, Google Scholar
• Hurkens C. A. J., Schrijver A. On the size of systems of sets every t of which have an sdr, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. (1989) 2:68–72Crossref, Google Scholar
• Hurkens C. A. J., Vredeveld T. Local search for multiprocessor scheduling: How many moves does it take to a local optimum? Oper. Res. Lett. (2003) 31:137–141Crossref, Google Scholar
• Kernighan B. W., Lin S. An efficient heuristic procedure for partitioning graphs. Bell System Tech. J. (1970) 49:291–307Crossref, Google Scholar
• Korupolu M. R., Plaxton C. G., Rajaraman R. Analysis of a local search heuristic for facility location problems. J. Algorithms (2000) 37:146–188Crossref, Google Scholar
• Lenstra J. K., Shmoys D. B., Tardos É. Approximation algorithms for scheduling unrelated parallel machines. Math. Programming (1990) 46:259–271Crossref, Google Scholar
• Lin S., Kernighan B. W. An effective heuristic for the traveling salesman problem. Oper. Res. (1973) 21:498–516Link, Google Scholar
• Lu H., Ravi R. The power of local optimization: Approximation for maximum-leaf spanning tree. Proc. 13th Annual Allerton Conf. Communications, Control, and Computing (1992) 533–542Google Scholar
• Pál M., Tardos Éva, Wexler T. Facility location with nonuniform hard capacities. Proc. 42nd Annual IEEE Sympos. the Foundations Comput. Sci. (2001) 329–338Crossref, Google Scholar
• Schuurman P., Vredeveld T. Performance guarantees of local search for multiprocessor scheduling. Proc. 8th Integer Programming and Combinatorial Optimization Conf., Lecture Notes Computer Science (2001) 2081(Springer, Berlin, Germany) 370–382Crossref, Google Scholar
• Vredeveld T., Lenstra J. K. On local search for the generalized graph coloring problem. Oper. Res. Lett. (2003) 31:28–34Crossref, Google Scholar