Arkin et al.~cite{ArkinBCCJKMM17} recently introduced textit{partitioned pairs} network optimization problems: given a metric-weighted graph on $n$ pairs of nodes, the task is to color one node from each pair red and the other blue, and then to compute two separate textit{network structures} or disjoint (node-covering) subgraphs of a specified sort, one on the graph induced by the red nodes and the other on the blue nodes. Three structures have been investigated by cite{ArkinBCCJKMM17}---textit{spanning trees}, textit{traveling salesperson tours}, and textit{perfect matchings}---and the three objectives to optimize for when computing such pairs of structures: textit{min-sum}, textit{min-max}, and textit{bottleneck}. We provide improved approximation guarantees and/or strengthened hardness results for these nine NP-hard problem settings.
Download