Search Results

Documents authored by Shachnai, Hadas

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.27
An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding

Authors: Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai

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

Abstract
In [Math. Oper. Res., 2011], Fleischer et al. introduced a powerful technique for solving the generic class of separable assignment problems (SAP), in which a set of items of given values and weights needs to be packed into a set of bins subject to separable assignment constraints, so as to maximize the total value. The approach of Fleischer at al. relies on solving a configuration LP and sampling a configuration for each bin independently based on the LP solution. While there is a SAP variant for which this approach yields the best possible approximation ratio, for various special cases, there are discrepancies between the approximation ratios obtained using the above approach and the state-of-the-art approximations. This raises the following natural question: Can we do better by iteratively solving the configuration LP and sampling a few bins at a time? To assess the potential of the iterative approach we consider a specific SAP variant as a case-study, Uniform Cardinality Constrained Multiple Knapsack, for which we answer this question affirmatively. The input is a set of items, each has a value and a weight, and a set of uniform capacity bins. The goal is to assign a subset of the items of maximum total value to the bins such that (i) the capacity of any bin is not exceeded, and (ii) the number of items assigned to each bin satisfies a given cardinality constraint. While the technique of Fleischer et al. yields a (1-1/e)-approximation for the problem, we show that iterative randomized rounding leads to efficient polynomial time approximation scheme (EPTAS), thus essentially resolving the complexity status of the problem. Our analysis of iterative randomized rounding may be useful for solving other SAP variants.
Cite as

Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{doronarad_et_al:LIPIcs.APPROX/RANDOM.2024.27,
  author =	{Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas},
  title =	{{An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.27},
  URN =		{urn:nbn:de:0030-drops-210204},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.27},
  annote =	{Keywords: multiple knapsack, cardinality constraint, EPTAS, iterative randomized rounding}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.56
Lower Bounds for Matroid Optimization Problems with a Linear Constraint

Authors: Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We study a family of matroid optimization problems with a linear constraint (MOL). In these problems, we seek a subset of elements which optimizes (i.e., maximizes or minimizes) a linear objective function subject to (i) a matroid independent set, or a matroid basis constraint, (ii) additional linear constraint. A notable member in this family is budgeted matroid independent set (BM), which can be viewed as classic 0/1-Knapsack with a matroid constraint. While special cases of BM, such as knapsack with cardinality constraint and multiple-choice knapsack, admit a fully polynomial-time approximation scheme (Fully PTAS), the best known result for BM on a general matroid is an Efficient PTAS. Prior to this work, the existence of a Fully PTAS for BM, and more generally, for any problem in the family of MOL problems, has been open. In this paper, we answer this question negatively by showing that none of the (non-trivial) problems in this family admits a Fully PTAS. This resolves the complexity status of several well studied problems. Our main result is obtained by showing first that exact weight matroid basis (EMB) does not admit a pseudo-polynomial time algorithm. This distinguishes EMB from the special cases of k-subset sum and EMB on a linear matroid, which are solvable in pseudo-polynomial time. We then obtain unconditional hardness results for the family of MOL problems in the oracle model (even if randomization is allowed), and show that the same results hold when the matroids are encoded as part of the input, assuming P ≠ NP. For the hardness proof of EMB, we introduce the Π-matroid family. This intricate subclass of matroids, which exploits the interaction between a weight function and the matroid constraint, may find use in tackling other matroid optimization problems.
Cite as

Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. Lower Bounds for Matroid Optimization Problems with a Linear Constraint. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 56:1-56:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{doronarad_et_al:LIPIcs.ICALP.2024.56,
  author =	{Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas},
  title =	{{Lower Bounds for Matroid Optimization Problems with a Linear Constraint}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{56:1--56:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.56},
  URN =		{urn:nbn:de:0030-drops-201990},
  doi =		{10.4230/LIPIcs.ICALP.2024.56},
  annote =	{Keywords: matroid optimization, budgeted problems, knapsack, approximation schemes}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.13
Budgeted Matroid Maximization: a Parameterized Viewpoint

Authors: Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
We study budgeted variants of well known maximization problems with multiple matroid constraints. Given an 𝓁-matchoid ℳ on a ground set E, a profit function p:E → ℝ_{≥ 0}, a cost function c:E → ℝ_{≥ 0}, and a budget B ∈ ℝ_{≥ 0}, the goal is to find in the 𝓁-matchoid a feasible set S of maximum profit p(S) subject to the budget constraint, i.e., c(S) ≤ B. The budgeted 𝓁-matchoid (BM) problem includes as special cases budgeted 𝓁-dimensional matching and budgeted 𝓁-matroid intersection. A strong motivation for studying BM from parameterized viewpoint comes from the APX-hardness of unbudgeted 𝓁-dimensional matching (i.e., B = ∞) already for 𝓁 = 3. Nevertheless, while there are known FPT algorithms for the unbudgeted variants of the above problems, the budgeted variants are studied here for the first time through the lens of parameterized complexity. We show that BM parametrized by solution size is W[1]-hard, already with a degenerate single matroid constraint. Thus, an exact parameterized algorithm is unlikely to exist, motivating the study of FPT-approximation schemes (FPAS). Our main result is an FPAS for BM (implying an FPAS for 𝓁-dimensional matching and budgeted 𝓁-matroid intersection), relying on the notion of representative set - a small cardinality subset of elements which preserves the optimum up to a small factor. We also give a lower bound on the minimum possible size of a representative set which can be computed in polynomial time.
Cite as

Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. Budgeted Matroid Maximization: a Parameterized Viewpoint. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{doronarad_et_al:LIPIcs.IPEC.2023.13,
  author =	{Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas},
  title =	{{Budgeted Matroid Maximization: a Parameterized Viewpoint}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.13},
  URN =		{urn:nbn:de:0030-drops-194329},
  doi =		{10.4230/LIPIcs.IPEC.2023.13},
  annote =	{Keywords: budgeted matching, budgeted matroid intersection, knapsack problems, FPT-approximation scheme}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.20
Improved Approximation for Two-Dimensional Vector Multiple Knapsack

Authors: Tomer Cohen, Ariel Kulik, and Hadas Shachnai

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
We study the uniform 2-dimensional vector multiple knapsack (2VMK) problem, a natural variant of multiple knapsack arising in real-world applications such as virtual machine placement. The input for 2VMK is a set of items, each associated with a 2-dimensional weight vector and a positive profit, along with m 2-dimensional bins of uniform (unit) capacity in each dimension. The goal is to find an assignment of a subset of the items to the bins, such that the total weight of items assigned to a single bin is at most one in each dimension, and the total profit is maximized. Our main result is a (1 - (ln 2)/2 - ε)-approximation algorithm for 2VMK, for every fixed ε > 0, thus improving the best known ratio of (1 - 1/e - ε) which follows as a special case from a result of [Fleischer at al., MOR 2011]. Our algorithm relies on an adaptation of the Round&Approx framework of [Bansal et al., SICOMP 2010], originally designed for set covering problems, to maximization problems. The algorithm uses randomized rounding of a configuration-LP solution to assign items to ≈ m⋅ln 2 ≈ 0.693⋅m of the bins, followed by a reduction to the (1-dimensional) Multiple Knapsack problem for assigning items to the remaining bins.
Cite as

Tomer Cohen, Ariel Kulik, and Hadas Shachnai. Improved Approximation for Two-Dimensional Vector Multiple Knapsack. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ISAAC.2023.20,
  author =	{Cohen, Tomer and Kulik, Ariel and Shachnai, Hadas},
  title =	{{Improved Approximation for Two-Dimensional Vector Multiple Knapsack}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.20},
  URN =		{urn:nbn:de:0030-drops-193229},
  doi =		{10.4230/LIPIcs.ISAAC.2023.20},
  annote =	{Keywords: vector multiple knapsack, two-dimensional packing, randomized rounding, approximation algorithms}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.22
An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding

Authors: Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai

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

Abstract
We consider the Bin Packing problem with a partition matroid constraint. The input is a set of items of sizes in [0,1], and a partition matroid over the items. The goal is to pack the items in a minimum number of unit-size bins, such that each bin forms an independent set in the matroid. This variant of classic Bin Packing has natural applications in secure storage on the Cloud, as well as in equitable scheduling and clustering with fairness constraints. Our main result is an asymptotic fully polynomial-time approximation scheme (AFPTAS) for Bin Packing with a partition matroid constraint. This scheme generalizes the known AFPTAS for Bin Packing with Cardinality Constraints and improves the existing asymptotic polynomial-time approximation scheme (APTAS) for Group Bin Packing, which are both special cases of Bin Packing with partition matroid. We derive the scheme via a new method for rounding a (fractional) solution for a configuration-LP. Our method uses this solution to obtain prototypes, in which items are interpreted as placeholders for other items, and applies fractional grouping to modify a fractional solution (prototype) into one having desired integrality properties.
Cite as

Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{doronarad_et_al:LIPIcs.APPROX/RANDOM.2023.22,
  author =	{Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas},
  title =	{{An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.22},
  URN =		{urn:nbn:de:0030-drops-188470},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.22},
  annote =	{Keywords: bin packing, partition-matroid, AFPTAS, LP-rounding}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.49
An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets

Authors: Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We study the budgeted versions of the well known matching and matroid intersection problems. While both problems admit a polynomial-time approximation scheme (PTAS) [Berger et al. (Math. Programming, 2011), Chekuri, Vondrák and Zenklusen (SODA 2011)], it has been an intriguing open question whether these problems admit a fully PTAS (FPTAS), or even an efficient PTAS (EPTAS). In this paper we answer the second part of this question affirmatively, by presenting an EPTAS for budgeted matching and budgeted matroid intersection. A main component of our scheme is a construction of representative sets for desired solutions, whose cardinality depends only on ε, the accuracy parameter. Thus, enumerating over solutions within a representative set leads to an EPTAS. This crucially distinguishes our algorithms from previous approaches, which rely on exhaustive enumeration over the solution set.
Cite as

Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{doronarad_et_al:LIPIcs.ICALP.2023.49,
  author =	{Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas},
  title =	{{An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.49},
  URN =		{urn:nbn:de:0030-drops-181018},
  doi =		{10.4230/LIPIcs.ICALP.2023.49},
  annote =	{Keywords: budgeted matching, budgeted matroid intersection, efficient polynomial-time approximation scheme}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.41
Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping

Authors: Yaron Fairstein, Ariel Kulik, and Hadas Shachnai

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

Abstract
A multiple knapsack constraint over a set of items is defined by a set of bins of arbitrary capacities, and a weight for each of the items. An assignment for the constraint is an allocation of subsets of items to the bins which adheres to bin capacities. In this paper we present a unified algorithm that yields efficient approximations for a wide class of submodular and modular optimization problems involving multiple knapsack constraints. One notable example is a polynomial time approximation scheme for Multiple-Choice Multiple Knapsack, improving upon the best known ratio of 2. Another example is Non-monotone Submodular Multiple Knapsack, for which we obtain a (0.385-ε)-approximation, matching the best known ratio for a single knapsack constraint. The robustness of our algorithm is achieved by applying a novel fractional variant of the classical linear grouping technique, which is of independent interest.
Cite as

Yaron Fairstein, Ariel Kulik, and Hadas Shachnai. Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fairstein_et_al:LIPIcs.ESA.2021.41,
  author =	{Fairstein, Yaron and Kulik, Ariel and Shachnai, Hadas},
  title =	{{Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{41:1--41:16},
  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.41},
  URN =		{urn:nbn:de:0030-drops-146229},
  doi =		{10.4230/LIPIcs.ESA.2021.41},
  annote =	{Keywords: Sumodular Optimization, Multiple Knapsack, Randomized Rounding, Linear Grouping, Multiple Choice Multiple 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
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.48
Maximizing Throughput in Flow Shop Real-Time Scheduling

Authors: Lior Ben Yamin, Jing Li, Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai

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

Abstract
We consider scheduling real-time jobs in the classic flow shop model. The input is a set of n jobs, each consisting of m segments to be processed on m machines in the specified order, such that segment I_i of a job can start processing on machine M_i only after segment I_{i-1} of the same job completed processing on machine M_{i-1}, for 2 ≤ i ≤ m. Each job also has a release time, a due date, and a weight. The objective is to maximize the throughput (or, profit) of the n jobs, i.e., to find a subset of the jobs that have the maximum total weight and can complete processing on the m machines within their time windows. This problem has numerous real-life applications ranging from manufacturing to cloud and embedded computing platforms, already in the special case where m = 2. Previous work in the flow shop model has focused on makespan, flow time, or tardiness objectives. However, little is known for the flow shop model in the real-time setting. In this work, we give the first nontrivial results for this problem and present a pseudo-polynomial time (2m+1)-approximation algorithm for the problem on m ≥ 2 machines, where m is a constant. This ratio is essentially tight due to a hardness result of Ω(m/(log m)) for the approximation ratio. We further give a polynomial-time algorithm for the two-machine case, with an approximation ratio of (9+ε) where ε = O(1/n). We obtain better bounds for some restricted subclasses of inputs with two machines. To the best of our knowledge, this fundamental problem of throughput maximization in the flow shop scheduling model is studied here for the first time.
Cite as

Lior Ben Yamin, Jing Li, Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai. Maximizing Throughput in Flow Shop Real-Time Scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{benyamin_et_al:LIPIcs.APPROX/RANDOM.2020.48,
  author =	{Ben Yamin, Lior and Li, Jing and Sarpatwar, Kanthi and Schieber, Baruch and Shachnai, Hadas},
  title =	{{Maximizing Throughput in Flow Shop Real-Time Scheduling}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.48},
  URN =		{urn:nbn:de:0030-drops-126510},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.48},
  annote =	{Keywords: Flow shop, real-time scheduling, throughput maximization, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.26
The Preemptive Resource Allocation Problem

Authors: Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
We revisit a classical scheduling model to incorporate modern trends in data center networks and cloud services. Addressing some key challenges in the allocation of shared resources to user requests (jobs) in such settings, we consider the following variants of the classic resource allocation problem (RAP). The input to our problems is a set J of jobs and a set M of homogeneous hosts, each has an available amount of some resource. A job is associated with a release time, a due date, a weight and a given length, as well as its resource requirement. A feasible schedule is an allocation of the resource to a subset of the jobs, satisfying the job release times/due dates as well as the resource constraints. A crucial distinction between classic RAP and our problems is that we allow preemption and migration of jobs, motivated by virtualization techniques. We consider two natural objectives: throughput maximization (MaxT), which seeks a maximum weight subset of the jobs that can be feasibly scheduled on the hosts in M, and resource minimization (MinR), that is finding the minimum number of (homogeneous) hosts needed to feasibly schedule all jobs. Both problems are known to be NP-hard. We first present an Omega(1)-approximation algorithm for MaxT instances where time-windows form a laminar family of intervals. We then extend the algorithm to handle instances with arbitrary time-windows, assuming there is sufficient slack for each job to be completed. For MinR we study a more general setting with d resources and derive an O(log d)-approximation for any fixed d >= 1, under the assumption that time-windows are not too small. This assumption can be removed leading to a slightly worse ratio of O(log d log^* T), where T is the maximum due date of any job.
Cite as

Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai. The Preemptive Resource Allocation Problem. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{sarpatwar_et_al:LIPIcs.FSTTCS.2019.26,
  author =	{Sarpatwar, Kanthi and Schieber, Baruch and Shachnai, Hadas},
  title =	{{The Preemptive Resource Allocation Problem}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.26},
  URN =		{urn:nbn:de:0030-drops-115886},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.26},
  annote =	{Keywords: Machine Scheduling, Resource Allocation, Vector Packing, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.69
Generalized Assignment via Submodular Optimization with Reserved Capacity

Authors: Ariel Kulik, Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai

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

Abstract
We study a variant of the generalized assignment problem (GAP) with group constraints. An instance of (Group GAP) is a set I of items, partitioned into L groups, and a set of m uniform (unit-sized) bins. Each item i in I has a size s_i >0, and a profit p_{i,j} >= 0 if packed in bin j. A group of items is satisfied if all of its items are packed. The goal is to find a feasible packing of a subset of the items in the bins such that the total profit from satisfied groups is maximized. We point to central applications of Group GAP in Video-on-Demand services, mobile Device-to-Device network caching and base station cooperation in 5G networks. Our main result is a 1/6-approximation algorithm for Group GAP instances where the total size of each group is at most m/2. At the heart of our algorithm lies an interesting derivation of a submodular function from the classic LP formulation of GAP, which facilitates the construction of a high profit solution utilizing at most half the total bin capacity, while the other half is reserved for later use. In particular, we give an algorithm for submodular maximization subject to a knapsack constraint, which finds a solution of profit at least 1/3 of the optimum, using at most half the knapsack capacity, under mild restrictions on element sizes. Our novel approach of submodular optimization subject to a knapsack with reserved capacity constraint may find applications in solving other group assignment problems.
Cite as

Ariel Kulik, Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai. Generalized Assignment via Submodular Optimization with Reserved Capacity. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 69:1-69:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kulik_et_al:LIPIcs.ESA.2019.69,
  author =	{Kulik, Ariel and Sarpatwar, Kanthi and Schieber, Baruch and Shachnai, Hadas},
  title =	{{Generalized Assignment via Submodular Optimization with Reserved Capacity}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{69:1--69:15},
  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.69},
  URN =		{urn:nbn:de:0030-drops-111906},
  doi =		{10.4230/LIPIcs.ESA.2019.69},
  annote =	{Keywords: Group Generalized Assignment Problem, Submodular Maximization, Knapsack Constraints, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.24
Generalized Assignment of Time-Sensitive Item Groups

Authors: Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai

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

Abstract
We study the generalized assignment problem with time-sensitive item groups (chi-AGAP). It has central applications in advertisement placement on the Internet, and in virtual network embedding in Cloud data centers. We are given a set of items, partitioned into n groups, and a set of T identical bins (or, time-slots). Each group 1 <= j <= n has a time-window chi_j = [r_j, d_j]subseteq [T] in which it can be packed. Each item i in group j has a size s_i>0 and a non-negative utility u_{it} when packed into bin t in chi_j. A bin can accommodate at most one item from each group and the total size of the items in a bin cannot exceed its capacity. The goal is to find a feasible packing of a subset of the items in the bins such that the total utility from groups that are completely packed is maximized. Our main result is an Omega(1)-approximation algorithm for chi-AGAP. Our approximation technique relies on a non-trivial rounding of a configuration LP, which can be adapted to other common scenarios of resource allocation in Cloud data centers.
Cite as

Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai. Generalized Assignment of Time-Sensitive Item Groups. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{sarpatwar_et_al:LIPIcs.APPROX-RANDOM.2018.24,
  author =	{Sarpatwar, Kanthi and Schieber, Baruch and Shachnai, Hadas},
  title =	{{Generalized Assignment of Time-Sensitive Item Groups}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.24},
  URN =		{urn:nbn:de:0030-drops-94287},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.24},
  annote =	{Keywords: Approximation Algorithms, Packing and Covering problems, Generalized Assignment problem}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.416
The Container Selection Problem

Authors: Viswanath Nagarajan, Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai, and Joel L. Wolf

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

Abstract
We introduce and study a network resource management problem that is a special case of non-metric k-median, naturally arising in cross platform scheduling and cloud computing. In the continuous d-dimensional container selection problem, we are given a set C of input points in d-dimensional Euclidean space, for some d >= 2, and a budget k. An input point p can be assigned to a "container point" c only if c dominates p in every dimension. The assignment cost is then equal to the L1-norm of the container point. The goal is to find k container points in the d-dimensional space, such that the total assignment cost for all input points is minimized. The discrete variant of the problem has one key distinction, namely, the container points must be chosen from a given set F of points. For the continuous version, we obtain a polynomial time approximation scheme for any fixed dimension d>= 2. On the negative side, we show that the problem is NP-hard for any d>=3. We further show that the discrete version is significantly harder, as it is NP-hard to approximate without violating the budget k in any dimension d>=3. Thus, we focus on obtaining bi-approximation algorithms. For d=2, the bi-approximation guarantee is (1+epsilon,3), i.e., for any epsilon>0, our scheme outputs a solution of size 3k and cost at most (1+epsilon) times the optimum. For fixed d>2, we present a (1+epsilon,O((1/epsilon)log k)) bi-approximation algorithm.
Cite as

Viswanath Nagarajan, Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai, and Joel L. Wolf. The Container Selection Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 416-434, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{nagarajan_et_al:LIPIcs.APPROX-RANDOM.2015.416,
  author =	{Nagarajan, Viswanath and Sarpatwar, Kanthi K. and Schieber, Baruch and Shachnai, Hadas and Wolf, Joel L.},
  title =	{{The Container Selection Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{416--434},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.416},
  URN =		{urn:nbn:de:0030-drops-53153},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.416},
  annote =	{Keywords: non-metric k-median, geometric hitting set, approximation algorithms, cloud computing, cross platform scheduling.}
}
Document
DOI: 10.4230/DagRep.1.2.67
Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091)

Authors: Klaus Jansen, Claire Matieu, Hadas Shachnai, and Neal E. Young

Published in: Dagstuhl Reports, Volume 1, Issue 2 (2011)

Abstract
From 27.02.2011 to 4.03.2011, the Dagstuhl Seminar 11091 ``Packing and Scheduling Algorithms for Information and Communication Services'' was held in Schloss Dagstuhl Leibniz Center for Informatics. During the seminar, several participants presented their current research, and on-going work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Klaus Jansen, Claire Matieu, Hadas Shachnai, and Neal E. Young. Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091). In Dagstuhl Reports, Volume 1, Issue 2, pp. 67-93, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{jansen_et_al:DagRep.1.2.67,
  author =	{Jansen, Klaus and Matieu, Claire and Shachnai, Hadas and Young, Neal E.},
  title =	{{Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091)}},
  pages =	{67--93},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{2},
  editor =	{Jansen, Klaus and Matieu, Claire and Shachnai, Hadas and Young, Neal E.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.2.67},
  URN =		{urn:nbn:de:0030-drops-31579},
  doi =		{10.4230/DagRep.1.2.67},
  annote =	{Keywords: Packing, scheduling, information and communication services, combinatorial optimization, mathematical programming, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2010.169
Minimizing Busy Time in Multiple Machine Real-time Scheduling

Authors: Rohit Khandekar, Baruch Schieber, Hadas Shachnai, and Tami Tamir

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Abstract
We consider the following fundamental scheduling problem. The input consists of $n$ jobs to be scheduled on a set of machines of bounded capacities. Each job is associated with a release time, a due date, a processing time and demand for machine capacity. The goal is to schedule all of the jobs non-preemptively in their release-time-deadline windows, subject to machine capacity constraints, such that the total busy time of the machines is minimized. Our problem has important applications in power-aware scheduling, optical network design and unit commitment in power systems. Scheduling to minimize busy times is APX-hard already in the special case where all jobs have the same (unit) processing times and can be scheduled in a fixed time interval. Our main result is a $5$-approximation algorithm for general instances. We extend this result to obtain an algorithm with the same approximation ratio for the problem of scheduling moldable jobs, that requires also to determine, for each job, one of several processing-time vs. demand configurations. Better bounds and exact algorithms are derived for several special cases, including proper interval graphs, intervals forming a clique and laminar families of intervals.
Cite as

Rohit Khandekar, Baruch Schieber, Hadas Shachnai, and Tami Tamir. Minimizing Busy Time in Multiple Machine Real-time Scheduling. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 169-180, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{khandekar_et_al:LIPIcs.FSTTCS.2010.169,
  author =	{Khandekar, Rohit and Schieber, Baruch and Shachnai, Hadas and Tamir, Tami},
  title =	{{Minimizing Busy Time in Multiple Machine Real-time Scheduling}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{169--180},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.169},
  URN =		{urn:nbn:de:0030-drops-28909},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.169},
  annote =	{Keywords: real-time scheduling, busy time, preemption, approximation algorithm}
}
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