Zobrazeno 1 - 10
of 1 132
pro vyhledávání: '"Williamson, David P."'
One of the most famous conjectures in combinatorial optimization is the four-thirds 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, due
Externí odkaz:
http://arxiv.org/abs/2311.01950
This paper revisits the 2-approximation algorithm for $k$-MST presented by Garg in light of a recent paper of Paul et al.. In the $k$-MST problem, the goal is to return a tree spanning $k$ vertices of minimum total edge cost. Paul et al. extend Garg'
Externí odkaz:
http://arxiv.org/abs/2306.01867
A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP is at most 4/3. Despite significant efforts, the conjecture remains open. We consider the hal
Externí odkaz:
http://arxiv.org/abs/2211.04639
The Simplex algorithm for solving linear programs-one of Computing in Science & Engineering's top 10 most influential algorithms of the 20th century-is an important topic in many algorithms courses. While the Simplex algorithm relies on intuitive geo
Externí odkaz:
http://arxiv.org/abs/2210.15655
The symmetric circulant TSP is a special case of the traveling salesman problem in which edge costs are symmetric and obey circulant symmetry. Despite the substantial symmetry of the input, remarkably little is known about the symmetric circulant TSP
Externí odkaz:
http://arxiv.org/abs/2207.10254
This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger, Motwani, and Sudan \cite{KMS98} give a vector program for which a coloring of the graph can be encoded as a semidefinite matrix of low rank.
Externí odkaz:
http://arxiv.org/abs/2202.10515