Finding total unimodularity in optimization problems solved by linear programs
by Mathilde Hurand (LIX) 

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 \cite{Baptiste.Schieber:A-Note-on-Scheduling,BruckerKravchenko:Time-Windows}  
and the single disk prefetching/caching problem \cite{Albers.Garg.Leonardi:Minimizing-stall}.

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, which provides 
simpler (and sometimes combinatorial) algorithms with better worst case running times.

joint work with Christoph Dürr