Semidefinite and linear programming integrality gaps for scheduling identical machines

• 成果类型: Article
• 署名作者: Kurpisz, Adam; Mastrolilli, Monaldo; Mathieu, Claire; Moemke, Tobias; Verdugo, Victor; Wiese, Andreas
• 署名单位: Universita della Svizzera Italiana; Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Saarland University; Universidad de Chile; Max Planck Society
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1152-5
• 发表日期: 2018
• 页码: 231-248
• 关键词: lovasz-schrijver; vertex cover; Approximation algorithms; lp relaxations; optimization; hierarchy; graph; cut; set

摘要

Sherali and Adams (SIAM J Discrete Math 3: 411-430, 1990) and Lovasz and Schrijver (SIAM J Optim 1: 166-190, 1991) developed systematic procedures to construct the hierarchies of relaxations known as lift-and-project methods. They have been proven to be a strong tool for developing approximation algorithms, matching the best relaxations known for problems like Max-Cut and Sparsest-Cut. In this work we provide lower bounds for these hierarchies when applied over the configuration LP for the problem of scheduling identical machines to minimize the makespan. First we show that the configuration LP has an integrality gap of at least 1024/1023 by providing a family of instances with 15 different job sizes. Then we show that for any integer n there is an instance with n jobs in this family such that after O(n) rounds of the Sherali-Adams (SA) or the Lovasz-Schrijver (LS+) hierarchy the integrality gap remains at least 1024/1023.