Sergey Bereg, Yuya Higashikawa, Naoki Katoh, László Kozma, Manuel Lafond, Günter Rote, Yuki Tokuni, Max Willert, and Binhai Zhu:

The two-squirrel problem and its relatives

Abstract

In this paper, we start with a variation of the star cover problem called the Two-Squirrel problem. Given a set P of 2n points in the plane, and two sites c₁ and c₂, compute two n-stars S₁ and S₂ centered at c₁ and c₂ respectively such that the maximum weight of S₁ and S₂ is minimized. This problem is strongly NP-hard by a reduction from Equal-size Set-Partition with Rationals. Then we consider two variationsof the Two-Squirrel problem, namely the Two-MST and Two-TSP problem, which are both NP-hard. The NP-hardness for the latter is obvious while the former needs a non-trivial reduction from Equal-size Set-Partition with Rationals. In terms of approximation algorithms, for Two-MST and Two-TSP we give approximations with factor 2.4268 and 2+ε respectively. Finally, we show some interesting polynomial-time solvable cases for Two-MST.