## 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**

**Abstract:**

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

**Abstract:**

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

**Abstract:**

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((n**log* n)^{2.5}) time, while previous algorithms for these instances ran in time at least *O(n*^{9}).