caa a22 4500 445805013 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110201xx s 000 0 eng 10.1007/s00453-009-9310-7 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9310-7 Finding Total Unimodularity in Optimization Problems Solved by Linear Programs [Elektronische Daten] [Christoph Dürr, Mathilde Hurand] 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 the same cost from the fractional solution. Examples are two scheduling problems (Baptiste and Schieber, J. Sched. 6(4):395-404, 2003; Brucker and Kravchenko, J. Sched. 11(4):229-237, 2008) and the single disk prefetching/caching problem (Albers etal., J. ACM 47:969-986, 2000). 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. Springer Science+Business Media, LLC, 2009 Scheduling nationallicence Caching nationallicence Linear programming nationallicence Totally unimodular matrices nationallicence Dürr Christoph CNRS and LIX, Ecole Polytechnique, Palaiseau, France aut Hurand Mathilde Google, 8002, Zürich, Switzerland aut Algorithmica Springer-Verlag 59/2(2011-02-01), 256-268 0178-4617 59:2<256 2011 59 453 https://doi.org/10.1007/s00453-009-9310-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9310-7 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dürr Christoph CNRS and LIX, Ecole Polytechnique, Palaiseau, France aut NATIONALLICENCE 700 1- Hurand Mathilde Google, 8002, Zürich, Switzerland aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/2(2011-02-01), 256-268 0178-4617 59:2<256 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer