
Maintaining an EDCS in General Graphs: Simpler, DensitySensitive and with WorstCase Time Bounds
In their breakthrough ICALP'15 paper, Bernstein and Stein presented an a...
read it

A Refined Approximation for Euclidean kMeans
In the Euclidean kMeans problem we are given a collection of n points D...
read it

Approximation Algorithms for Demand Strip Packing
In the Demand Strip Packing problem (DSP), we are given a time interval ...
read it

Improved Approximation Algorithms for 2Dimensional Knapsack: Packing into Multiple LShapes, Spirals, and More
In the 2Dimensional Knapsack problem (2DK) we are given a square knapsa...
read it

Online Edge Coloring Algorithms via the Nibble Method
Nearly thirty years ago, BarNoy, Motwani and Naor [IPL'92] conjectured ...
read it

Improved Approximation Algorithms for StochasticMatching Problems
We consider the Stochastic Matching problem, which is motivated by appli...
read it

AllPairs LCA in DAGs: Breaking through the O(n^2.5) barrier
Let G=(V,E) be an nvertex directed acyclic graph (DAG). A lowest common...
read it

Breaching the 2Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner Tree
The basic goal of survivable network design is to build a cheap network ...
read it

Fully Dynamic (Δ+1)Coloring in Constant Update Time
The problem of (vertex) (Δ+1)coloring a graph of maximum degree Δ has b...
read it

Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
The area of parameterized approximation seeks to combine approximation a...
read it

O(^2k/k)Approximation Algorithm for Directed Steiner Tree: A Tight QuasiPolynomialTime Algorithm
In the Directed Steiner Tree (DST) problem we are given an nvertex dire...
read it

The Matching Augmentation Problem: A 7/4Approximation Algorithm
We present a 7/4 approximation algorithm for the matching augmentation p...
read it

Improved Approximation for Tree Augmentation: Saving by Rewiring
The Tree Augmentation Problem (TAP) is a fundamental network design prob...
read it

Improved PseudoPolynomialTime Approximation for Strip Packing
We study the strip packing problem, a classical packing problem which ge...
read it

Approximating Geometric Knapsack via Lpackings
We study the twodimensional geometric knapsack problem (2DK) in which w...
read it

When the Optimum is also Blind: a New Perspective on Universal Optimization
Consider the following variant of the set cover problem. We are given a ...
read it
Fabrizio Grandoni
is this you? claim profile