Name
Abstract | ||
|---|---|---|
Given a set of pairs of points in the plane, the goal of the shortest separating cycle problem is to find a simple tour of minimum length that separates the two points of each pair to different sides. In this article we prove hardness of the problem and provide approximation algorithms under various settings. Assuming the Unique Games Conjecture, the problem cannot be approximated within a factor of 2. We provide a polynomial algorithm when all pairs are unit length apart with horizontal orientation inside a square board of size 2 - epsilon. We provide constant approximation algorithms for unit length horizontal or vertical pairs or constant length pairs on points laying on a grid. For pairs with no restriction we have an O(root n)-approximation algorithm and an O(log n)-approximation algorithm for the shortest separating planar graph. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-51741-4_1 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Shortest separating cycle,Traveling salesman problem | Approximation algorithm,Binary logarithm,Combinatorics,Horizontal and vertical,Unique games conjecture,Computer science,Travelling salesman problem,Polynomial algorithm,Grid,Planar graph | Conference |
Volume | ISSN | Citations |
10138 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Esther M. Arkin | 1 | 1207 | 158.07 |
| Jie Gao | 2 | 2174 | 155.61 |
| Adam Hesterberg | 3 | 4 | 7.07 |
| Joseph S.B. Mitchell | 4 | 4329 | 428.84 |
| Jiemin Zeng | 5 | 3 | 1.41 |