Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is αCUT ≃ 0.87856, obtained by the celebrated SDPbased approximation algorithm of Goemans and Williamson. The currently best approximation algorithm for MAX DICUT, i.e., the MAX CUT problem in directed graphs, achieves a ratio of about 0.87401, leaving open the question whether MAX DICUT can be approximated as well as MAX CUT. We obtain a slightly improved algorithm for MAX DICUT and a new UGChardness result for it, showing that 0.87446 ≤ αDICUT ≤ 0.87461, where αDICUT is the best approximation ratio that can be obtained in polynomial time for MAX DICUT under UGC. The new upper bound separates MAX DICUT from MAX CUT, resolving a question raised by Feige and Goemans.
A natural generalization of MAX DICUT is the MAX 2AND problem in which each constraint is of the form z1∧z2, where z1 and z2 are literals, i.e., variables or their negations (In MAX DICUT each constraint is of the form \neg{x1}∧x2, where x1 and x2 are variables.) Austrin separated MAX 2AND from MAX CUT by showing that α2AND < 0.87435 and conjectured that MAX 2AND and MAX DICUT have the same approximation ratio. Our new lower bound on MAX DICUT refutes this conjecture, completing the separation of the three problems MAX 2AND, MAX DICUT and MAX CUT. We also obtain a new lower bound for MAX 2AND, showing that 0.87414 ≤ α2AND ≤ 0.87435.
Our upper bound on MAX DICUT is achieved via a simple, analytical proof. The lower bounds on MAX DICUT and MAX 2AND (the new approximation algorithms) use experimentallydiscovered distributions of rounding functions which are then verified via computerassisted proofs.
more »
« less
This content will become publicly available on August 27, 2025
A Lower Bound for the Max Entropy Algorithm for TSP
One of the most famous conjectures in combinatorial optimization is the fourthirds conjecture, which states that the integrality gap of the subtour LP relaxation of the TSP is equal to $\frac43$. For 40 years, the best known upper bound was $1.5$. Recently, Karlin, Klein, and Oveis Gharan \cite{KKO21b} showed that the max entropy algorithm for the TSP gives an improved bound of $1.5  10^{36}$.
In this paper, we show that the approximation ratio of the max entropy algorithm is at least 1.375, even for graphic TSP.
Thus the max entropy algorithm does not appear to be the algorithm that will ultimately resolve the fourthirds conjecture in the affirmative, should that be possible.
more »
« less
 Award ID(s):
 2007009
 NSFPAR ID:
 10536482
 Publisher / Repository:
 Springer
 Date Published:
 ISBN:
 9783031598357
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


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 wellstudied 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/6approximation for graphic TSP and a 1.625approximation 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

Del Pia, Alberto ; Kaibel, Volker (Ed.)A longstanding conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP (sometimes called the Subtour LP or the HeldKarp bound) is at most 4/3 for symmetric instances of the TSP obeying the triangle inequality. In this paper we consider the halfintegral case, in which a feasible solution to the LP has solution values in {0,1/2,1} . Karlin, Klein, and Oveis Gharan [9], in a breakthrough result, were able to show that in the halfintegral case, the integrality gap is at most 1.49993; Gupta et al. [6] showed a slight improvement of this result to 1.4983. Both of these papers consider a hierarchy of critical tight sets in the support graph of the LP solution, in which some of the sets correspond to cycle cuts and the others to degree cuts. Here we show that if all the sets in the hierarchy correspond to cycle cuts, then we can find a distribution of tours whose expected cost is at most 4/3 times the value of the halfintegral LP solution; sampling from the distribution gives us a randomized 4/3approximation algorithm. We note that known bad cases for the integrality gap have a gap of 4/3 and have a halfintegral LP solution in which all the critical tight sets in the hierarchy are cycle cuts; thus our result is tight.more » « less

A systematic study of simultaneous optimization of constraint satisfaction problems was initiated by Bhangale et al. [ICALP, 2015]. The simplest such problem is the simultaneous MaxCut. Bhangale et al. [SODA, 2018] gave a .878minimum approximation algorithm for simultaneous MaxCut which is almost optimal assuming the Unique Games Conjecture (UGC). For single instance MaxCut, GoemansWilliamson [JACM, 1995] gave an α_GWapproximation algorithm where α_GW ≈ .87856720... which is optimal assuming the UGC. It was left open whether one can achieve an α_GWminimum approximation algorithm for simultaneous MaxCut. We answer the question by showing that there exists an absolute constant ε₀ ≥ 10^{5} such that it is NPhard to get an (α_GW ε₀)minimum approximation for simultaneous MaxCut assuming the Unique Games Conjecture.more » « less

Megow, Nicole ; Smith, Adam (Ed.)We study the question of when an approximate search optimization problem is harder than the associated decision problem. Specifically, we study a natural and quite general model of blackbox searchtodecision reductions, which we call branchandbound reductions (in analogy with branchandbound algorithms). In this model, an algorithm attempts to minimize (or maximize) a function f: D → ℝ_{≥ 0} by making oracle queries to h_f : T → ℝ_{≥ 0} satisfying min_{x ∈ S} f(x) ≤ h_f(S) ≤ γ ⋅ min_{x ∈ S} f(x) (*) for some γ ≥ 1 and any subset S in some allowed class of subsets T; of the domain D. (When the goal is to maximize f, h_f instead yields an approximation to the maximal value of f over S.) We show tight upper and lower bounds on the number of queries q needed to find even a \gamma'approximate minimizer (or maximizer) for quite large \gamma'; in a number of interesting settings, as follows.  For arbitrary functions f : {0,1}ⁿ → ℝ_{≥ 0}, where T; contains all subsets of the domain, we show that no branchandbound reduction can achieve γ' ≲ γ^{n/log q}, while a simple greedy approach achieves essentially γ^{n/log q}.  For a large class of MAXCSPs, where T = {S_w} contains each set of assignments to the variables induced by a partial assignment w, we show that no branchandbound reduction can do significantly better than essentially a random guess, even when the oracle h_f guarantees an approximation factor of γ ≈ 1+√{log(q)/n}.  For the Traveling Salesperson Problem (TSP), where T = {S_p} contains each set of tours extending a path p, we show that no branchandbound reduction can achieve γ' ≲ (γ1) n/log q. We also prove a nearly matching upper bound in our model. These results show an oracle model in which approximate search and decision are strongly separated. (In particular, our result for TSP can be viewed as a negative answer to a question posed by Bellare and Goldwasser (SIAM J. Comput. 1994), though only in an oracle model.) We also note two alternative interpretations of our results. First, if we view h_f as a data structure, then our results unconditionally rule out blackbox searchtodecision reductions for certain data structure problems. Second, if we view h_f as an efficiently computable heuristic, then our results show that any reasonably efficient branchandbound algorithm requires more guarantees from its heuristic than simply Eq. (*). Behind our results is a ``useless oracle lemma'' which allows us to argue that under certain conditions the oracle h_f is ``useless'' and which might be of independent interest.more » « less