Finding total unimodularity in optimization problems solved by linear programs

Abstract : A popular approach in combinatorial optimization is to model problems as integer linear programs. Ideally, the relaxed linear program would have only integer solutions, which happens for instance when the constraint matrix is totally unimodular. Still, sometimes it is possible to build an integer solution with same cost from the fractional solution. Examples are two scheduling problems and the single disk prefetching/caching problem. We show that problems such as the three previously mentioned can be separated into two subproblems: (1) finding an optimal feasible set of slots, and (2) assigning the jobs or pages to the slots. It is straigthforward to show that the latter can be solved greedily. We are able to solve the former with a totally unimodular linear program, from which we obtain simple combinatorial algorithms with improved worst case running time.
Type de document :
Communication dans un congrès
Azar Y., Erlebach T. Proc. of the 14th Annual European Symposium on Algorithms (ESA)},, Sep 2006, Zürich, Springer-Verlag, 4168 (4168), pp.315-326, 2006, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00123679
Contributeur : Christoph Dürr <>
Soumis le : mercredi 10 janvier 2007 - 16:10:35
Dernière modification le : jeudi 11 janvier 2018 - 06:19:44

Identifiants

  • HAL Id : inria-00123679, version 1

Collections

Citation

Christoph Dürr, Mathilde Hurand. Finding total unimodularity in optimization problems solved by linear programs. Azar Y., Erlebach T. Proc. of the 14th Annual European Symposium on Algorithms (ESA)},, Sep 2006, Zürich, Springer-Verlag, 4168 (4168), pp.315-326, 2006, Lecture Notes in Computer Science. 〈inria-00123679〉

Partager

Métriques

Consultations de la notice

65