License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.6
URN: urn:nbn:de:0030-drops-82700
URL: https://drops.dagstuhl.de/opus/volltexte/2017/8270/
Go to the corresponding LIPIcs Volume Portal

Arkin, Esther M. ; Banik, Aritra ; Carmi, Paz ; Citovsky, Gui ; Jia, Su ; Katz, Matthew J. ; Mayer, Tyler ; Mitchell, Joseph S. B.

Network Optimization on Partitioned Pairs of Points

pdf-format:
LIPIcs-ISAAC-2017-6.pdf (0.6 MB)

Abstract

Given n pairs of points, S = {{p_1, q_1}, {p_2, q_2}, ..., {p_n, q_n}}, in some metric space, we study the problem of two-coloring the points within each pair, red and blue, to optimize the cost of a pair of node-disjoint networks, one over the red points and one over the blue points. In this paper we consider our network structures to be spanning trees, traveling salesman tours or matchings. We consider several different weight functions computed over the network structures induced, as well as several different objective functions. We show that some of these problems are NP-hard, and provide constant factor approximation algorithms in all cases.

BibTeX - Entry

@InProceedings{arkin_et_al:LIPIcs:2017:8270,
  author =	{Esther M. Arkin and Aritra Banik and Paz Carmi and Gui Citovsky and Su Jia and Matthew J. Katz and Tyler Mayer and Joseph S. B. Mitchell},
  title =	{{Network Optimization on Partitioned Pairs of Points}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8270},
  URN =		{urn:nbn:de:0030-drops-82700},
  doi =		{10.4230/LIPIcs.ISAAC.2017.6},
  annote =	{Keywords: Network Optimization, TSP tour, Matching, Spanning Tree, Pairs, Partition, Algorithms, Complexity}
}

Keywords: Network Optimization, TSP tour, Matching, Spanning Tree, Pairs, Partition, Algorithms, Complexity
Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 07.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI