Thursday, 13:45 - 14:10 h, Room: H 3010


Christoph Dürr
Packing and covering problems on the line as shortest path problems


A popular approach to understand a new problem is to model it as an integer linear program, and to analyze properties of the relaxed linear program. Sometimes one might discover the the variable-constraint matrix is totally unimodular (TUM), which implies that the problem has a polynomial time solution, most likely with a flow structure. In some cases however the linear program is not TUM, but nevertheless has the property, that whenever it has a solution, all optimal extrem point solutions are integral. Again this leads to a polynomial time solution, just by solving the relaxed linear program. D. and Mathilde Hurand in 2006 found that some of these linear programs could be simplified as shortest path formulations. In 2011 Alejandro L\'{o}pez-Ortiz and Claude-Guy Quimper showed how the special structure of these shortest path instances could be used to solve the problem within improved running time. In this talk the outline of these analysis and simplification techniques are presented, illustrated on packing and covering problems on the line.


Talk 2 of the invited session Thu.2.H 3010
"Scheduling, packing and covering" [...]
Cluster 1
"Approximation & online algorithms" [...]


  Most online loan lenders allow getting New Jersey Loans Online without visiting a bank, straight to your bank account. This pill gives a hand to thousands who suffer from erectile dysfunction. People who take Viagra Super Active can forget about their impotence and have a normal intimate life.