2026-08-07T08:16:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8270 2024-03-06T10:41:46Z ddc:004 open_access

Network Optimization on Partitioned Pairs of Points Arkin, Esther M. Banik, Aritra Carmi, Paz Citovsky, Gui Jia, Su Katz, Matthew J. Mayer, Tyler Mitchell, Joseph S. B. Network Optimization TSP tour Matching Spanning Tree Pairs Partition Algorithms Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik 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 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.6 urn:nbn:de:0030-drops-82700 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.6 eng https://creativecommons.org/licenses/by/3.0/legalcode