research
∙
06/02/2023
Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs
This paper revisits the 2-approximation algorithm for k-MST presented by...
share
research
∙
11/09/2022
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP
A long-standing conjecture for the traveling salesman problem (TSP) stat...
research
∙
10/19/2022
GILP: An Interactive Tool for Visualizing the Simplex Algorithm
The Simplex algorithm for solving linear programs-one of Computing in Sc...
research
∙
07/21/2022
The Two-Stripe Symmetric Circulant TSP is in P
The symmetric circulant TSP is a special case of the traveling salesman ...
research
∙
02/21/2022
Graph Coloring and Semidefinite Rank
This paper considers the interplay between semidefinite programming, mat...
research
∙
09/02/2021
Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows
We study the problem of finding flows in undirected graphs so as to mini...
research
∙
12/22/2020
The Circlet Inequalities: A New, Circulant-Based Facet-Defining Inequality for the TSP
Facet-defining inequalities of the symmetric Traveling Salesman Problem ...
research
∙
10/30/2020
A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems
Over the last two decades, a significant line of work in theoretical alg...
research
∙
10/29/2020
Recursive Random Contraction Revisited
In this note, we revisit the recursive random contraction algorithm of K...
research
∙
07/25/2020
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching
In this paper, we consider the online vertex-weighted bipartite matching...
research
∙
06/06/2020
Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time
Combinatorial optimization algorithms for graph problems are usually des...
research
∙
01/08/2020
Easy Capacitated Facility Location Problems, with Connections to Lot-Sizing
In this note, we consider the capacitated facility location problem when...
research
∙
07/26/2019
Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP
De Klerk, Pasechnik, and Sotirov give a semidefinite programming constra...
research
∙
07/21/2019
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
The traveling salesman problem (TSP) is a fundamental problem in combina...
research
∙
04/26/2019
Tight Bounds for Online Weighted Tree Augmentation
The Weighted Tree Augmentation problem (WTAP) is a fundamental problem i...
research
∙
02/18/2019
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
We consider the integrality gap of the subtour LP relaxation of the Trav...
research
∙
10/23/2017