13 Search Results for "Shachnai, Hadas"


Document
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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}
}
  • Refine by Author
  • 13 Shachnai, Hadas
  • 7 Kulik, Ariel
  • 6 Schieber, Baruch
  • 4 Sarpatwar, Kanthi
  • 3 Doron-Arad, Ilan
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Packing and covering problems
  • 3 Theory of computation
  • 2 Theory of computation → Scheduling algorithms
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Combinatorial optimization
  • Show More...

  • Refine by Keyword
  • 3 Approximation Algorithms
  • 3 approximation algorithms
  • 2 Multiple Knapsack
  • 2 Randomized Rounding
  • 2 Sumodular Optimization
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 4 2023
  • 2 2019
  • 2 2020
  • 1 2010
  • 1 2011
  • Show More...

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