  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 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.
