12 Search Results for "Kulik, Ariel"

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-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
DOI: 10.4230/LIPIcs.IPEC.2023.17
Approximate Monotone Local Search for Weighted Problems

Authors: Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma

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

Abstract
In a recent work, Esmer et al. describe a simple method - Approximate Monotone Local Search - to obtain exponential approximation algorithms from existing parameterized exact algorithms, polynomial-time approximation algorithms and, more generally, parameterized approximation algorithms. In this work, we generalize those results to the weighted setting. More formally, we consider monotone subset minimization problems over a weighted universe of size n (e.g., Vertex Cover, d-Hitting Set and Feedback Vertex Set). We consider a model where the algorithm is only given access to a subroutine that finds a solution of weight at most α ⋅ W (and of arbitrary cardinality) in time c^k ⋅ n^{𝒪(1)} where W is the minimum weight of a solution of cardinality at most k. In the unweighted setting, Esmer et al. determine the smallest value d for which a β-approximation algorithm running in time dⁿ ⋅ n^{𝒪(1)} can be obtained in this model. We show that the same dependencies also hold in a weighted setting in this model: for every fixed ε > 0 we obtain a β-approximation algorithm running in time 𝒪((d+ε)ⁿ), for the same d as in the unweighted setting. Similarly, we also extend a β-approximate brute-force search (in a model which only provides access to a membership oracle) to the weighted setting. Using existing approximation algorithms and exact parameterized algorithms for weighted problems, we obtain the first exponential-time β-approximation algorithms that are better than brute force for a variety of problems including Weighted Vertex Cover, Weighted d-Hitting Set, Weighted Feedback Vertex Set and Weighted Multicut.
Cite as

Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma. Approximate Monotone Local Search for Weighted Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{esmer_et_al:LIPIcs.IPEC.2023.17,
  author =	{Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Neuen, Daniel and Sharma, Roohani},
  title =	{{Approximate Monotone Local Search for Weighted Problems}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{17:1--17:23},
  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.17},
  URN =		{urn:nbn:de:0030-drops-194360},
  doi =		{10.4230/LIPIcs.IPEC.2023.17},
  annote =	{Keywords: parameterized approximations, exponential approximations, monotone local search}
}
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-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
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-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
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-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
DOI: 10.4230/LIPIcs.IPEC.2022.12
Computing Generalized Convolutions Faster Than Brute Force

Authors: Barış Can Esmer, Ariel Kulik, Dániel Marx, Philipp Schepper, and Karol Węgrzycki

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
In this paper, we consider a general notion of convolution. Let D be a finite domain and let Dⁿ be the set of n-length vectors (tuples) of D. Let f : D × D → D be a function and let ⊕_f be a coordinate-wise application of f. The f-Convolution of two functions g,h : Dⁿ → {-M,…,M} is (g ⊛_f h)(v) := ∑_{v_g,v_h ∈ D^n s.t. v = v_g ⊕_f v_h} g(v_g) ⋅ h(v_h) for every 𝐯 ∈ Dⁿ. This problem generalizes many fundamental convolutions such as Subset Convolution, XOR Product, Covering Product or Packing Product, etc. For arbitrary function f and domain D we can compute f-Convolution via brute-force enumeration in 𝒪̃(|D|^{2n} ⋅ polylog(M)) time. Our main result is an improvement over this naive algorithm. We show that f-Convolution can be computed exactly in 𝒪̃((c ⋅ |D|²)ⁿ ⋅ polylog(M)) for constant c := 5/6 when D has even cardinality. Our main observation is that a cyclic partition of a function f : D × D → D can be used to speed up the computation of f-Convolution, and we show that an appropriate cyclic partition exists for every f. Furthermore, we demonstrate that a single entry of the f-Convolution can be computed more efficiently. In this variant, we are given two functions g,h : Dⁿ → {-M,…,M} alongside with a vector 𝐯 ∈ Dⁿ and the task of the f-Query problem is to compute integer (g ⊛_f h)(𝐯). This is a generalization of the well-known Orthogonal Vectors problem. We show that f-Query can be computed in 𝒪̃(|D|^{(ω/2)n} ⋅ polylog(M)) time, where ω ∈ [2,2.373) is the exponent of currently fastest matrix multiplication algorithm.
Cite as

Barış Can Esmer, Ariel Kulik, Dániel Marx, Philipp Schepper, and Karol Węgrzycki. Computing Generalized Convolutions Faster Than Brute Force. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{esmer_et_al:LIPIcs.IPEC.2022.12,
  author =	{Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Schepper, Philipp and W\k{e}grzycki, Karol},
  title =	{{Computing Generalized Convolutions Faster Than Brute Force}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.12},
  URN =		{urn:nbn:de:0030-drops-173685},
  doi =		{10.4230/LIPIcs.IPEC.2022.12},
  annote =	{Keywords: Generalized Convolution, Fast Fourier Transform, Fast Subset Convolution}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.50
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search

Authors: Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J.ACM 2019], by establishing a connection between parameterized approximation and exponential-time approximation algorithms for monotone subset minimization problems. In a monotone subset minimization problem the input implicitly describes a non-empty set family over a universe of size n which is closed under taking supersets. The task is to find a minimum cardinality set in this family. Broadly speaking, we use approximate monotone local search to show that a parameterized α-approximation algorithm that runs in c^k⋅n^𝒪(1) time, where k is the solution size, can be used to derive an α-approximation randomized algorithm that runs in dⁿ⋅n^𝒪(1) time, where d is the unique value in (1, 1+{c-1}/α) such that 𝒟(1/α‖{d-1}/{c-1}) = {ln c}/α and 𝒟(a‖b) is the Kullback-Leibler divergence. This running time matches that of Fomin et al. for α = 1, and is strictly better when α > 1, for any c > 1. Furthermore, we also show that this result can be derandomized at the expense of a sub-exponential multiplicative factor in the running time. We use an approximate variant of the exhaustive search as a benchmark for our algorithm. We show that the classic 2ⁿ⋅n^𝒪(1) exhaustive search can be adapted to an α-approximate exhaustive search that runs in time (1+exp(-α⋅ℋ(1/(α))))ⁿ⋅n^𝒪(1), where ℋ is the entropy function. Furthermore, we provide a lower bound stating that the running time of this α-approximate exhaustive search is the best achievable running time in an oracle model. When compared to approximate exhaustive search, and to other techniques, the running times obtained by approximate monotone local search are strictly better for any α ≥ 1, c > 1. We demonstrate the potential of approximate monotone local search by deriving new and faster exponential approximation algorithms for Vertex Cover, 3-Hitting Set, Directed Feedback Vertex Set, Directed Subset Feedback Vertex Set, Directed Odd Cycle Transversal and Undirected Multicut. For instance, we get a 1.1-approximation algorithm for Vertex Cover with running time 1.114ⁿ⋅n^𝒪(1), improving upon the previously best known 1.1-approximation running in time 1.127ⁿ⋅n^𝒪(1) by Bourgeois et al. [DAM 2011].
Cite as

Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma. Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{esmer_et_al:LIPIcs.ESA.2022.50,
  author =	{Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Neuen, Daniel and Sharma, Roohani},
  title =	{{Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{50:1--50:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.50},
  URN =		{urn:nbn:de:0030-drops-169887},
  doi =		{10.4230/LIPIcs.ESA.2022.50},
  annote =	{Keywords: parameterized approximations, exponential approximations, monotone local search}
}
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-dev.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.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-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
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-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
DOI: 10.4230/LIPIcs.DISC.2019.6
Parameterized Distributed Algorithms

Authors: Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
In this work, we initiate a thorough study of graph optimization problems parameterized by the output size in the distributed setting. In such a problem, an algorithm decides whether a solution of size bounded by k exists and if so, it finds one. We study fundamental problems, including Minimum Vertex Cover (MVC), Maximum Independent Set (MaxIS), Maximum Matching (MaxM), and many others, in both the LOCAL and CONGEST distributed computation models. We present lower bounds for the round complexity of solving parameterized problems in both models, together with optimal and near-optimal upper bounds. Our results extend beyond the scope of parameterized problems. We show that any LOCAL (1+epsilon)-approximation algorithm for the above problems must take Omega(epsilon^{-1}) rounds. Joined with the (epsilon^{-1}log n)^{O(1)} rounds algorithm of [Ghaffari et al., 2017] and the Omega (sqrt{(log n)/(log log n)}) lower bound of [Fabian Kuhn et al., 2016], the lower bounds match the upper bound up to polynomial factors in both parameters. We also show that our parameterized approach reduces the runtime of exact and approximate CONGEST algorithms for MVC and MaxM if the optimal solution is small, without knowing its size beforehand. Finally, we propose the first o(n^2) rounds CONGEST algorithms that approximate MVC within a factor strictly smaller than 2.
Cite as

Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Parameterized Distributed Algorithms. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.DISC.2019.6,
  author =	{Ben-Basat, Ran and Kawarabayashi, Ken-ichi and Schwartzman, Gregory},
  title =	{{Parameterized Distributed Algorithms}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.6},
  URN =		{urn:nbn:de:0030-drops-113135},
  doi =		{10.4230/LIPIcs.DISC.2019.6},
  annote =	{Keywords: Distributed Algorithms, Approximation Algorithms, Parameterized 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-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}
}
  • Refine by Author
  • 11 Kulik, Ariel
  • 7 Shachnai, Hadas
  • 3 Doron-Arad, Ilan
  • 3 Esmer, Barış Can
  • 3 Fairstein, Yaron
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Packing and covering problems
  • 3 Mathematics of computing → Approximation algorithms
  • 3 Theory of computation
  • 2 Theory of computation → Approximation algorithms analysis
  • 1 Mathematics of computing → Linear programming
  • Show More...

  • Refine by Keyword
  • 2 Approximation Algorithms
  • 2 Multiple Knapsack
  • 2 Randomized Rounding
  • 2 Sumodular Optimization
  • 2 budgeted matching
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 5 2023
  • 2 2019
  • 2 2021
  • 2 2022
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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