3 Search Results for "Bender, Andreas"

Document
DOI: 10.4230/LIPIcs.ESA.2019.53
Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack

Authors: Fabrizio Grandoni, Stefan Kratsch, and Andreas Wiese

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1+epsilon)-approximations in f(k,epsilon)n^O(1) time where k is some parameter of the input. The goal is to overcome lower bounds from either of the areas. We obtain the following results on parameterized approximability: - In the maximum independent set of rectangles problem (MISR) we are given a collection of n axis parallel rectangles in the plane. Our goal is to select a maximum-cardinality subset of pairwise non-overlapping rectangles. This problem is NP-hard and also W[1]-hard [Marx, ESA'05]. The best-known polynomial-time approximation factor is O(log log n) [Chalermsook and Chuzhoy, SODA'09] and it admits a QPTAS [Adamaszek and Wiese, FOCS'13; Chuzhoy and Ene, FOCS'16]. Here we present a parameterized approximation scheme (PAS) for MISR, i.e. an algorithm that, for any given constant epsilon>0 and integer k>0, in time f(k,epsilon)n^g(epsilon), either outputs a solution of size at least k/(1+epsilon), or declares that the optimum solution has size less than k. - In the (2-dimensional) geometric knapsack problem (2DK) we are given an axis-aligned square knapsack and a collection of axis-aligned rectangles in the plane (items). Our goal is to translate a maximum cardinality subset of items into the knapsack so that the selected items do not overlap. In the version of 2DK with rotations (2DKR), we are allowed to rotate items by 90 degrees. Both variants are NP-hard, and the best-known polynomial-time approximation factor is 2+epsilon [Jansen and Zhang, SODA'04]. These problems admit a QPTAS for polynomially bounded item sizes [Adamaszek and Wiese, SODA'15]. We show that both variants are W[1]-hard. Furthermore, we present a PAS for 2DKR. For all considered problems, getting time f(k,epsilon)n^O(1), rather than f(k,epsilon)n^g(epsilon), would give FPT time f'(k)n^O(1) exact algorithms by setting epsilon=1/(k+1), contradicting W[1]-hardness. Instead, for each fixed epsilon>0, our PASs give (1+epsilon)-approximate solutions in FPT time. For both MISR and 2DKR our techniques also give rise to preprocessing algorithms that take n^g(epsilon) time and return a subset of at most k^g(epsilon) rectangles/items that contains a solution of size at least k/(1+epsilon) if a solution of size k exists. This is a special case of the recently introduced notion of a polynomial-size approximate kernelization scheme [Lokshtanov et al., STOC'17].
Cite as

Fabrizio Grandoni, Stefan Kratsch, and Andreas Wiese. Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 53:1-53:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{grandoni_et_al:LIPIcs.ESA.2019.53,
  author =	{Grandoni, Fabrizio and Kratsch, Stefan and Wiese, Andreas},
  title =	{{Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.53},
  URN =		{urn:nbn:de:0030-drops-111741},
  doi =		{10.4230/LIPIcs.ESA.2019.53},
  annote =	{Keywords: parameterized approximation, parameterized intractability, independent set of rectangles, geometric knapsack}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.54
Packing Cars into Narrow Roads: PTASs for Limited Supply Highway

Authors: Fabrizio Grandoni and Andreas Wiese

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In the Highway problem, we are given a path with n edges (the highway), and a set of m drivers, each one characterized by a subpath and a budget. For a given assignment of edge prices (the tolls), the highway owner collects from each driver the total price of the associated path when it does not exceed drivers’s budget, and zero otherwise. The goal is to choose the prices to maximize the total profit. A PTAS is known for this (strongly NP-hard) problem [Grandoni,Rothvoss-SODA'11, SICOMP'16]. In this paper we study the limited supply generalization of Highway, that incorporates capacity constraints. Here the input also includes a capacity u_e >= 0 for each edge e; we need to select, among drivers that can afford the required price, a subset such that the number of drivers that use each edge e is at most u_e (and we get profit only from selected drivers). To the best of our knowledge, the only approximation algorithm known for this problem is a folklore O(log m) approximation based on a reduction to the related Unsplittable Flow on a Path problem (UFP). The main result of this paper is a PTAS for limited supply highway. As a second contribution, we study a natural generalization of the problem where each driver i demands a different amount d_i of capacity. Using known techniques, it is not hard to derive a QPTAS for this problem. Here we present a PTAS for the case that drivers have uniform budgets. Finding a PTAS for non-uniform-demand limited supply highway is left as a challenging open problem.
Cite as

Fabrizio Grandoni and Andreas Wiese. Packing Cars into Narrow Roads: PTASs for Limited Supply Highway. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 54:1-54:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{grandoni_et_al:LIPIcs.ESA.2019.54,
  author =	{Grandoni, Fabrizio and Wiese, Andreas},
  title =	{{Packing Cars into Narrow Roads: PTASs for Limited Supply Highway}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.54},
  URN =		{urn:nbn:de:0030-drops-111751},
  doi =		{10.4230/LIPIcs.ESA.2019.54},
  annote =	{Keywords: approximation algorithms, pricing problems, highway problem, unsplittable flow on a path}
}
Document
DOI: 10.4230/DagRep.3.5.78
Computational Methods Aiding Early-Stage Drug Design (Dagstuhl Seminar 13212)

Authors: Andreas Bender, Hinrich Göhlmann, Sepp Hochreiter, and Ziv Shkedy

Published in: Dagstuhl Reports, Volume 3, Issue 5 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13212 "Computational Methods Aiding Early-Stage Drug Design". The aim of the seminar was to bring scientists working on various aspects of drug discovery, genomic technologies and computational science (e.g., bioinformatics, chemoinformatics, machine learning, and statistics) together to explore how high dimensional data sets created by genomic technologies can be integrated to identify functional manifestations of drug actions on living cells early in the drug discovery process.
Cite as

Andreas Bender, Hinrich Göhlmann, Sepp Hochreiter, and Ziv Shkedy. Computational Methods Aiding Early-Stage Drug Design (Dagstuhl Seminar 13212). In Dagstuhl Reports, Volume 3, Issue 5, pp. 78-94, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{bender_et_al:DagRep.3.5.78,
  author =	{Bender, Andreas and G\"{o}hlmann, Hinrich and Hochreiter, Sepp and Shkedy, Ziv},
  title =	{{Computational Methods Aiding Early-Stage Drug Design (Dagstuhl Seminar 13212)}},
  pages =	{78--94},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{5},
  editor =	{Bender, Andreas and G\"{o}hlmann, Hinrich and Hochreiter, Sepp and Shkedy, Ziv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.5.78},
  URN =		{urn:nbn:de:0030-drops-41791},
  doi =		{10.4230/DagRep.3.5.78},
  annote =	{Keywords: Bioinformatics, Chemoinformatics, Machine learning, Statistics, Interdisciplinary applications}
}
  • Refine by Author
  • 2 Grandoni, Fabrizio
  • 2 Wiese, Andreas
  • 1 Bender, Andreas
  • 1 Göhlmann, Hinrich
  • 1 Hochreiter, Sepp
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Packing and covering problems
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 1 Bioinformatics
  • 1 Chemoinformatics
  • 1 Interdisciplinary applications
  • 1 Machine learning
  • 1 Statistics
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2019
  • 1 2013

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact