10 citations · 21 across the 16 of their papers we have counts for
4 papers · 1 filter
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…