10 citations · 21 across the 16 of their papers we have counts for
26 papers
Fractional Dichromatic Number and Domination in Tournaments
Paul Colinot, Alantha Newman
Bourneuf, Charbit and Thomassé [BCT25] showed that the domination number of a tournament can be bounded as a function of its fractional dichromatic number. The function proved was…
Hardness and Approximation for Coloring Digraphs
Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer +2
The dichromatic number of a digraph is the minimum number such that can be partitioned into subsets, each inducing an acyclic digraph. The acyclic number…
Static to Dynamic Correlation Clustering
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee +7
Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [Mach. Learn. '04]. The input is an unweighted, undirected graph. The problem is to clu…
Solving the Correlation Cluster LP in Sublinear Time
Nairen Cao, Vincent Cohen-Addad, Shi Li +7
Correlation Clustering is a fundamental and widely-studied problem in unsupervised learning and data mining. The input is a graph and the goal is to construct a clustering minimizi…
Improved linearly ordered colorings of hypergraphs via SDP rounding
Anand Louis, Alantha Newman, Arka Ray
We consider the problem of linearly ordered (LO) coloring of hypergraphs. A hypergraph has an LO coloring if there is a vertex coloring, using a set of ordered colors, so that (i)…
Understanding the Cluster LP for Correlation Clustering
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee +3
In the classic Correlation Clustering problem introduced by Bansal, Blum, and Chawla (FOCS 2002), the input is a complete graph where edges are labeled either or , and the g…
A PTAS for -Low Rank Approximation: Solving Dense CSPs over Reals
Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal +4
We consider the Low Rank Approximation problem, where the input consists of a matrix and an integer , and the goal is to find a matrix of…
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering
Vincent Cohen-Addad, Euiwoong Lee, Shi Li +1
We consider the classic Correlation Clustering problem: Given a complete graph where edges are labelled either or , the goal is to find a partition of the vertices that mini…
Bounding the chromatic number of dense digraphs by arc neighborhoods
Felix Klingelhoefer, Alantha Newman
The chromatic number of a directed graph is the minimum number of induced acyclic subdigraphs that cover its vertex set, and accordingly, the chromatic number of a tournament is th…
Coloring tournaments with few colors: Algorithms and complexity
Felix Klingelhoefer, Alantha Newman
A -coloring of a tournament is a partition of its vertices into acyclic sets. Deciding if a tournament is 2-colorable is NP-hard. A natural problem, akin to that of coloring…
Correlation Clustering with Sherali-Adams
Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman
Given a complete graph where each edge is labeled or , the Correlation Clustering problem asks to partition into clusters to minimize the number of edges…
Voting algorithms for unique games on complete graphs
Antoine Méot, Arnaud de Mesmay, Moritz Mühlenthaler +1
An approximation algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying a -fraction of the constraints on any -s…
Towards Improving Christofides Algorithm on Fundamental Classes by Gluing Convex Combinations of Tours
Arash Haddadan, Alantha Newman
We present a new approach for gluing tours over certain tight, 3-edge cuts. Gluing over 3-edge cuts has been used in algorithms for finding Hamilton cycles in special graph classes…
Complex Semidefinite Programming and Max-k-Cut
Alantha Newman
In a second seminal paper on the application of semidefinite programming to graph partitioning problems, Goemans and Williamson showed how to formulate and round a complex semidefi…
Rounding semidefinite programs for large-domain problems via Brownian motion
Kevin L. Chang, Alantha Newman
We present a new simple method for rounding a semidefinite programming relaxation of a constraint satisfaction problem. We apply it to the problem of approximate angular synchroniz…
Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
Arash Haddadan, Alantha Newman
Finding the exact integrality gap for the LP relaxation of the 2-edge-connected spanning multigraph problem (2EC) is closely related to the same problem for the Held-Karp relax…
Explicit 3-colorings for exponential graphs
Adrien Argento, Pierre Charbit, Alantha Newman
For a graph and integer , two functions from into are adjacent if for all edges of , . The graph of all such f…
Domination and fractional domination in digraphs
Ararat Harutyunyan, Tien-Nam Le, Alantha Newman +1
In this paper, we investigate the relation between the (fractional) domination number of a digraph and the independence number of its underlying graph, denoted by . More…
Shorter tours and longer detours: Uniform covers and a bit beyond
Arash Haddadan, Alantha Newman, R. Ravi
Motivated by the well known four-thirds conjecture for the traveling salesman problem (TSP), we study the problem of {\em uniform covers}. A graph has an -uniform cove…
Coloring dense digraphs
Ararat Harutyunyan, Tien-Nam Le, Alantha Newman +1
The chromatic number of a digraph is the minimum number of acyclic subgraphs covering the vertex set of . A tournament is a hero if every -free tournament has chr…
The Alternating Stock Size Problem and the Gasoline Puzzle
Alantha Newman, Heiko Röglin, Johanna Seif
Given a set S of integers whose sum is zero, consider the problem of finding a permutation of these integers such that: (i) all prefix sums of the ordering are nonnegative, and (ii…
Graph-TSP from Steiner Cycles
Satoru Iwata, Alantha Newman, R. Ravi
We present an approach for the traveling salesman problem with graph metric based on Steiner cycles. A Steiner cycle is a cycle that is required to contain some specified subset of…
An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs
Alantha Newman
Mömke and Svensson presented a beautiful new approach for the traveling salesman problem on a graph metric (graph-TSP), which yields a -approximation guarantee on subcubic gra…
On the Configuration LP for Maximum Budgeted Allocation
Christos Kalaitzis, Aleksander Mcadry, Alantha Newman +2
We study the Maximum Budgeted Allocation problem, i.e., the problem of selling a set of indivisible goods to players, each with a separate budget, such that we maximize the…