research
∙
07/10/2023
Bounding the chromatic number of dense digraphs by arc neighborhoods
The chromatic number of a directed graph is the minimum number of induce...
share
research
∙
05/04/2023
Coloring tournaments with few colors: Algorithms and complexity
A k-coloring of a tournament is a partition of its vertices into k acycl...
research
∙
07/22/2022
Correlation Clustering with Sherali-Adams
Given a complete graph G = (V, E) where each edge is labeled + or -, the...
research
∙
10/22/2021
Voting algorithms for unique games on complete graphs
An approximation algorithm for a Constraint Satisfaction Problem is call...
research
∙
07/03/2019
Towards improving Christofides algorithm for half-integer TSP
We study the traveling salesman problem (TSP) in the case when the objec...
research
∙
12/27/2018
Complex Semidefinite Programming and Max-k-Cut
In a second seminal paper on the application of semidefinite programming...
research
∙
12/09/2018
Rounding semidefinite programs for large-domain problems via Brownian motion
We present a new simple method for rounding a semidefinite programming r...
research
∙
11/24/2018
Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
Finding the exact integrality gap α for the LP relaxation of the 2-edge-...
research
∙
11/24/2018
Polynomial-time algorithms for 2-edge-connected subgraphs on fundamental classes by top-down coloring
Finding the exact integrality gap α for the LP relaxation of the 2-edge-...
research
∙
08/27/2018