Invited Session Wed.2.H 3010

Wednesday, 13:15 - 14:45 h, Room: H 3010

Cluster 1: Approximation & online algorithms [...]

Approximation in routing and scheduling


Chair: Nicole Megow and Jose Correa



Wednesday, 13:15 - 13:40 h, Room: H 3010, Talk 1

Jose Antonio Soto
The traveling salesman problem in cubic graphs

Coauthors: Jose Correa, Omar Larre


We prove that every 2-connected cubic graph on n vertices has a tour of length at most (4/3-ε)n, for a small, but positive ε. This in particular implies that the integrality gap of the Held and Karp LP relaxation for the TSP is strictly less than 4/3 on this graph class.



Wednesday, 13:45 - 14:10 h, Room: H 3010, Talk 2

Jose Verschae
The power of recourse for online MST and TSP

Coauthors: Nicole Megow, Martin Skutella, Andreas Wiese


We consider online versions of MST and TSP problems with recourse. Assume that vertices of a complete metric graph appear one by one, and must be connected by a tree (respectively tour) of low cost. In the standard online setting, where decisions are irrevocable, the competitive factor of each algorithm is Ω(log n). In our model, recourse is allowed by granting a limited number of edge rearrangements per iteration. More than 20 years ago, Imase and Waxman (1991) conjectured that constant-competitive solutions can be achieved with a constant (amortized) number of rearrangements. In this talk I will present an algorithm that solves this conjecture for MSTs in the amortized setting.
Unlike in offline TSP variants, the standard double-tree and shortcutting approach does not give constant guarantees in the online setting. However, a non-trivial robust shortcutting technique allows to convert trees into tours at the loss of small factors, implying the conjecture of Imase and Waxman for tours.
For the non-amortized setting, we conjecture a structural property of optimal solutions that would imply a constant competitive ratio with one recourse action per iteration.



Wednesday, 14:15 - 14:40 h, Room: H 3010, Talk 3

Claudio Telha
The jump number (maximum independent set) of two-directional orthogonal-ray graphs

Coauthor: Jose A. Soto


We consider a special case of the independent set of rectangles problem. Given a family of white (W) and black (B) points in the plane, we construct the family R of rectangles having bottom-left corner in W and top-right corner in B. The problem is to find the maximum cardinality of a collection of disjoint rectangles in R.
We show that this problem can be efficiently solved using linear programming techniques. Inspired by this result, and by previous work of A. Frank, T. Jordan and L. Vegh on set-pairs, we describe a faster combinatorial algorithm that solves this problem in Õ((|W|+|B|)2.5) time.
We also establish a connection between this special case of the independent set of rectangles problem and the problem of finding the jump number of a certain class of comparability graphs (known as two-directional orthogonal ray graphs). Using this connection, we can compute the jump number of convex graphs with n nodes in O((nlog n)2.5) time, while previous algorithms for these instances ran in time at least O(n9).


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.