2 Search Results for "Schmidt genannt Waldschmidt, Daniel"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.49
Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint

Authors: Max Klimm and Martin Knaack

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
This paper studies the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop an algorithm with a robustness factor that is decreasing in the curvature c of the submodular function. For the extreme cases c = 0 corresponding to a modular objective, it matches a previously known and best possible robustness factor of 1/2. For the other extreme case of c = 1 it yields a robustness factor of ≈ 0.35 improving over the best previously known robustness factor of ≈ 0.06.
Cite as

Max Klimm and Martin Knaack. Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{klimm_et_al:LIPIcs.APPROX/RANDOM.2022.49,
  author =	{Klimm, Max and Knaack, Martin},
  title =	{{Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{49:1--49:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.49},
  URN =		{urn:nbn:de:0030-drops-171711},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.49},
  annote =	{Keywords: submodular function, knapsack, approximation algorithm, robust optimization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.79
Restricted Adaptivity in Stochastic Scheduling

Authors: Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We consider the stochastic scheduling problem of minimizing the expected makespan on m parallel identical machines. While the (adaptive) list scheduling policy achieves an approximation ratio of 2, any (non-adaptive) fixed assignment policy has performance guarantee Ω((log m)/(log log m)). Although the performance of the latter class of policies are worse, there are applications in which non-adaptive policies are desired. In this work, we introduce the two classes of δ-delay and τ-shift policies whose degree of adaptivity can be controlled by a parameter. We present a policy - belonging to both classes - which is an 𝒪(log log m)-approximation for reasonably bounded parameters. In other words, an exponential improvement on the performance of any fixed assignment policy can be achieved when allowing a small degree of adaptivity. Moreover, we provide a matching lower bound for any δ-delay and τ-shift policy when both parameters, respectively, are in the order of the expected makespan of an optimal non-anticipatory policy.
Cite as

Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt. Restricted Adaptivity in Stochastic Scheduling. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 79:1-79:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sagnol_et_al:LIPIcs.ESA.2021.79,
  author =	{Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel},
  title =	{{Restricted Adaptivity in Stochastic Scheduling}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{79:1--79:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.79},
  URN =		{urn:nbn:de:0030-drops-146603},
  doi =		{10.4230/LIPIcs.ESA.2021.79},
  annote =	{Keywords: stochastic scheduling, makespan minimzation, approximation algorithm, fixed assignment policy, non-anticipatory policy}
}
  • Refine by Author
  • 1 Klimm, Max
  • 1 Knaack, Martin
  • 1 Sagnol, Guillaume
  • 1 Schmidt genannt Waldschmidt, Daniel

  • Refine by Classification
  • 1 Mathematics of computing → Submodular optimization and polymatroids
  • 1 Theory of computation → Online algorithms
  • 1 Theory of computation → Packing and covering problems
  • 1 Theory of computation → Scheduling algorithms

  • Refine by Keyword
  • 2 approximation algorithm
  • 1 fixed assignment policy
  • 1 knapsack
  • 1 makespan minimzation
  • 1 non-anticipatory policy
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2022

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact