Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Varun Ganesan, Vladislav Kontsevoi, Qipeng Liu, Quanquan Liu, Fermi Ma, Ofir Nachum, Aaron Sidford, Erik Waingarten, and Daniel Ziegler, “Arboral satisfaction: Recognition and LP approximation”, Information Processing Letters, volume 127, November 2017, pages 1–5.

BibTeX

@Article{ArboralSatisfaction_IPL,
  AUTHOR        = {Erik D. Demaine and Varun Ganesan and Vladislav Kontsevoi and Qipeng Liu and Quanquan Liu and Fermi Ma and Ofir Nachum and Aaron Sidford and Erik Waingarten and Daniel Ziegler},
  TITLE         = {Arboral satisfaction: Recognition and {LP} approximation},
  JOURNAL       = {Information Processing Letters},
  journalurl    = {https://www.journals.elsevier.com/information-processing-letters},
  VOLUME        = 127,
  MONTH         = {November},
  YEAR          = 2017,
  PAGES         = {1--5},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1016/J.IPL.2017.04.012},
  dblp          = {https://dblp.org/rec/journals/ipl/DemaineGKLLMNSW17},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1016/j.ipl.2017.04.012">ScienceDirect</A>.},
}

Abstract:

A point set P is arborally satisfied if, for any pair of points with no shared coordinates, the box they span contains another point in P. At SODA 2009, Demaine, Harmon, Iacono, Kane, and Pǎtraşcu proved a connection between the longstanding dynamic optimality conjecture about binary search trees and the problem of finding the minimum-size arborally satisfied superset of a given 2D point set [1].

We study two basic problems about arboral satisfaction. First, we develop two nontrivial algorithms to test whether a given point set is arborally satisfied. In 2D, both of our algorithms run in O(n log n) time, and one of them achieves O(n) runtime if the points are presorted; we also show a matching Ω(n log n) lower bound in the algebraic decision tree model. In d dimensions, our algorithm runs in O(d n log n + n log^d - 1 n) time. Second, we study a natural integer linear programming formulation of finding the minimum-size arborally satisfied superset of a given 2D point set, which is equivalent to finding offline dynamically optimal binary search trees. Unfortunately, we conclude that the linear programming relaxation has large integrality gap, making it unlikely to find an approximation algorithm via this approach.

Comments:

This paper is also available from ScienceDirect.

Availability:

The paper is available in PDF (259k).

See information on file formats.

[Google Scholar search]