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


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


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(n2) time algorithm.


  There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis Sale was obtained in Europe, Australia, New Zealand.