5 citations · 8 across the 3 of their papers we have counts for
5 papers
Approximating Geometric Knapsack via L-packings
Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich +3
We study the two-dimensional geometric knapsack problem (2DK) in which we are given a set of n axis-aligned rectangular items, each one with an associated profit, and an axis-align…
Approximation Schemes for Independent Set and Sparse Subsets of Polygons
Anna Adamaszek, Sariel Har-Peled, Andreas Wiese
We present an -approximation algorithm with quasi-polynomial running time for computing the maximum weight independent set of polygons out of a given set of polygo…
This House Proves that Debating is Harder than Soccer
Stefan Neumann, Andreas Wiese
During the last twenty years, a lot of research was conducted on the sport elimination problem: Given a sports league and its remaining matches, we have to decide whether a given t…
Competitive-Ratio Approximation Schemes for Minimizing the Makespan in the Online-List Model
Nicole Megow, Andreas Wiese
We consider online scheduling on multiple machines for jobs arriving one-by-one with the objective of minimizing the makespan. For any number of identical parallel or uniformly rel…
A Mazing 2+eps Approximation for Unsplittable Flow on a Path
Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi +1
We study the unsplittable flow on a path problem (UFP) where we are given a path with non-negative edge capacities and tasks, which are characterized by a subpath, a demand, and a…