Fabrizio Grandoni

Vera Traub

CoRR, 2024

A 5/4 Approximation for Two-Edge-Connectivity.

[BibT_eX]

[DOI]

Miguel Bosch-Calvo

CoRR, 2024

Unsplittable Flow on a Short Path.

[BibT_eX]

[DOI]

Ilan Doron-Arad

Ariel Kulik

Proceedings of the 19th International Symposium on Parameterized and Exact Computation, 2024

An O(loglog n)-Approximation for Submodular Facility Location.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller Than 2.

[BibT_eX]

[DOI]

Jaroslaw Byrka

Vera Traub

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Computational Geometry, 2024

2023

A Tight (3/2+ε )-Approximation for Skewed Strip Packing.

[BibT_eX]

[DOI]

Algorithmica, October, 2023

Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree.

[BibT_eX]

[DOI]

Jaroslaw Byrka

SIAM J. Comput., June, 2023

Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter.

[BibT_eX]

[DOI]

Amir Abboud

ACM Trans. Algorithms, January, 2023

A PTAS for Triangle-Free 2-Matching.

[BibT_eX]

[DOI]

Miguel Bosch-Calvo

CoRR, 2023

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median.

[BibT_eX]

[DOI]

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

Improved Approximation for Two-Edge-Connectivity.

[BibT_eX]

[DOI]

Mohit Garg

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

Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm.

[BibT_eX]

[DOI]

Claire Mathieu

Hang Zhou

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

A 4/3 Approximation for 2-Vertex-Connectivity.

[BibT_eX]

[DOI]

Miguel Bosch-Calvo

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Fully Dynamic (Δ +1)-Coloring in O(1) Update Time.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

A refined approximation for Euclidean k-means.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2022

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median.

[BibT_eX]

[DOI]

CoRR, 2022

A PTAS for unsplittable flow on a path.

[BibT_eX]

[DOI]

Tobias Mömke

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

Breaching the 2-approximation barrier for the forest augmentation problem.

[BibT_eX]

[DOI]

Vera Traub

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

Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds.

[BibT_eX]

[DOI]

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

Unsplittable Flow on a Path: The Game!.

[BibT_eX]

[DOI]

Tobias Mömke

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

2021

Approximating Geometric Knapsack via L-packings.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

On the Cycle Augmentation Problem: Hardness and Approximation Algorithms.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2021

All-Pairs LCA in DAGs: Breaking through the O(n2.5) barrier.

[BibT_eX]

[DOI]

Aleksander Lukasiewicz

Nikos Parotsidis

Przemyslaw Uznanski

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

Online Edge Coloring Algorithms via the Nibble Method.

[BibT_eX]

[DOI]

Sayan Bhattacharya

David Wajc

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

Faster (1+ε)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back.

[BibT_eX]

[DOI]

Tobias Mömke

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Computational Geometry, 2021

Approximation Algorithms for Demand Strip Packing.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

Faster Replacement Paths and Distance Sensitivity Oracles.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

The matching augmentation problem: a $\frac{7}{4}$-approximation algorithm.

[BibT_eX]

[DOI]

Math. Program., 2020

Improved Approximation Algorithms for Stochastic-Matching Problems.

[BibT_eX]

[DOI]

Marek Adamczyk

Brian Brubach

Karthik Abinav Sankararaman

Aravind Srinivasan

Pan Xu

CoRR, 2020

All-Pairs LCA in DAGs: Breaking through the O(n2.5) barrier.

[BibT_eX]

[DOI]

Aleksander Lukasiewicz

Nikos Parotsidis

Przemyslaw Uznanski

CoRR, 2020

2019

Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.

[BibT_eX]

[DOI]

Karl Bringmann

Barna Saha

SIAM J. Comput., 2019

Fully Dynamic (Δ+1)-Coloring in Constant Update Time.

[BibT_eX]

[DOI]

CoRR, 2019

Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstrauss lemma.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Dynamic set cover: improved algorithms and lower bounds.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

O(log2 k / log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm.

[BibT_eX]

[DOI]

Shi Li

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time.

[BibT_eX]

[DOI]

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

Packing Cars into Narrow Roads: PTASs for Limited Supply Highway.

[BibT_eX]

[DOI]

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

Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack.

[BibT_eX]

[DOI]

Stefan Kratsch

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

2018

Editorial fun.

[BibT_eX]

[DOI]

Erik D. Demaine

Theor. Comput. Sci., 2018

Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue.

[BibT_eX]

[DOI]

Aravindan Vijayaraghavan

Qin Zhang

ACM Trans. Algorithms, 2018

A Mazing 2+ϵ Approximation for Unsplittable Flow on a Path.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

O(log2k/log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm.

[BibT_eX]

[DOI]

Shi Li

CoRR, 2018

The Matching Augmentation Problem: A 7/4-Approximation Algorithm.

[BibT_eX]

[DOI]

CoRR, 2018

A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Improved approximation for tree augmentation: saving by rewiring.

[BibT_eX]

[DOI]

Christos Kalaitzis

Rico Zenklusen

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Distributed Approximation Algorithms via LP-Duality and Randomization.

[BibT_eX]

[DOI]

Devdatt P. Dubhashi

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

2017

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy.

[BibT_eX]

[DOI]

Danny Hermelin

ACM Trans. Algorithms, 2017

Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack.

[BibT_eX]

[DOI]

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

Preserving Distances in Very Faulty Graphs.

[BibT_eX]

[DOI]

Greg Bodwin

Merav Parter

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

When the Optimum is also Blind: a New Perspective on Universal Optimization.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Exact Algorithms for Maximum Independent Set.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Pricing on Paths: A PTAS for the Highway Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Surviving in Directed Graphs: A Polylogarithmic Approximation for Two-Connected Directed Steiner Tree.

[BibT_eX]

[DOI]

CoRR, 2016

Online Network Design with Outliers.

[BibT_eX]

[DOI]

Algorithmica, 2016

Improved Pseudo-Polynomial-Time Approximation for Strip Packing.

[BibT_eX]

[DOI]

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

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product.

[BibT_eX]

[DOI]

Karl Bringmann

Barna Saha

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

An LP-rounding 2√2-approximation for restricted maximum acyclic subgraph.

[BibT_eX]

[DOI]

Tomasz Kociumaka

Michal Wlodarczyk

Inf. Process. Lett., 2015

Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows.

[BibT_eX]

[DOI]

Salvatore Ingala

Sumedha Uniyal

Proceedings of the Approximation and Online Algorithms - 13th International Workshop, 2015

On Conflict-Free Multi-coloring.

[BibT_eX]

[DOI]

Andreas Bärtschi

Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

On Survivable Set Connectivity.

[BibT_eX]

[DOI]

Parinya Chalermsook

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Improved Purely Additive Fault-Tolerant Spanners.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

Improved Approximation Algorithms for Stochastic Matching.

[BibT_eX]

[DOI]

Marek Adamczyk

Joydeep Mukherjee

Proceedings of the Algorithms - ESA 2015, 2015

2014

Utilitarian Mechanism Design for Multiobjective Optimization.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

New approaches to multi-objective optimization.

[BibT_eX]

[DOI]

Math. Program., 2014

An LP-Rounding $2\sqrt{2}$ Approximation for Restricted Maximum Acyclic Subgraph.

[BibT_eX]

[DOI]

Tomasz Kociumaka

Michal Wlodarczyk

CoRR, 2014

A Mazing 2+∊ Approximation for Unsplittable Flow on a Path.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

Set Covering with Our Eyes Closed.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Data structures resilient to memory faults: An experimental study of dictionaries.

[BibT_eX]

[DOI]

Umberto Ferraro Petrillo

ACM J. Exp. Algorithmics, 2013

Steiner Tree Approximation via Iterative Randomized Rounding.

[BibT_eX]

[DOI]

J. ACM, 2013

Computing Optimal Steiner Trees in Polynomial Space.

[BibT_eX]

[DOI]

Algorithmica, 2013

On Pairwise Spanners.

[BibT_eX]

[DOI]

Telikepalli Kavitha

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

How to Sell Hyperedges: The Hypermatching Assignment Problem.

[BibT_eX]

[DOI]

Monaldo Mastrolilli

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy - (Extended Abstract).

[BibT_eX]

[DOI]

Danny Hermelin

Proceedings of the Algorithms - ESA 2013, 2013

2012

A Mazing 2+eps Approximation for Unsplittable Flow on a Path

[BibT_eX]

[DOI]

CoRR, 2012

Sharp Separation and Applications to Exact and Parameterized Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 2012

Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths.

[BibT_eX]

[DOI]

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

On Min-Power Steiner Tree.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2012, 2012

A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2012, 2012

2011

Budgeted matching and budgeted matroid intersection via the gasoline puzzle.

[BibT_eX]

[DOI]

Math. Program., 2011

From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk.

[BibT_eX]

[DOI]

Laura Sanità

Math. Oper. Res., 2011

Approximation Algorithms for Single and Multi-Commodity Connected Facility Location.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Approximation Algorithms for Union and Intersection Covering Problems.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

2010

Stable routing under the Spanning Tree Protocol.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2010

Connected facility location via random facility sampling and core detouring.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2010

Prizing on Paths: A PTAS for the Highway Problem

[BibT_eX]

[DOI]

CoRR, 2010

Optimization with More than One Budget

[BibT_eX]

[DOI]

Rico Zenklusen

CoRR, 2010

An improved LP-based approximation for steiner tree.

[BibT_eX]

[DOI]

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

Utilitarian Mechanism Design for Multi-Objective Optimization.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Network Design via Core Detouring for Problems without a Core.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Approximation Schemes for Multi-Budgeted Independence Systems.

[BibT_eX]

[DOI]

Rico Zenklusen

Proceedings of the Algorithms, 2010

2009

Optimal resilient sorting and searching in the presence of memory faults.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Balanced cut approximation in random geometric graphs.

[BibT_eX]

[DOI]

Josep Díaz

Alberto Marchetti-Spaccamela

Theor. Comput. Sci., 2009

Resilient dictionaries.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

A measure & conquer approach for the analysis of exact algorithms.

[BibT_eX]

[DOI]

J. ACM, 2009

Iterative Rounding for Multi-Objective Optimization Problems.

[BibT_eX]

[DOI]

R. Ravi

Mohit Singh

Proceedings of the Algorithms, 2009

2008

Exact Algorithms for Dominating Set.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Distributed weighted vertex cover via maximal matchings.

[BibT_eX]

[DOI]

Jochen Könemann

ACM Trans. Algorithms, 2008

Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2008

A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

A short proof of the VPN Tree Routing Conjecture on ring networks.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2008

Solving Connected Dominating Set Faster than 2 n .

[BibT_eX]

[DOI]

Algorithmica, 2008

Approximating connected facility location problems via random facility sampling and core detouring.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Faster Steiner Tree Computation in Polynomial-Space.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2008

2007

Distributed Approximation Algorithms via LP-Duality and Randomization.

[BibT_eX]

[DOI]

Devdatt P. Dubhashi

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

New Approaches for Virtual Private Network Design.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Designing reliable algorithms in unreliable memories.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2007

Resilient search trees.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Fast Low Degree Connectivity of Ad-Hoc Networks Via Percolation.

[BibT_eX]

[DOI]

Emilio De Santis

Proceedings of the Algorithms, 2007

Optimal Resilient Dynamic Dictionaries.

[BibT_eX]

[DOI]

Gerth Stølting Brodal

Allan Grønlund Jørgensen

Gabriel Moruz

Thomas Mølhave

Proceedings of the Algorithms, 2007

2006

A note on the complexity of minimum dominating set.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2006

A linear time algorithm to list the minimal separators of chordal graphs.

[BibT_eX]

[DOI]

L. Sunil Chandran

Discret. Math., 2006

Measure and conquer: a simple O(20.288n) independent set algorithm.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Improved Approximation for Single-Sink Buy-at-Bulk.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

Algorithms and Constraint Programming.

[BibT_eX]

[DOI]

Proceedings of the Principles and Practice of Constraint Programming, 2006

2005

Refined memorization for vertex cover.

[BibT_eX]

[DOI]

L. Sunil Chandran

Inf. Process. Lett., 2005

On maximum number of minimal dominating sets in graphs.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2005

Some New Techniques in Design and Analysis of Exact (Exponential) Algorithms.

[BibT_eX]

Bull. EATCS, 2005

An improved approximation algorithm for virtual private network design.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Primal-dual based distributed algorithms for vertex cover with semi-hard capacities.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, 2005

Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Measure and Conquer: Domination - A Case Study.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004

On the complexity of fixed parameter clique and dominating set.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

Theor. Comput. Sci., 2004

Decremental Clique Problem.

[BibT_eX]

[DOI]

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

Refined Memorisation for Vertex Cover.

[BibT_eX]

[DOI]

L. Sunil Chandran

Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004

2003

Detecting directed 4-cycles still faster.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

Inf. Process. Lett., 2003

Improved Algorithms for Max-restricted Path Consistency.

[BibT_eX]

[DOI]