The shortest separating cycle problem

Esther M. Arkin; Jie Gao; Adam Hesterberg; Joseph S.B. Mitchell; Jiemin Zeng

doi:10.1007/978-3-319-51741-4_1

The shortest separating cycle problem

Esther M. Arkin, Jie Gao, Adam Hesterberg, Joseph S.B. Mitchell, Jiemin Zeng

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

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 − ε. 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(√n)-approximation algorithm and an O(log n)- approximation algorithm for the shortest separating planar graph.

Original language	English (US)
Title of host publication	Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers
Editors	Monaldo Mastrolilli, Klaus Jansen
Publisher	Springer Verlag
Pages	1-13
Number of pages	13
ISBN (Print)	9783319517407
DOIs	https://doi.org/10.1007/978-3-319-51741-4_1
State	Published - 2017
Externally published	Yes
Event	14th International Workshop on Approximation and Online Algorithms, WAOA 2016 - Aarhus, Denmark Duration: Aug 25 2016 → Aug 26 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10138 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Workshop on Approximation and Online Algorithms, WAOA 2016
Country/Territory	Denmark
City	Aarhus
Period	8/25/16 → 8/26/16

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Keywords

Shortest separating cycle
Traveling salesman problem

Access to Document

10.1007/978-3-319-51741-4_1

Cite this

Arkin, E. M., Gao, J., Hesterberg, A., Mitchell, J. S. B., & Zeng, J. (2017). The shortest separating cycle problem. In M. Mastrolilli, & K. Jansen (Eds.), Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers (pp. 1-13). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10138 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-51741-4_1

Arkin, Esther M. ; Gao, Jie ; Hesterberg, Adam et al. / The shortest separating cycle problem. Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers. editor / Monaldo Mastrolilli ; Klaus Jansen. Springer Verlag, 2017. pp. 1-13 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ca38b21e246d474db93e63f90285a827,

title = "The shortest separating cycle problem",

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 − ε. 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(√n)-approximation algorithm and an O(log n)- approximation algorithm for the shortest separating planar graph.",

keywords = "Shortest separating cycle, Traveling salesman problem",

author = "Arkin, {Esther M.} and Jie Gao and Adam Hesterberg and Mitchell, {Joseph S.B.} and Jiemin Zeng",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 14th International Workshop on Approximation and Online Algorithms, WAOA 2016 ; Conference date: 25-08-2016 Through 26-08-2016",

year = "2017",

doi = "10.1007/978-3-319-51741-4_1",

language = "English (US)",

isbn = "9783319517407",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "1--13",

editor = "Monaldo Mastrolilli and Klaus Jansen",

booktitle = "Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers",

address = "Germany",

}

Arkin, EM, Gao, J, Hesterberg, A, Mitchell, JSB & Zeng, J 2017, The shortest separating cycle problem. in M Mastrolilli & K Jansen (eds), Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10138 LNCS, Springer Verlag, pp. 1-13, 14th International Workshop on Approximation and Online Algorithms, WAOA 2016, Aarhus, Denmark, 8/25/16. https://doi.org/10.1007/978-3-319-51741-4_1

The shortest separating cycle problem. / Arkin, Esther M.; Gao, Jie; Hesterberg, Adam et al.
Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers. ed. / Monaldo Mastrolilli; Klaus Jansen. Springer Verlag, 2017. p. 1-13 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10138 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - The shortest separating cycle problem

AU - Arkin, Esther M.

AU - Gao, Jie

AU - Hesterberg, Adam

AU - Mitchell, Joseph S.B.

AU - Zeng, Jiemin

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - 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 − ε. 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(√n)-approximation algorithm and an O(log n)- approximation algorithm for the shortest separating planar graph.

AB - 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 − ε. 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(√n)-approximation algorithm and an O(log n)- approximation algorithm for the shortest separating planar graph.

KW - Shortest separating cycle

KW - Traveling salesman problem

UR - http://www.scopus.com/inward/record.url?scp=85010690607&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85010690607&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-51741-4_1

DO - 10.1007/978-3-319-51741-4_1

M3 - Conference contribution

AN - SCOPUS:85010690607

SN - 9783319517407

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 13

BT - Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers

A2 - Mastrolilli, Monaldo

A2 - Jansen, Klaus

PB - Springer Verlag

T2 - 14th International Workshop on Approximation and Online Algorithms, WAOA 2016

Y2 - 25 August 2016 through 26 August 2016

ER -

Arkin EM, Gao J, Hesterberg A, Mitchell JSB, Zeng J. The shortest separating cycle problem. In Mastrolilli M, Jansen K, editors, Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers. Springer Verlag. 2017. p. 1-13. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-51741-4_1

The shortest separating cycle problem

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this