Search Results

Documents authored by Newman, Alantha

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.48
Static to Dynamic Correlation Clustering

Authors: Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
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 cluster the vertices so as to minimize the number of edges between vertices in different clusters and missing edges between vertices inside the same cluster. This problem has a wide application in data mining and machine learning. We introduce a general framework that transforms existing static correlation clustering algorithms into fully-dynamic ones that work against an adaptive adversary. We show how to apply our framework to known efficient correlation clustering algorithms, starting from the classic 3-approximate Pivot algorithm from Ailon, Charikar and Newman [JACM'08]. Applied to the most recent sublinear 1.485-approximation algorithm from Cao, Cohen-Addad, Lee, Li, Lolck, Newman, Thorup, Vogl, Yan and Zhang [STOC'25] , we get an 1.485-approximation fully-dynamic algorithm that works with worst-case constant update time. The original static algorithm gets its approximation factor with constant probability, and we get the same against an adaptive adversary in the sense that for any given update step, not known to our algorithm, our solution is an 1.485-approximation with constant probability when we reach this update. Most of previous dynamic algorithms, including the celebrated result from Behnezhad, Charikar, Ma and Tan [FOCS'19], had approximation factors around 3 in expectation, and they could only handle an oblivious adversary. A recent algorithm by Braverman, Dharangutte, Pai, Shah, and Wang [AISTATS'25] handles an adaptive adversary, but it has a large unspecified constant approximation ratio. This contrasts with our general transformation, which works with all the best approximation factors known for the static case.
Cite as

Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang. Static to Dynamic Correlation Clustering. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 48:1-48:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ICALP.2026.48,
  author =	{Cao, Nairen and Cohen-Addad, Vincent and Lee, Euiwoong and Li, Shi and Lolck, David Rasmussen and Newman, Alantha and Thorup, Mikkel and Vogl, Lukas and Yan, Shuyi and Zhang, Hanwen},
  title =	{{Static to Dynamic Correlation Clustering}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{48:1--48:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.48},
  URN =		{urn:nbn:de:0030-drops-264378},
  doi =		{10.4230/LIPIcs.ICALP.2026.48},
  annote =	{Keywords: Dynamic Algorithms, Correlation Clustering, Approximation Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.53
Hardness and Approximation for Coloring Digraphs

Authors: Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer, Alantha Newman, and Chaoliang Tang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
The dichromatic number χ(D) of a digraph is the minimum number k such that V(D) can be partitioned into k subsets, each inducing an acyclic digraph. The acyclic number α(D) is the cardinality of a largest induced acyclic subdigraph of D. We study these problems from an approximation point of view. We begin with establishing that even when restricted to tournaments, approximating χ and α remain as challenging as their undirected counterparts on general graphs. Specifically, we establish that for every ε > 0, it is hard to approximate both α and χ up to a factor of n^{1-ε} even when restricted to tournaments. We next consider approximate coloring of digraphs in special cases. We begin with establishing that we can color 𝓁-dicolorable digraphs using at most 𝓁 ⋅ n^{1-1/(𝓁)} colors in time O(n^{2𝓁}); in particular, we can color 2-dicolorable digraphs with 2√n colors in polynomial time. We then focus on bounding the dichromatic number of dense digraphs as a function of the independence number α of the underlying graph. We consider two special cases in this regard: digraphs with χ(D) ≤ 2 and digraphs that do not contain any directed triangle. For these cases, we present algorithms which generalize and improve existing tools and results.
Cite as

Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer, Alantha Newman, and Chaoliang Tang. Hardness and Approximation for Coloring Digraphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.ICALP.2026.53,
  author =	{Chalermsook, Parinya and Gahlawat, Harmender and Klingelhoefer, Felix and Newman, Alantha and Tang, Chaoliang},
  title =	{{Hardness and Approximation for Coloring Digraphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{53:1--53:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.53},
  URN =		{urn:nbn:de:0030-drops-264421},
  doi =		{10.4230/LIPIcs.ICALP.2026.53},
  annote =	{Keywords: Graph Algorithms, Hardness of Approximation, Polynomial Time Approximation Algorithms, Structural Graph Theory}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2024.30
Improved Linearly Ordered Colorings of Hypergraphs via SDP Rounding

Authors: Anand Louis, Alantha Newman, and Arka Ray

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract
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) no edge is monochromatic, and (ii) each edge has a unique maximum color. It is an open question as to whether or not a 2-LO colorable 3-uniform hypergraph can be LO colored with 3 colors in polynomial time. Nakajima and Živný recently gave a polynomial-time algorithm to color such hypergraphs with Õ(n^{1/3}) colors and asked if SDP methods can be used directly to obtain improved bounds. Our main result is to show how to use SDP-based rounding methods to produce an LO coloring with Õ(n^{1/5}) colors for such hypergraphs. We show how to reduce the problem to cases with highly structured SDP solutions, which we call balanced hypergraphs. Then we discuss how to apply classic SDP-rounding tools in this case to obtain improved bounds.
Cite as

Anand Louis, Alantha Newman, and Arka Ray. Improved Linearly Ordered Colorings of Hypergraphs via SDP Rounding. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{louis_et_al:LIPIcs.FSTTCS.2024.30,
  author =	{Louis, Anand and Newman, Alantha and Ray, Arka},
  title =	{{Improved Linearly Ordered Colorings of Hypergraphs via SDP Rounding}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.30},
  URN =		{urn:nbn:de:0030-drops-222199},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.30},
  annote =	{Keywords: hypergraph coloring, SDP rounding, promise constraint satisfaction problems}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.71
Coloring Tournaments with Few Colors: Algorithms and Complexity

Authors: Felix Klingelhoefer and Alantha Newman

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
A k-coloring of a tournament is a partition of its vertices into k acyclic sets. Deciding if a tournament is 2-colorable is NP-hard. A natural problem, akin to that of coloring a 3-colorable graph with few colors, is to color a 2-colorable tournament with few colors. This problem does not seem to have been addressed before, although it is a special case of coloring a 2-colorable 3-uniform hypergraph with few colors, which is a well-studied problem with super-constant lower bounds. We present an efficient decomposition lemma for tournaments and show that it can be used to design polynomial-time algorithms to color various classes of tournaments with few colors, including an algorithm to color a 2-colorable tournament with ten colors. For the classes of tournaments considered, we complement our upper bounds with strengthened lower bounds, painting a comprehensive picture of the algorithmic and complexity aspects of coloring tournaments.
Cite as

Felix Klingelhoefer and Alantha Newman. Coloring Tournaments with Few Colors: Algorithms and Complexity. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{klingelhoefer_et_al:LIPIcs.ESA.2023.71,
  author =	{Klingelhoefer, Felix and Newman, Alantha},
  title =	{{Coloring Tournaments with Few Colors: Algorithms and Complexity}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{71:1--71:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.71},
  URN =		{urn:nbn:de:0030-drops-187247},
  doi =		{10.4230/LIPIcs.ESA.2023.71},
  annote =	{Keywords: Tournaments, Graph Coloring, Algorithms, Complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.56
Towards Improving Christofides Algorithm for Half-Integer TSP

Authors: Arash Haddadan and Alantha Newman

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We study the traveling salesman problem (TSP) in the case when the objective function of the subtour linear programming relaxation is minimized by a half-cycle point: x_e in {0,1/2,1} where the half-edges form a 2-factor and the 1-edges form a perfect matching. Such points are sufficient to resolve half-integer TSP in general and they have been conjectured to demonstrate the largest integrality gap for the subtour relaxation. For half-cycle points, the best-known approximation guarantee is 3/2 due to Christofides' famous algorithm. Proving an integrality gap of alpha for the subtour relaxation is equivalent to showing that alpha x can be written as a convex combination of tours, where x is any feasible solution for this relaxation. To beat Christofides' bound, our goal is to show that (3/2 - epsilon)x can be written as a convex combination of tours for some positive constant epsilon. Let y_e = 3/2-epsilon when x_e = 1 and y_e = 3/4 when x_e = 1/2. As a first step towards this goal, our main result is to show that y can be written as a convex combination of tours. In other words, we show that we can save on 1-edges, which has several applications. Among them, it gives an alternative algorithm for the recently studied uniform cover problem. Our main new technique is a procedure to glue tours over proper 3-edge cuts that are tight with respect to x, thus reducing the problem to a base case in which such cuts do not occur.
Cite as

Arash Haddadan and Alantha Newman. Towards Improving Christofides Algorithm for Half-Integer TSP. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 56:1-56:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{haddadan_et_al:LIPIcs.ESA.2019.56,
  author =	{Haddadan, Arash and Newman, Alantha},
  title =	{{Towards Improving Christofides Algorithm for Half-Integer TSP}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{56:1--56:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.56},
  URN =		{urn:nbn:de:0030-drops-111772},
  doi =		{10.4230/LIPIcs.ESA.2019.56},
  annote =	{Keywords: Traveling salesman problem, subtour elimination relaxation, integrality gap, gluing subtours}
}
Document
DOI: 10.4230/OASIcs.SOSA.2018.13
Complex Semidefinite Programming and Max-k-Cut

Authors: Alantha Newman

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)

Abstract
In a second seminal paper on the application of semidefinite programming to graph partitioning problems, Goemans and Williamson showed in 2004 how to formulate and round a complex semidefinite program to give what is to date still the best-known approximation guarantee of .836008 for Max-3-Cut. (This approximation ratio was also achieved independently around the same time by De Klerk et al..) Goemans and Williamson left open the problem of how to apply their techniques to Max-k-Cut for general k. They point out that it does not seem straightforward or even possible to formulate a good quality complex semidefinite program for the general Max-k-Cut problem, which presents a barrier for the further application of their techniques. We present a simple rounding algorithm for the standard semidefinite programmming relaxation of Max-k-Cut and show that it is equivalent to the rounding of Goemans and Williamson in the case of Max-3-Cut. This allows us to transfer the elegant analysis of Goemans and Williamson for Max-3-Cut to Max-k-Cut. For k > 3, the resulting approximation ratios are about .01 worse than the best known guarantees. Finally, we present a generalization of our rounding algorithm and conjecture (based on computational observations) that it matches the best-known guarantees of De Klerk et al.
Cite as

Alantha Newman. Complex Semidefinite Programming and Max-k-Cut. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 13:1-13:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{newman:OASIcs.SOSA.2018.13,
  author =	{Newman, Alantha},
  title =	{{Complex Semidefinite Programming and Max-k-Cut}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{13:1--13:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.13},
  URN =		{urn:nbn:de:0030-drops-83098},
  doi =		{10.4230/OASIcs.SOSA.2018.13},
  annote =	{Keywords: Graph Partitioning, Max-k-Cut, Semidefinite Programming}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.71
The Alternating Stock Size Problem and the Gasoline Puzzle

Authors: Alantha Newman, Heiko Röglin, and Johanna Seif

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Given a set S of integers whose sum is zero, consider the problem of finding a permutation of these integers such that: (i) all prefixes of the ordering are non-negative, and (ii) the maximum value of a prefix sum is minimized. Kellerer et al. referred to this problem as the stock size problem and showed that it can be approximated to within 3/2. They also showed that an approximation ratio of 2 can be achieved via several simple algorithms. We consider a related problem, which we call the alternating stock size problem, where the number of positive and negative integers in the input set S are equal. The problem is the same as above, but we are additionally required to alternate the positive and negative numbers in the output ordering. This problem also has several simple 2-approximations. We show that it can be approximated to within 1.79. Then we show that this problem is closely related to an optimization version of the gasoline puzzle due to Lovász, in which we want to minimize the size of the gas tank necessary to go around the track. We present a 2-approximation for this problem, using a natural linear programming relaxation whose feasible solutions are doubly stochastic matrices. Our novel rounding algorithm is based on a transformation that yields another doubly stochastic matrix with special properties, from which we can extract a suitable permutation.
Cite as

Alantha Newman, Heiko Röglin, and Johanna Seif. The Alternating Stock Size Problem and the Gasoline Puzzle. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{newman_et_al:LIPIcs.ESA.2016.71,
  author =	{Newman, Alantha and R\"{o}glin, Heiko and Seif, Johanna},
  title =	{{The Alternating Stock Size Problem and the Gasoline Puzzle}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{71:1--71:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.71},
  URN =		{urn:nbn:de:0030-drops-64134},
  doi =		{10.4230/LIPIcs.ESA.2016.71},
  annote =	{Keywords: approximation algorithms, stock size problem, scheduling with non-renewable resources}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact