4 papers
Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely +1
The (Non-Preemptive) Throughput Maximization problem is a natural and fundamental scheduling problem. We are given jobs, where each job is characterized by a processing tim…
On the Approximability of Unsplittable Flow on a Path with Time Windows
Alexander Armbruster, Fabrizio Grandoni, Edin Husić +2
In the Time-Windows Unsplittable Flow on a Path problem (twUFP) we are given a resource whose available amount changes over a given time interval (modeled as the edge-capacities of…
Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions
Fabrizio Grandoni, Edin Husić, Mathieu Mari +1
In the maximum independent set of convex polygons problem, we are given a set of convex polygons in the plane with the objective of selecting a maximum cardinality subset of no…
An O(loglog n)-Approximation for Submodular Facility Location
Fateme Abbasi, Marek Adamczyk, Miguel Bosch-Calvo +4
In the Submodular Facility Location problem (SFL) we are given a collection of clients and facilities in a metric space. A feasible solution consists of an assignment of ea…