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 proceedingConference contribution

2 Scopus citations


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 languageEnglish (US)
Title of host publicationApproximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers
EditorsMonaldo Mastrolilli, Klaus Jansen
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783319517407
StatePublished - 2017
Externally publishedYes
Event14th International Workshop on Approximation and Online Algorithms, WAOA 2016 - Aarhus, Denmark
Duration: Aug 25 2016Aug 26 2016

Publication series

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


Conference14th International Workshop on Approximation and Online Algorithms, WAOA 2016

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Shortest separating cycle
  • Traveling salesman problem


Dive into the research topics of 'The shortest separating cycle problem'. Together they form a unique fingerprint.

Cite this