research
∙
05/03/2023
A 4/3 Approximation for 2-Vertex-Connectivity
The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the mo...
share
research
∙
11/10/2022
An O(loglog n)-Approximation for Submodular Facility Location
In the Submodular Facility Location problem (SFL) we are given a collect...
research
∙
09/21/2022
Improved Approximation for Two-Edge-Connectivity
The basic goal of survivable network design is to construct low-cost net...
research
∙
09/12/2022
Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm
In the unsplittable capacitated vehicle routing problem, we are given a ...
research
∙
07/11/2022
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
The Uncapacitated Facility Location (UFL) problem is one of the most fun...
research
∙
12/22/2021
Breaching the 2-Approximation Barrier for the Forest Augmentation Problem
The basic goal of survivable network design is to build cheap networks t...
research
∙
08/19/2021
Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds
In their breakthrough ICALP'15 paper, Bernstein and Stein presented an a...
research
∙
07/15/2021
A Refined Approximation for Euclidean k-Means
In the Euclidean k-Means problem we are given a collection of n points D...
research
∙
05/18/2021
Approximation Algorithms for Demand Strip Packing
In the Demand Strip Packing problem (DSP), we are given a time interval ...
research
∙
03/18/2021
Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More
In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsa...
research
∙
10/30/2020
Online Edge Coloring Algorithms via the Nibble Method
Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured ...
research
∙
10/14/2020
Improved Approximation Algorithms for Stochastic-Matching Problems
We consider the Stochastic Matching problem, which is motivated by appli...
research
∙
07/17/2020
All-Pairs LCA in DAGs: Breaking through the O(n^2.5) barrier
Let G=(V,E) be an n-vertex directed acyclic graph (DAG). A lowest common...
research
∙
11/06/2019
Breaching the 2-Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner Tree
The basic goal of survivable network design is to build a cheap network ...
research
∙
10/04/2019
Fully Dynamic (Δ+1)-Coloring in Constant Update Time
The problem of (vertex) (Δ+1)-coloring a graph of maximum degree Δ has b...
research
∙
06/26/2019
Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
The area of parameterized approximation seeks to combine approximation a...
research
∙
11/07/2018
O(^2k/k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
In the Directed Steiner Tree (DST) problem we are given an n-vertex dire...
research
∙
10/17/2018
The Matching Augmentation Problem: A 7/4-Approximation Algorithm
We present a 7/4 approximation algorithm for the matching augmentation p...
research
∙
04/06/2018
Improved Approximation for Tree Augmentation: Saving by Rewiring
The Tree Augmentation Problem (TAP) is a fundamental network design prob...
research
∙
01/23/2018
Improved Pseudo-Polynomial-Time Approximation for Strip Packing
We study the strip packing problem, a classical packing problem which ge...
research
∙
11/21/2017
Approximating Geometric Knapsack via L-packings
We study the two-dimensional geometric knapsack problem (2DK) in which w...
research
∙
07/06/2017