Ola Svensson

Math. Program., February, 2023

Scheduling (Dagstuhl Seminar 23061).

[BibT_eX]

[DOI]

Dagstuhl Reports, February, 2023

An Analysis of $D^α$ seeding for $k$-means.

[BibT_eX]

[DOI]

Étienne Bamas

Sai Ganesh Nagarajan

CoRR, 2023

The Exact Bipartite Matching Polytope Has Exponential Extension Complexity.

[BibT_eX]

[DOI]

Xinrui Jia

Weiqiang Yuan

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

Speeding Up Bellman Ford via Minimum Violation Permutations.

[BibT_eX]

[DOI]

Silvio Lattanzi

Sergei Vassilvitskii

Proceedings of the International Conference on Machine Learning, 2023

The Price of Explainability for Clustering.

[BibT_eX]

[DOI]

Anupam Gupta

Madhusudhan Reddy Pittu

Rachel Yuan

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

Online Algorithms with Costly Predictions.

[BibT_eX]

[DOI]

Marina Drygala

Sai Ganesh Nagarajan

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2023

2022

A Framework for the Secretary Problem on the Intersection of Matroids.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Fair colorful k-center clustering.

[BibT_eX]

[DOI]

Xinrui Jia

Kshiteej Sheth

Math. Program., 2022

On inequalities with bounded coefficients and pitch for the min knapsack polytope.

[BibT_eX]

[DOI]

Discret. Optim., 2022

Flow time scheduling and prefix Beck-Fiala.

[BibT_eX]

[DOI]

Nikhil Bansal

Lars Rohwedder

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Towards Non-Uniform k-Center with Constant Types of Radii.

[BibT_eX]

[DOI]

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem.

[BibT_eX]

[DOI]

Étienne Bamas

Marina Drygala

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

Streaming Submodular Maximization Under Matroid Constraints.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Submodular Maximization Subject to Matroid Intersection on the Fly.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

Approximate Cluster Recovery from Noisy Labels.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Online Contention Resolution Schemes with Applications to Bayesian Selection Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines.

[BibT_eX]

[DOI]

Nikhil Bansal

Aravind Srinivasan

SIAM J. Comput., 2021

Towards Non-Uniform k-Center with Constant Types of Radii.

[BibT_eX]

[DOI]

CoRR, 2021

Streaming Submodular Maximization with Matroid and Matching Constraints.

[BibT_eX]

[DOI]

CoRR, 2021

A QPTAS for stabbing rectangles.

[BibT_eX]

[DOI]

CoRR, 2021

Consistent k-Clustering for General Metrics.

[BibT_eX]

[DOI]

Hendrik Fichtenberger

Silvio Lattanzi

Ashkan Norouzi-Fard

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

Nearly-Tight and Oblivious Algorithms for Explainable Clustering.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Parallel and Efficient Hierarchical k-Median Clustering.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

2020

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem.

[BibT_eX]

[DOI]

László A. Végh

J. ACM, 2020

Scheduling (Dagstuhl Seminar 20081).

[BibT_eX]

[DOI]

Nicole Megow

David B. Shmoys

Dagstuhl Reports, 2020

Fast and Accurate $k$-means++ via Rejection Sampling.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

The Primal-Dual method for Learning Augmented Algorithms.

[BibT_eX]

[DOI]

Étienne Bamas

Andreas Maggiori

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Learning Augmented Energy Minimization via Speed Scaling.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Robust Algorithms Under Adversarial Injections.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

No Small Linear Program Approximates Vertex Cover Within a Factor 2 - ɛ.

[BibT_eX]

[DOI]

Math. Oper. Res., 2019

Beating Greedy for Stochastic Bipartite Matching.

[BibT_eX]

[DOI]

Buddhima Gamlath

Sagar Kale

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Weighted Matchings via Unweighted Augmentations.

[BibT_eX]

[DOI]

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Approximately Good and Modern Matchings (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Online Matching with General Arrivals.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

New Notions and Constructions of Sparsification for Graphs and Hypergraphs.

[BibT_eX]

[DOI]

Nikhil Bansal

Teklemariam Tsegay Tesfay

Luca Trevisan

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Optimal Software Patching Plan for PMUs.

[BibT_eX]

[DOI]

Jean-Yves Le Boudec

IEEE Trans. Smart Grid, 2018

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits.

[BibT_eX]

[DOI]

Theory Comput., 2018

Constant factor approximation for ATSP with two edge weights.

[BibT_eX]

[DOI]

László A. Végh

Math. Program., 2018

A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem.

[BibT_eX]

[DOI]

Math. Oper. Res., 2018

On Bounded Pitch Inequalities for the Min-Knapsack Polytope.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization - 5th International Symposium, 2018

Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams.

[BibT_eX]

[DOI]

Proceedings of the 35th International Conference on Machine Learning, 2018

Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering.

[BibT_eX]

[DOI]

Buddhima Gamlath

Sangxia Huang

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Algorithms for the Asymmetric Traveling Salesman Problem (Invited Paper).

[BibT_eX]

[DOI]

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

2017

Combinatorial Algorithm for Restricted Max-Min Fair Allocation.

[BibT_eX]

[DOI]

Chidambaram Annamalai

Christos Kalaitzis

ACM Trans. Algorithms, 2017

Dynamic Facility Location via Exponential Clocks.

[BibT_eX]

[DOI]

Hyung-Chan An

Ashkan Norouzi-Fard

ACM Trans. Algorithms, 2017

LP-Based Algorithms for Capacitated Facility Location.

[BibT_eX]

[DOI]

Hyung-Chan An

Mohit Singh

SIAM J. Comput., 2017

The Matching Problem in General Graphs is in Quasi-NC.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios.

[BibT_eX]

[DOI]

Christos Kalaitzis

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation.

[BibT_eX]

[DOI]

Lukás Polácek

ACM Trans. Algorithms, 2016

Approximating k-Median via Pseudo-Approximation.

[BibT_eX]

[DOI]

Shi Li

SIAM J. Comput., 2016

Removing and Adding Edges for the Traveling Salesman Problem.

[BibT_eX]

[DOI]

Tobias Mömke

J. ACM, 2016

Online Contention Resolution Schemes.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Linear Relaxations for Finding Diverse Elements in Metric Spaces.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Constant Factor Approximation for ATSP with Two Edge Weights - (Extended Abstract).

[BibT_eX]

[DOI]

László A. Végh

Proceedings of the Integer Programming and Combinatorial Optimization, 2016

Algorithms with Provable Guarantees for Clustering.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Special Issue: APPROX-RANDOM 2013: Guest Editors' Foreword.

[BibT_eX]

[DOI]

Sofya Raskhodnikova

Alberto Marchetti-Spaccamela

Theory Comput., 2015

On the configuration LP for maximum budgeted allocation.

[BibT_eX]

[DOI]

Math. Program., 2015

Strong LP formulations for scheduling splittable jobs on unrelated machines.

[BibT_eX]

[DOI]

José Correa

Math. Program., 2015

Centrality of trees for capacitated k-center.

[BibT_eX]

[DOI]

Math. Program., 2015

No Small Linear Program Approximates Vertex Cover within a Factor 2-ε.

[BibT_eX]

[DOI]

CoRR, 2015

Approximating ATSP by Relaxing Connectivity.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

A Simple Order-Oblivious O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem.

[BibT_eX]

[DOI]

CoRR, 2014

2013

Hardness of Vertex Deletion and Project Scheduling.

[BibT_eX]

[DOI]

Theory Comput., 2013

Single machine scheduling with scenarios.

[BibT_eX]

[DOI]

Nikolaus Mutsanas

Theor. Comput. Sci., 2013

Centrality of Trees for Capacitated k-Center

[BibT_eX]

[DOI]

Hyung-Chan An

Aditya Bhaskara

CoRR, 2013

Overview of New Approaches for Approximating TSP.

[BibT_eX]

[DOI]

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

2012

Tight approximation algorithms for scheduling with fixed jobs and nonavailability.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

Santa Claus Schedules Jobs on Unrelated Machines.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

2011

Hardness of Precedence Constrained Scheduling on Identical Machines.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut.

[BibT_eX]

[DOI]

Christoph Ambühl

SIAM J. Comput., 2011

On the Approximability of Single-Machine Scheduling with Precedence Constraints.

[BibT_eX]

[DOI]

Math. Oper. Res., 2011

Hardness of Approximating Flow and Job Shop Scheduling Problems.

[BibT_eX]

[DOI]

J. ACM, 2011

Approximating Graphic TSP by Matchings.

[BibT_eX]

[DOI]

Tobias Mömke

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Faster Approximation Algorithms for Scheduling with Fixed Jobs.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Computing: The Australasian Theory Symposium, 2011

2010

Minimizing the sum of weighted completion times in a concurrent open shop.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2010

Approximating Linear Threshold Predicates.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Conditional hardness of precedence constrained scheduling on identical machines.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2009

Improved Bounds for Flow Shop Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Precedence Constraint Scheduling and Connections to Dimension Theory of Partial Orders.

[BibT_eX]

Bull. EATCS, 2008

(Acyclic) JobShops are Hard to Approximate.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Approximating Single Machine Scheduling with Scenarios.

[BibT_eX]

[DOI]

Nikolaus Mutsanas

Proceedings of the Approximation, 2008

2007

Scheduling with Precedence Constraints of Low Fractional Dimension.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2007

Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling.

[BibT_eX]

[DOI]

Christoph Ambühl

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Linear Complementarity and P-Matrices for Stochastic Games.

[BibT_eX]

[DOI]

Sergei G. Vorobyov

Proceedings of the Perspectives of Systems Informatics, 2006

Approximating Precedence-Constrained Single Machine Scheduling by Coloring.

[BibT_eX]

[DOI]

Christoph Ambühl

Proceedings of the Approximation, 2006

Linear Programming Polytope and Algorithm for Mean Payoff Games.

[BibT_eX]

[DOI]