Search Results

Documents authored by Raz, Danny

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.15
General Knapsack Problems in a Dynamic Setting

Authors: Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, and Danny Raz

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

Abstract
The world is dynamic and changes over time, thus any optimization problem used to model real life problems must address this dynamic nature, taking into account the cost of changes to a solution over time. The multistage model was introduced with this goal in mind. In this model we are given a series of instances of an optimization problem, corresponding to different times, and a solution is provided for each instance. The strive for obtaining near-optimal solutions for each instance on one hand, while maintaining similar solutions for consecutive time units on the other hand, is quantified and integrated into the objective function. In this paper we consider the Generalized Multistage d-Knapsack problem, a generalization of the multistage variants of the Multiple Knapsack problem, as well as the d-Dimensional Knapsack problem. We present a PTAS for Generalized Multistage d-Knapsack.
Cite as

Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, and Danny Raz. General Knapsack Problems in a Dynamic Setting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fairstein_et_al:LIPIcs.APPROX/RANDOM.2021.15,
  author =	{Fairstein, Yaron and Kulik, Ariel and Naor, Joseph (Seffi) and Raz, Danny},
  title =	{{General Knapsack Problems in a Dynamic Setting}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.15},
  URN =		{urn:nbn:de:0030-drops-147081},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.15},
  annote =	{Keywords: Multistage, Multiple-Knapsacks, Multidimensional Knapsack}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.44
A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem

Authors: Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, Danny Raz, and Hadas Shachnai

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint (SMKP). The input is a set I of items, each associated with a non-negative weight, and a set of bins having arbitrary capacities. Also, we are given a submodular, monotone and non-negative function f over subsets of the items. The objective is to find a subset of items A ⊆ I and a packing of these items in the bins, such that f(A) is maximized. SMKP is a natural extension of both Multiple Knapsack and the problem of monotone submodular maximization subject to a knapsack constraint. Our main result is a nearly optimal polynomial time (1-e^{-1}-ε)-approximation algorithm for the problem, for any ε > 0. Our algorithm relies on a refined analysis of techniques for constrained submodular optimization combined with sophisticated application of tools used in the development of approximation schemes for packing problems.
Cite as

Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, Danny Raz, and Hadas Shachnai. A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fairstein_et_al:LIPIcs.ESA.2020.44,
  author =	{Fairstein, Yaron and Kulik, Ariel and Naor, Joseph (Seffi) and Raz, Danny and Shachnai, Hadas},
  title =	{{A (1-e^\{-1\}-\epsilon)-Approximation for the Monotone Submodular Multiple Knapsack Problem}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.44},
  URN =		{urn:nbn:de:0030-drops-129107},
  doi =		{10.4230/LIPIcs.ESA.2020.44},
  annote =	{Keywords: Sumodular Optimization, Multiple Knapsack, Randomized Rounding}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.10
Online Multidimensional Packing Problems in the Random-Order Model

Authors: David Naori and Danny Raz

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We study online multidimensional variants of the generalized assignment problem which are used to model prominent real-world applications, such as the assignment of virtual machines with multiple resource requirements to physical infrastructure in cloud computing. These problems can be seen as an extension of the well known secretary problem and thus the standard online worst-case model cannot provide any performance guarantee. The prevailing model in this case is the random-order model, which provides a useful realistic and robust alternative. Using this model, we study the d-dimensional generalized assignment problem, where we introduce a novel technique that achieves an O(d)-competitive algorithms and prove a matching lower bound of Omega(d). Furthermore, our algorithm improves upon the best-known competitive-ratio for the online (one-dimensional) generalized assignment problem and the online knapsack problem.
Cite as

David Naori and Danny Raz. Online Multidimensional Packing Problems in the Random-Order Model. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{naori_et_al:LIPIcs.ISAAC.2019.10,
  author =	{Naori, David and Raz, Danny},
  title =	{{Online Multidimensional Packing Problems in the Random-Order Model}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.10},
  URN =		{urn:nbn:de:0030-drops-115067},
  doi =		{10.4230/LIPIcs.ISAAC.2019.10},
  annote =	{Keywords: Random Order, Generalized Assignment Problem, Knapsack Problem, Multidimensional Packing, Secretary Problem}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.72
A Relaxed FPTAS for Chance-Constrained Knapsack

Authors: Galia Shabtai, Danny Raz, and Yuval Shavitt

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
The stochastic knapsack problem is a stochastic version of the well known deterministic knapsack problem, in which some of the input values are random variables. There are several variants of the stochastic problem. In this paper we concentrate on the chance-constrained variant, where item values are deterministic and item sizes are stochastic. The goal is to find a maximum value allocation subject to the constraint that the overflow probability is at most a given value. Previous work showed a PTAS for the problem for various distributions (Poisson, Exponential, Bernoulli and Normal). Some strictly respect the constraint and some relax the constraint by a factor of (1+epsilon). All algorithms use Omega(n^{1/epsilon}) time. A very recent work showed a "almost FPTAS" algorithm for Bernoulli distributions with O(poly(n) * quasipoly(1/epsilon)) time. In this paper we present a FPTAS for normal distributions with a solution that satisfies the chance constraint in a relaxed sense. The normal distribution is particularly important, because by the Berry-Esseen theorem, an algorithm solving the normal distribution also solves, under mild conditions, arbitrary independent distributions. To the best of our knowledge, this is the first (relaxed or non-relaxed) FPTAS for the problem. In fact, our algorithm runs in poly(n/epsilon) time. We achieve the FPTAS by a delicate combination of previous techniques plus a new alternative solution to the non-heavy elements that is based on a non-convex program with a simple structure and an O(n^2 log {n/epsilon}) running time. We believe this part is also interesting on its own right.
Cite as

Galia Shabtai, Danny Raz, and Yuval Shavitt. A Relaxed FPTAS for Chance-Constrained Knapsack. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 72:1-72:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{shabtai_et_al:LIPIcs.ISAAC.2018.72,
  author =	{Shabtai, Galia and Raz, Danny and Shavitt, Yuval},
  title =	{{A Relaxed FPTAS for Chance-Constrained Knapsack}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{72:1--72:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.72},
  URN =		{urn:nbn:de:0030-drops-100201},
  doi =		{10.4230/LIPIcs.ISAAC.2018.72},
  annote =	{Keywords: Stochastic knapsack, Chance constraint, Approximation algorithms, Combinatorial optimization}
}
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 About DROPS Imprint Privacy Contact