An official website of the United States government
Features of graphs that hinder finding closed paths with particular properties, as represented by the Traveling Salesperson Problem—TSP, are identified for three classes of graphs. Removing these terms leads to a companion graph with identical closed path properties that is easier to analyze. A surprise is that these troubling graph factors are precisely what is needed to analyze certain voting methods, while the companion graph’s terms are what cause voting theory complexities as manifested by Arrow’s Theorem. This means that the seemingly separate goals of analyzing closed paths in graphs and analyzing voting methods are complementary: components of data terms that assist in one of these areas are the source of troubles in the other. Consequences for standard decision methods are in Sects. 2.5, 3.7 and the companion paper (Saari in Theory Decis 91(3):377–402, 2021). The emphasis here is on paths in graphs; incomplete graphs are similarly handled.
more »
« less
Connecting Arrow's Theorem, Voting Theory, and the Traveling Salesperson Problem
Problems with majority voting over pairs as represented by Arrow’s Theorem and those of finding the lengths of closed paths as captured by the Traveling Salesperson Problem (TSP) appear to have nothing in common. In fact, they are connected. As shown, pairwise voting and a version of the TSP share the same domain where each system can be simplified by restricting it to complementary regions to eliminate extraneous terms. Central for doing so is the Borda Count, where it is shown that its outcome most accurately reflects the voter preferences.
more »
« less
- Award ID(s):
- 1923164
- PAR ID:
- 10328205
- Date Published:
- Journal Name:
- arXiv:2204.13230 [math.CO]
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The multiple traveling salesman problem (mTSP) is an important variant of metric TSP where a set of k salespeople together visit a set of n cities while minimizing the total cost of the k routes under a given cost metric. The mTSP problem has applications to many real-life problems such as vehicle routing. Rothkopf [14] introduced another variant of TSP called many-visits TSP (MV-TSP) where a request r(v) is given for each city v and a single salesperson needs to visit each city r(v) times and return to his starting point. We note that in MV-TSP the cost of loops is positive, so a TSP solution cannot be trivially extended (without an increase in cost) to a MV-TSP solution by consecutively visiting each vertex to satisfy the visit requirements. A combination of mTSP and MV-TSP, called many-visits multiple TSP (MV-mTSP) was studied by Berczi, Mnich, and Vincze [3] where the authors give approximation algorithms for various variants of MV-mTSP. In this work, we show a simple linear programming (LP) based reduction that converts a mTSP LP-based algorithm to an LP-based algorithm for MV-mTSP with the same approximation factor. We apply this reduction to improve or match the current best approximation factors of several variants of the MV-mTSP. Our reduction shows that the addition of visit requests r(v) to mTSP does not make the problem harder to approximate even when r(v) is exponential in the number of vertices. To apply our reduction, we either use existing LP-based algorithms for mTSP variants or show that several existing combinatorial algorithms for mTSP variants can be interpreted as LP-based algorithms. This allows us to apply our reduction to these combinatorial algorithms while achieving improved guarantees.more » « less
-
We consider the problem of designing sublinear time algorithms for estimating the cost of minimum] metric traveling salesman (TSP) tour. Specifically, given access to a n × n distance matrix D that specifies pairwise distances between n points, the goal is to estimate the TSP cost by performing only sublinear (in the size of D) queries. For the closely related problem of estimating the weight of a metric minimum spanning tree (MST), it is known that for any epsilon > 0, there exists an O^~(n/epsilon^O(1))-time algorithm that returns a (1+epsilon)-approximate estimate of the MST cost. This result immediately implies an O^~(n/epsilon^O(1)) time algorithm to estimate the TSP cost to within a (2 + epsilon) factor for any epsilon > 0. However, no o(n^2)-time algorithms are known to approximate metric TSP to a factor that is strictly better than 2. On the other hand, there were also no known barriers that rule out existence of (1 + epsilon)-approximate estimation algorithms for metric TSP with O^~ (n) time for any fixed epsilon > 0. In this paper, we make progress on both algorithms and lower bounds for estimating metric TSP cost. On the algorithmic side, we first consider the graphic TSP problem where the metric D corresponds to shortest path distances in a connected unweighted undirected graph. We show that there exists an O^~(n) time algorithm that estimates the cost of graphic TSP to within a factor of (2 − epsilon_0) for some epsilon_0 > 0. This is the first sublinear cost estimation algorithm for graphic TSP that achieves an approximation factor less than 2. We also consider another well-studied special case of metric TSP, namely, (1, 2)-TSP where all distances are either 1 or 2, and give an O^~(n ^ 1.5) time algorithm to estimate optimal cost to within a factor of 1.625. Our estimation algorithms for graphic TSP as well as for (1, 2)-TSP naturally lend themselves to O^~(n) space streaming algorithms that give an 11/6-approximation for graphic TSP and a 1.625-approximation for (1, 2)-TSP. These results motivate the natural question if analogously to metric MST, for any epsilon > 0, (1 + epsilon)-approximate estimates can be obtained for graphic TSP and (1, 2)-TSP using O^~ (n) queries. We answer this question in the negative – there exists an epsilon_0 > 0, such that any algorithm that estimates the cost of graphic TSP ((1, 2)-TSP) to within a (1 + epsilon_0)-factor, necessarily requires (n^2) queries. This lower bound result highlights a sharp separation between the metric MST and metric TSP problems. Similarly to many classical approximation algorithms for TSP, our sublinear time estimation algorithms utilize subroutines for estimating the size of a maximum matching in the underlying graph. We show that this is not merely an artifact of our approach, and that for any epsilon > 0, any algorithm that estimates the cost of graphic TSP or (1, 2)-TSP to within a (1 + epsilon)-factor, can also be used to estimate the size of a maximum matching in a bipartite graph to within an epsilon n additive error. This connection allows us to translate known lower bounds for matching size estimation in various models to similar lower bounds for metric TSP cost estimation.more » « less
-
Abstract Studies of star formation in various galaxy cluster mergers have reached apparently contradictory conclusions regarding whether mergers stimulate star formation, quench it, or have no effect. Because the mergers studied span a range of time since pericenter (TSP), it is possible that the apparent effect on star formation is a function of the TSP. We use a sample of 12 bimodal mergers to assess the star formation as a function of TSP. We measure the equivalent width of the Hαemission line in ∼100 member galaxies in each merger, classify galaxies as emitters or nonemitters, and then classify emitters as star-forming galaxies (SFGs) or active galactic nucleus (AGN) based on the [Nii]λ6583 line. We quantify the distribution of SFG and AGN relative to nonemitters along the spatial axis defined by the subcluster separation. The SFG and AGN fractions vary from merger to merger but show no trend with TSP. The spatial distribution of SFG is consistent with that of nonemitters in eight mergers, but show significant avoidance of the system center in the remaining four mergers, including the three with the lowest TSP. If there is a connection between star formation activity and TSP, probing it further will require more precise TSP estimates and more mergers with TSP in the range of 0–400 Myr.more » « less
-
The classical Beardwood-Halton-Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form $$\beta \sqrt n$$ for the minimum length of a Traveling Salesperson Tour throuh $$n$$ random points in the unit square, and in the decades since it was proved, the existence of such formulas has been shown for other such \emph{Euclidean functionals} on random points in the unit square as well. Despite more than 50 years of attention, however, it remained unknown whether the minimum length TSP through $$n$$ random points in $[0,1]^2$ was asymptotically distinct from its natural lower bounds, such as the minimum length spanning tree, the minimum length 2-factor, or, as raised by Goemans and Bertsimas, from its linear programming relaxation. We prove that the TSP on random points in Euclidean space is indeed asymptotically distinct from these and other natural lower bounds, and show that this separation implies that branch-and-bound algorithms based on these natural lower bounds must take nearly exponential ($$e^{\tilde \Omega(n)}$$) time to solve the TSP to optimality, even in average case. This is the first average-case superpolynomial lower bound for these branch-and-bound algorithms (a lower bound as strong as $$e^{\tilde \Omega (n)}$$ was not even been known in worst-case analysis).more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
