Configuration linear program
The configuration linear program (configuration-LP) is a particular linear programming used for solving combinatorial optimization problems such as cutting stock,[1] bin packing[2][3] and job scheduling.[4][5]
Background
Consider for example the problem of unrelated-machines scheduling.
 | This article or section is in a state of significant expansion or restructuring. You are welcome to assist in its construction by editing it as well. This template was placed by Erel Segal (talk · contribs). If this article or section has not been edited in several days, please remove this template. If you are the editor who added this template and you are actively editing, please be sure to replace this template with {{in use}} during the active editing session. Click on the link for template parameters to use.
This article was last edited by Erel Segal (talk | contribs) 3 years ago. (Update timer) |
Properties
The integrality gap of the configuration-LP for unrelated-machines scheduling is 2.[4]
References
- ^ Gilmore P. C., R. E. Gomory (1961). A linear programming approach to the cutting-stock problem. Operations Research 9: 849-859
- ^ Karmarkar, Narendra; Karp, Richard M. (1982-11). "An efficient approximation scheme for the one-dimensional bin-packing problem". 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982): 312–320. doi:10.1109/SFCS.1982.61.
{{cite journal}}: Check date values in:|date=(help) - ^ Bansal, Nikhil; Caprara, Alberto; Sviridenko, Maxim (2006-10-01). "Improved approximation algorithms for multidimensional bin packing problems". 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06): 697–708. doi:10.1109/FOCS.2006.38.
- ^ a b Verschae, José; Wiese, Andreas (2014-08-01). "On the configuration-LP for scheduling on unrelated machines". Journal of Scheduling. 17 (4): 371–383. doi:10.1007/s10951-013-0359-4. ISSN 1099-1425.
- ^ Knop, Dušan; Koutecký, Martin (2020-03-04). "Scheduling Kernels via Configuration LP". arXiv:2003.02187 [cs].
- ^ Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). "Approximation algorithms for scheduling unrelated parallel machines". Mathematical Programming. 46 (1): 259–271. doi:10.1007/BF01585745. ISSN 1436-4646.