## Contributed Session Wed.2.H 3005

#### Wednesday, 13:15 - 14:45 h, Room: H 3005

**Cluster 2: Combinatorial optimization** [...]

### Geometric combinatorial optimization

**Chair: Maurice Queyranne**

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

**Maurice Queyranne**

Modeling convex subsets of points

**Abstract:**

A subset *S* of a given set *P* of points in a vector space is convex (relative to *P*) if every given point of *P* that is in the convex hull *S* is also in *S*.

We are interested in modelling such discrete convexity restrictions which arise, usually in a low-dimensional space and subject to additional constraints, in many applications (e.g., mining, forestry, location, data mining, political districting, police quadrant design).

This question is well understood in one dimension, where optimization can be solved in time that is linear (in the number *|P|* of given points); a complete (but exponential-size) polyhedral description in the natural variables (that select the points in *S*), and a linear-time separation algorithm are known, as well as a linear-sized ideal extended formulation.

On the other hand the optimization problem (to find a maximum weight convex subset of given points with weights of arbitrary signs) is NP-hard in dimensions three and higher, and inapproximable when the dimension is part of the input.

In the two-dimensional plane, the optimization problem is solved in polynomial (cubic) time by dynamic programming [Bautista-Santiago et al., 2011] and, thanks to Carathéodory's

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

**Eranda Dragoti-Cela**

On the x-and-y axes travelling salesman problem

**Coauthors: Vladimir Deineko, Gerhard Woeginger**

**Abstract:**

We consider a special case of the Euclidean Travelling Salesman Problem (TSP) known as x-and-y-axes TSP. In this case all cities s are situated on the *x*-axis and on the *y*-axis of an orthogonal coordinate system for the Euclidean plane. This is a special case of the so-called Constrained TSP (CTSP) investigated by Rubinstein, Thomas and Wormald (2001), where the *n* cities lie on a given finite set *G* of smooth, compact curves in the plane, such that each curve has a finite length and the number of (self) intersections is finite. Moreover at each intersection the branches of the curve approach in different directions. Rubinstein et al. have shown that the CTSP is polynomially solvable, where the degree of the polynomial is large and depends on *G* and *n*. We show that for each circle around the origin the optimal tour of the x-and-y axes TSP contains at most eight edges leaving that circle. By considering one circle for each vertex we construct a dynamic programming scheme (DPS) which assembles the optimal tour by means of optimal sub-paths lying outside the circle and on one of the half-axes. A non-trivial analysis shows that this DPS leads to an *O(n*^{2}) time algorithm.