Alantha Newman

65 papers A* 9A 5B 5Journal 37Unranked 6

Year	Rank	Type	Title / Venue / Authors
2025	A*	`conf`	Solving the Correlation Cluster LP in Sublinear Time. STOC Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, Hanwen Zhang
2025	J	`jnl`	Solving the Correlation Cluster LP in Sublinear Time. CoRR Nairen Cao, Vincent Cohen-Addad, Shi Li, Euiwoong Lee, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, Hanwen Zhang
2025	J	`jnl`	Static to Dynamic Correlation Clustering. CoRR Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, Hanwen Zhang
2024	A*	`conf`	A PTAS for SODA Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang
2024	J	`jnl`	Bounding the Chromatic Number of Dense Digraphs by Arc Neighborhoods. Comb. Felix Klingelhöfer, Alantha Newman
2024	J	`jnl`	Coloring Tournaments with Few Colors: Algorithms and Complexity. SIAM J. Discret. Math. Felix Klingelhöfer, Alantha Newman
2024	—	`conf`	Improved Linearly Ordered Colorings of Hypergraphs via SDP Rounding. FSTTCS Anand Louis, Alantha Newman, Arka Ray
2024	J	`jnl`	Improved linearly ordered colorings of hypergraphs via SDP rounding. CoRR Anand Louis, Alantha Newman, Arka Ray
2024	J	`jnl`	Understanding the Cluster LP for Correlation Clustering. CoRR Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl
2024	A*	`conf`	Understanding the Cluster Linear Program for Correlation Clustering. STOC Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl
2023	J	`jnl`	A PTAS for 𝓁 CoRR Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang
2023	J	`jnl`	A decision aid algorithm for long-haul parcel transportation based on hierarchical network structure. Int. J. Prod. Res. Camille Gras, Nathalie Herr, Alantha Newman
2023	J	`jnl`	Bounding the chromatic number of dense digraphs by arc neighborhoods. CoRR Felix Klingelhöfer, Alantha Newman
2023	A	`conf`	Coloring Tournaments with Few Colors: Algorithms and Complexity. ESA Felix Klingelhöfer, Alantha Newman
2023	J	`jnl`	Coloring tournaments with few colors: Algorithms and complexity. CoRR Felix Klingelhöfer, Alantha Newman
2023	A*	`conf`	Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. FOCS Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman
2023	J	`jnl`	Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. CoRR Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman
2023	J	`jnl`	Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours. Math. Program. Arash Haddadan, Alantha Newman
2023	—	`conf`	Voting algorithms for unique games on complete graphs. SOSA Antoine Méot, Arnaud de Mesmay, Moritz Mühlenthaler, Alantha Newman
2022	A*	`conf`	Correlation Clustering with Sherali-Adams. FOCS Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman
2022	J	`jnl`	Correlation Clustering with Sherali-Adams. CoRR Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman
2021	—	`conf`	A Hierarchical Network Approach for Long-Haul Parcel Transportation. APMS (5) Camille Gras, Van-Dat Cung, Nathalie Herr, Alantha Newman
2021	J	`jnl`	Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes. Discret. Optim. Arash Haddadan, Alantha Newman
2021	J	`jnl`	Shorter tours and longer detours: uniform covers and a bit beyond. Math. Program. Arash Haddadan, Alantha Newman, R. Ravi
2021	J	`jnl`	Voting algorithms for unique games on complete graphs. CoRR Antoine Méot, Arnaud de Mesmay, Moritz Mühlenthaler, Alantha Newman
2020	J	`jnl`	An Improved Analysis of the Mömke-Svensson Algorithm for Graph-TSP on Subquartic Graphs. SIAM J. Discret. Math. Alantha Newman
2019	J	`jnl`	Coloring Dense Digraphs. Comb. Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, Stéphan Thomassé
2019	A	`conf`	Towards Improving Christofides Algorithm for Half-Integer TSP. ESA Arash Haddadan, Alantha Newman
2019	J	`jnl`	Towards improving Christofides algorithm for half-integer TSP. CoRR Arash Haddadan, Alantha Newman
2018	—	`conf`	Complex Semidefinite Programming and Max-k-Cut. SOSA Alantha Newman
2018	J	`jnl`	Complex Semidefinite Programming and Max-k-Cut. CoRR Alantha Newman
2018	J	`jnl`	Domination and Fractional Domination in Digraphs. Electron. J. Comb. Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, Stéphan Thomassé
2018	J	`jnl`	Explicit 3-colorings for exponential graphs. CoRR Adrien Argento, Alantha Newman
2018	J	`jnl`	Polynomial-time algorithms for 2-edge-connected subgraphs on fundamental classes by top-down coloring. CoRR Arash Haddadan, Alantha Newman
2018	J	`jnl`	Rounding semidefinite programs for large-domain problems via Brownian motion. CoRR Kevin L. Chang, Alantha Newman
2018	J	`jnl`	The Alternating Stock Size Problem and the Gasoline Puzzle. ACM Trans. Algorithms Alantha Newman, Heiko Röglin, Johanna Seif
2017	J	`jnl`	Coloring dense digraphs. Electron. Notes Discret. Math. Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, Stéphan Thomassé
2017	J	`jnl`	Cover and Conquer: Augmenting Decompositions for Connectivity Problems. CoRR Arash Haddadan, Alantha Newman, R. Ravi
2016	—	`ch.`	Max Cut. Encyclopedia of Algorithms Alantha Newman
2016	A	`conf`	The Alternating Stock Size Problem and the Gasoline Puzzle. ESA Alantha Newman, Heiko Röglin, Johanna Seif
2015	J	`jnl`	On the configuration LP for maximum budgeted allocation. Math. Program. Christos Kalaitzis, Aleksander Madry, Alantha Newman, Lukás Polácek, Ola Svensson
2015	J	`jnl`	The Alternating Stock Size Problem and the Gasoline Puzzle. CoRR Alantha Newman, Heiko Röglin, Johanna Seif
2014	A	`conf`	An Improved Analysis of the Mömke-Svensson Algorithm for Graph-TSP on Subquartic Graphs. ESA Alantha Newman
2014	J	`jnl`	An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs. CoRR Alantha Newman
2014	B	`conf`	Graph-TSP from Steiner Cycles. WG Satoru Iwata, Alantha Newman, R. Ravi
2014	J	`jnl`	Graph-TSP from Steiner Cycles. CoRR Satoru Iwata, Alantha Newman, R. Ravi
2014	B	`conf`	On the Configuration LP for Maximum Budgeted Allocation. IPCO Christos Kalaitzis, Aleksander Madry, Alantha Newman, Lukas Polacek, Ola Svensson
2014	J	`jnl`	On the Configuration LP for Maximum Budgeted Allocation. CoRR Christos Kalaitzis, Aleksander Madry, Alantha Newman, Lukas Polacek, Ola Svensson
2012	A*	`conf`	Beck's Three Permutations Conjecture: A Counterexample and Some Consequences. FOCS Alantha Newman, Ofer Neiman, Aleksandar Nikolov
2011	J	`jnl`	A counterexample to Beck's conjecture on the discrepancy of three permutations CoRR Alantha Newman, Aleksandar Nikolov
2011	A	`conf`	Complex Semidefinite Programming Revisited and the Assembly of Circular Genomes. ICS Konstantin Makarychev, Alantha Newman
2011	A*	`conf`	Tight Hardness Results for Minimizing Discrepancy. SODA Moses Charikar, Alantha Newman, Aleksandar Nikolov
2010	J	`jnl`	Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes) CoRR 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
2008	J	`jnl`	Aggregating inconsistent information: Ranking and clustering. J. ACM Nir Ailon, Moses Charikar, Alantha Newman
2008	—	`ch.`	Max Cut. Encyclopedia of Algorithms Alantha Newman
2008	J	`jnl`	Traveling salesman path problems. Math. Program. Fumei Lam, Alantha Newman
2007	J	`jnl`	Decision-making based on approximate and smoothed Pareto curves. Theor. Comput. Sci. Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking
2005	A*	`conf`	Aggregating inconsistent information: ranking and clustering. STOC Nir Ailon, Moses Charikar, Alantha Newman
2005	B	`conf`	Decision Making Based on Approximate and Smoothed Pareto Curves. ISAAC Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking
2004	—	`—`	Algorithms for string and graph layout. Alantha Newman
2004	B	`conf`	Combinatorial Problems on Strings with Applications to Protein Folding. LATIN Alantha Newman, Matthias Ruhl
2004	—	`conf`	Cuts and Orderings: On Semidefinite Relaxations for the Linear Ordering Problem. APPROX-RANDOM Alantha Newman
2002	A*	`conf`	A new algorithm for protein folding in the HP model. SODA Alantha Newman
2001	B	`conf`	Fences Are Futile: On Relaxations for the Linear Ordering Problem. IPCO Alantha Newman, Santosh S. Vempala
2001	—	`conf`	The Maximum Acyclic Subgraph Problem and Degree-3 Graphs. RANDOM-APPROX Alantha Newman