Alantha Newman

According to our database, Alantha Newman authored at least 43 papers between 2001 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Bounding the Chromatic Number of Dense Digraphs by Arc Neighborhoods.

Felix Klingelhöfer, Alantha Newman

Comb., August, 2024

Understanding the Cluster LP for Correlation Clustering.

Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl

CoRR, 2024

Understanding the Cluster Linear Program for Correlation Clustering.

Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

A PTAS for <i>ℓ</i>₀-Low Rank Approximation: Solving Dense CSPs over Reals.

Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Improved Linearly Ordered Colorings of Hypergraphs via SDP Rounding.

Anand Louis, Alantha Newman, Arka Ray

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

2023

A decision aid algorithm for long-haul parcel transportation based on hierarchical network structure.

Camille Gras, Nathalie Herr, Alantha Newman

Int. J. Prod. Res., November, 2023

Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours.

Arash Haddadan, Alantha Newman

Math. Program., March, 2023

A PTAS for 𝓁₀-Low Rank Approximation: Solving Dense CSPs over Reals.

Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang

CoRR, 2023

Voting algorithms for unique games on complete graphs.

Antoine Méot, Arnaud de Mesmay, Moritz Mühlenthaler, Alantha Newman

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering.

Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Coloring Tournaments with Few Colors: Algorithms and Complexity.

Felix Klingelhöfer, Alantha Newman

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Correlation Clustering with Sherali-Adams.

Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Shorter tours and longer detours: uniform covers and a bit beyond.

Arash Haddadan, Alantha Newman, R. Ravi

Math. Program., 2021

Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes.

Arash Haddadan, Alantha Newman

Discret. Optim., 2021

A Hierarchical Network Approach for Long-Haul Parcel Transportation.

Camille Gras, Van-Dat Cung, Nathalie Herr, Alantha Newman

Proceedings of the Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems, 2021

2020

An Improved Analysis of the Mömke-Svensson Algorithm for Graph-TSP on Subquartic Graphs.

Alantha Newman

SIAM J. Discret. Math., 2020

2019

Towards Improving Christofides Algorithm for Half-Integer TSP.

Arash Haddadan, Alantha Newman

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

The Alternating Stock Size Problem and the Gasoline Puzzle.

Alantha Newman, Heiko Röglin, Johanna Seif

ACM Trans. Algorithms, 2018

Rounding semidefinite programs for large-domain problems via Brownian motion.

Kevin L. Chang, Alantha Newman

CoRR, 2018

Polynomial-time algorithms for 2-edge-connected subgraphs on fundamental classes by top-down coloring.

Arash Haddadan, Alantha Newman

CoRR, 2018

Explicit 3-colorings for exponential graphs.

Adrien Argento, Alantha Newman

CoRR, 2018

Domination and Fractional Domination in Digraphs.

Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, Stéphan Thomassé

Electron. J. Comb., 2018

Complex Semidefinite Programming and Max-k-Cut.

Alantha Newman

Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

2017

Coloring dense digraphs.

Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, Stéphan Thomassé

Electron. Notes Discret. Math., 2017

Cover and Conquer: Augmenting Decompositions for Connectivity Problems.

Arash Haddadan, Alantha Newman, R. Ravi

CoRR, 2017

2016

Max Cut.

Alantha Newman

Encyclopedia of Algorithms, 2016

2015

On the configuration LP for maximum budgeted allocation.

Christos Kalaitzis, Aleksander Madry, Alantha Newman, Lukás Polácek, Ola Svensson

Math. Program., 2015

2014

Graph-TSP from Steiner Cycles.

Satoru Iwata, Alantha Newman, R. Ravi

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

2012

Beck's Three Permutations Conjecture: A Counterexample and Some Consequences.

Alantha Newman, Ofer Neiman, Aleksandar Nikolov

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

A counterexample to Beck's conjecture on the discrepancy of three permutations

Alantha Newman, Aleksandar Nikolov

CoRR, 2011

Tight Hardness Results for Minimizing Discrepancy.

Moses Charikar, Alantha Newman, Aleksandar Nikolov

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Complex Semidefinite Programming Revisited and the Assembly of Circular Genomes.

Konstantin Makarychev, Alantha Newman

Proceedings of the Innovations in Computer Science, 2011

2010

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

Prahladh Harsha, Moses Charikar, Matthew Andrews, Sanjeev Arora, Subhash Khot, Dana Moshkovitz, Lisa Zhang, Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard, Gwen Spencer

CoRR, 2010

2008

Max Cut.

Alantha Newman

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Traveling salesman path problems.

Fumei Lam, Alantha Newman

Math. Program., 2008

Aggregating inconsistent information: Ranking and clustering.

Nir Ailon, Moses Charikar, Alantha Newman

J. ACM, 2008

2007

Decision-making based on approximate and smoothed Pareto curves.

Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking

Theor. Comput. Sci., 2007

2004

Algorithms for string and graph layout.

Alantha Newman

PhD thesis, 2004

Combinatorial Problems on Strings with Applications to Protein Folding.

Alantha Newman, Matthias Ruhl

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Cuts and Orderings: On Semidefinite Relaxations for the Linear Ordering Problem.

Alantha Newman

Proceedings of the Approximation, 2004

2002

A new algorithm for protein folding in the HP model.

Alantha Newman

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001

The Maximum Acyclic Subgraph Problem and Degree-3 Graphs.

Alantha Newman

Proceedings of the Approximation, 2001

Fences Are Futile: On Relaxations for the Linear Ordering Problem.

Alantha Newman, Santosh S. Vempala

Proceedings of the Integer Programming and Combinatorial Optimization, 2001