DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.15

List Update with Delays or Time Windows

Authors: Yossi Azar, Shahar Lewkowicz, and Danny Vainstein

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

Abstract

We address the problem of List Update, which is considered one of the fundamental problems in online algorithms and competitive analysis. In this context, we are presented with a list of elements and receive requests for these elements over time. Our objective is to fulfill these requests, incurring a cost proportional to their position in the list. Additionally, we can swap any two consecutive elements at a cost of 1. The renowned "Move to Front" algorithm, introduced by Sleator and Tarjan, immediately moves any requested element to the front of the list. They demonstrated that this algorithm achieves a competitive ratio of 2. While this bound is impressive, the actual cost of the algorithm’s solution can be excessively high. For example, if we request the last half of the list, the resulting solution cost becomes quadratic in the list’s length. To address this issue, we consider a more generalized problem called List Update with Time Windows. In this variant, each request arrives with a specific deadline by which it must be served, rather than being served immediately. Moreover, we allow the algorithm to process multiple requests simultaneously, accessing the corresponding elements in a single pass. The cost incurred in this case is determined by the position of the furthest element accessed, leading to a significant reduction in the total solution cost. We introduce this problem to explore lower solution costs, but it necessitates the development of new algorithms. For instance, Move-to-Front fails when handling the simple scenario of requesting the last half of the list with overlapping time windows. In our work, we present a natural O(1) competitive algorithm for this problem. While the algorithm itself is intuitive, its analysis is intricate, requiring the use of a novel potential function. Additionally, we delve into a more general problem called List Update with Delays, where the fixed deadlines are replaced with arbitrary delay functions. In this case, the cost includes not only the access and swapping costs, but also penalties for the delays incurred until the requests are served. This problem encompasses a special case known as the prize collecting version, where a request may go unserved up to a given deadline, resulting in a specified penalty. For this more comprehensive problem, we establish an O(1) competitive algorithm. However, the algorithm for the delay version is more complex, and its analysis involves significantly more intricate considerations.

Cite as

Yossi Azar, Shahar Lewkowicz, and Danny Vainstein. List Update with Delays or Time Windows. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.ICALP.2024.15,
  author =	{Azar, Yossi and Lewkowicz, Shahar and Vainstein, Danny},
  title =	{{List Update with Delays or Time Windows}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{15:1--15: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.15},
  URN =		{urn:nbn:de:0030-drops-201583},
  doi =		{10.4230/LIPIcs.ICALP.2024.15},
  annote =	{Keywords: Online, List Update, Delay, Time Window, Deadline}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.100

Subquadratic Submodular Maximization with a General Matroid Constraint

Authors: Yusuke Kobayashi and Tatsuya Terao

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

Abstract

We consider fast algorithms for monotone submodular maximization with a general matroid constraint. We present a randomized (1 - 1/e - ε)-approximation algorithm that requires Õ_{ε}(√r n) independence oracle and value oracle queries, where n is the number of elements in the matroid and r ≤ n is the rank of the matroid. This improves upon the previously best algorithm by Buchbinder-Feldman-Schwartz [Mathematics of Operations Research 2017] that requires Õ_{ε}(r² + √rn) queries. Our algorithm is based on continuous relaxation, as with other submodular maximization algorithms in the literature. To achieve subquadratic query complexity, we develop a new rounding algorithm, which is our main technical contribution. The rounding algorithm takes as input a point represented as a convex combination of t bases of a matroid and rounds it to an integral solution. Our rounding algorithm requires Õ(r^{3/2} t) independence oracle queries, while the previously best rounding algorithm by Chekuri-Vondrák-Zenklusen [FOCS 2010] requires O(r² t) independence oracle queries. A key idea in our rounding algorithm is to use a directed cycle of arbitrary length in an auxiliary graph, while the algorithm of Chekuri-Vondrák-Zenklusen focused on directed cycles of length two.

Cite as

Yusuke Kobayashi and Tatsuya Terao. Subquadratic Submodular Maximization with a General Matroid Constraint. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 100:1-100:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ICALP.2024.100,
  author =	{Kobayashi, Yusuke and Terao, Tatsuya},
  title =	{{Subquadratic Submodular Maximization with a General Matroid Constraint}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{100:1--100:19},
  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.100},
  URN =		{urn:nbn:de:0030-drops-202437},
  doi =		{10.4230/LIPIcs.ICALP.2024.100},
  annote =	{Keywords: submodular maximization, matroid constraint, approximation algorithm, rounding algorithm, query complexity}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.115

On the Cut-Query Complexity of Approximating Max-Cut

Authors: Orestis Plevrakis, Seyoon Ragavan, and S. Matthew Weinberg

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

Abstract

We consider the problem of query-efficient global max-cut on a weighted undirected graph in the value oracle model examined by [Rubinstein et al., 2018]. Graph algorithms in this cut query model and other query models have recently been studied for various other problems such as min-cut, connectivity, bipartiteness, and triangle detection. Max-cut in the cut query model can also be viewed as a natural special case of submodular function maximization: on query S ⊆ V, the oracle returns the total weight of the cut between S and V\S. Our first main technical result is a lower bound stating that a deterministic algorithm achieving a c-approximation for any c > 1/2 requires Ω(n) queries. This uses an extension of the cut dimension to rule out approximation (prior work of [Graur et al., 2020] introducing the cut dimension only rules out exact solutions). Secondly, we provide a randomized algorithm with Õ(n) queries that finds a c-approximation for any c < 1. We achieve this using a query-efficient sparsifier for undirected weighted graphs (prior work of [Rubinstein et al., 2018] holds only for unweighted graphs). To complement these results, for most constants c ∈ (0,1], we nail down the query complexity of achieving a c-approximation, for both deterministic and randomized algorithms (up to logarithmic factors). Analogously to general submodular function maximization in the same model, we observe a phase transition at c = 1/2: we design a deterministic algorithm for global c-approximate max-cut in O(log n) queries for any c < 1/2, and show that any randomized algorithm requires Ω(n/log n) queries to find a c-approximate max-cut for any c > 1/2. Additionally, we show that any deterministic algorithm requires Ω(n²) queries to find an exact max-cut (enough to learn the entire graph).

Cite as

Orestis Plevrakis, Seyoon Ragavan, and S. Matthew Weinberg. On the Cut-Query Complexity of Approximating Max-Cut. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 115:1-115:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{plevrakis_et_al:LIPIcs.ICALP.2024.115,
  author =	{Plevrakis, Orestis and Ragavan, Seyoon and Weinberg, S. Matthew},
  title =	{{On the Cut-Query Complexity of Approximating Max-Cut}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{115:1--115: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.115},
  URN =		{urn:nbn:de:0030-drops-202587},
  doi =		{10.4230/LIPIcs.ICALP.2024.115},
  annote =	{Keywords: query complexity, maximum cut, approximation algorithms, graph sparsification}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2023.95

An Improved Lower Bound for Matroid Intersection Prophet Inequalities

Authors: Raghuvansh R. Saxena, Santhoshini Velusamy, and S. Matthew Weinberg

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract

We consider prophet inequalities subject to feasibility constraints that are the intersection of q matroids. The best-known algorithms achieve a Θ(q)-approximation, even when restricted to instances that are the intersection of q partition matroids, and with i.i.d. Bernoulli random variables [José R. Correa et al., 2022; Moran Feldman et al., 2016; Marek Adamczyk and Michal Wlodarczyk, 2018]. The previous best-known lower bound is Θ(√q) due to a simple construction of [Robert Kleinberg and S. Matthew Weinberg, 2012] (which uses i.i.d. Bernoulli random variables, and writes the construction as the intersection of partition matroids). We establish an improved lower bound of q^{1/2+Ω(1/log log q)} by writing the construction of [Robert Kleinberg and S. Matthew Weinberg, 2012] as the intersection of asymptotically fewer partition matroids. We accomplish this via an improved upper bound on the product dimension of a graph with p^p disjoint cliques of size p, using recent techniques developed in [Noga Alon and Ryan Alweiss, 2020].

Cite as

Raghuvansh R. Saxena, Santhoshini Velusamy, and S. Matthew Weinberg. An Improved Lower Bound for Matroid Intersection Prophet Inequalities. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{saxena_et_al:LIPIcs.ITCS.2023.95,
  author =	{Saxena, Raghuvansh R. and Velusamy, Santhoshini and Weinberg, S. Matthew},
  title =	{{An Improved Lower Bound for Matroid Intersection Prophet Inequalities}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{95:1--95:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.95},
  URN =		{urn:nbn:de:0030-drops-175986},
  doi =		{10.4230/LIPIcs.ITCS.2023.95},
  annote =	{Keywords: Prophet Inequalities, Intersection of Matroids}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.41

On Maximizing Sums of Non-Monotone Submodular and Linear Functions

Authors: Benjamin Qi

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract

We study the problem of Regularized Unconstrained Submodular Maximization (RegularizedUSM) as defined by [Bodek and Feldman '22]. In this problem, we are given query access to a non-negative submodular function f: 2^N → ℝ_{≥ 0} and a linear function 𝓁: 2^N → ℝ over the same ground set N, and the objective is to output a set T ⊆ N approximately maximizing the sum f(T)+𝓁(T). Specifically, an algorithm is said to provide an (α,β)-approximation for RegularizedUSM if it outputs a set T such that E[f(T)+𝓁(T)] ≥ max_{S ⊆ N}[α ⋅ f(S)+β⋅ 𝓁(S)]. We also study the setting where S and T are constrained to be independent in a given matroid, which we refer to as Regularized Constrained Submodular Maximization (RegularizedCSM). The special case of RegularizedCSM with monotone f has been extensively studied [Sviridenko et al. '17, Feldman '18, Harshaw et al. '19]. On the other hand, we are aware of only one prior work that studies RegularizedCSM with non-monotone f [Lu et al. '21], and that work constrains 𝓁 to be non-positive. In this work, we provide improved (α,β)-approximation algorithms for both {RegularizedUSM} and {RegularizedCSM} with non-monotone f. In particular, we are the first to provide nontrivial (α,β)-approximations for RegularizedCSM where the sign of 𝓁 is unconstrained, and the α we obtain for RegularizedUSM improves over [Bodek and Feldman '22] for all β ∈ (0,1). In addition to approximation algorithms, we provide improved inapproximability results for all of the aforementioned cases. In particular, we show that the α our algorithm obtains for {RegularizedCSM} with unconstrained 𝓁 is essentially tight for β ≥ e/(e+1). Using similar ideas, we are also able to show 0.478-inapproximability for maximizing a submodular function where S and T are subject to a cardinality constraint, improving a 0.491-inapproximability result due to [Oveis Gharan and Vondrak '10].

Cite as

Benjamin Qi. On Maximizing Sums of Non-Monotone Submodular and Linear Functions. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{qi:LIPIcs.ISAAC.2022.41,
  author =	{Qi, Benjamin},
  title =	{{On Maximizing Sums of Non-Monotone Submodular and Linear Functions}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.41},
  URN =		{urn:nbn:de:0030-drops-173263},
  doi =		{10.4230/LIPIcs.ISAAC.2022.41},
  annote =	{Keywords: submodular maximization, regularization, continuous greedy, inapproximability}
}

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.33

Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model

Authors: Moran Feldman and Ariel Szarf

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

Abstract

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1/2-approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively. Unfortunately, a recent work [Christian Konrad and Kheeran K. Naidu, 2021] shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1/2-approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms are currently known (to the best of our knowledge), and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs (the result for three passes improves over the previous state-of-the-art, but is worse than the result of this paper mentioned in the previous paragraph for general graphs). The improvements obtained by these results are, unfortunately, numerically not very impressive, but the main importance (in our opinion) of these results is in demonstrating the potential of non-maximal-matching-first algorithms.

Cite as

Moran Feldman and Ariel Szarf. Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 33:1-33:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.APPROX/RANDOM.2022.33,
  author =	{Feldman, Moran and Szarf, Ariel},
  title =	{{Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{33:1--33:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.33},
  URN =		{urn:nbn:de:0030-drops-171559},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.33},
  annote =	{Keywords: Maximum matching, semi-streaming algorithms, multi-pass algorithms}
}

Document

DOI: 10.4230/LIPIcs.ESA.2022.23

Maximizing Sums of Non-Monotone Submodular and Linear Functions: Understanding the Unconstrained Case

Authors: Kobi Bodek and Moran Feldman

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

Abstract

Motivated by practical applications, recent works have considered maximization of sums of a submodular function g and a linear function 𝓁. Almost all such works, to date, studied only the special case of this problem in which g is also guaranteed to be monotone. Therefore, in this paper we systematically study the simplest version of this problem in which g is allowed to be non-monotone, namely the unconstrained variant, which we term Regularized Unconstrained Submodular Maximization (RegularizedUSM). Our main algorithmic result is the first non-trivial guarantee for general RegularizedUSM. For the special case of RegularizedUSM in which the linear function 𝓁 is non-positive, we prove two inapproximability results, showing that the algorithmic result implied for this case by previous works is not far from optimal. Finally, we reanalyze the known Double Greedy algorithm to obtain improved guarantees for the special case of RegularizedUSM in which the linear function 𝓁 is non-negative; and we complement these guarantees by showing that it is not possible to obtain (1/2, 1)-approximation for this case (despite intuitive arguments suggesting that this approximation guarantee is natural).

Cite as

Kobi Bodek and Moran Feldman. Maximizing Sums of Non-Monotone Submodular and Linear Functions: Understanding the Unconstrained Case. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bodek_et_al:LIPIcs.ESA.2022.23,
  author =	{Bodek, Kobi and Feldman, Moran},
  title =	{{Maximizing Sums of Non-Monotone Submodular and Linear Functions: Understanding the Unconstrained Case}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{23:1--23:17},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.23},
  URN =		{urn:nbn:de:0030-drops-169618},
  doi =		{10.4230/LIPIcs.ESA.2022.23},
  annote =	{Keywords: Unconstrained submodular maximization, regularization, double greedy, non-oblivious local search, inapproximability}
}

Document

DOI: 10.4230/LIPIcs.ESA.2022.52

Submodular Maximization Subject to Matroid Intersection on the Fly

Authors: Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen

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

Abstract

Despite a surge of interest in submodular maximization in the data stream model, there remain significant gaps in our knowledge about what can be achieved in this setting, especially when dealing with multiple constraints. In this work, we nearly close several basic gaps in submodular maximization subject to k matroid constraints in the data stream model. We present a new hardness result showing that super polynomial memory in k is needed to obtain an o(k/(log k))-approximation. This implies near optimality of prior algorithms. For the same setting, we show that one can nevertheless obtain a constant-factor approximation by maintaining a set of elements whose size is independent of the stream size. Finally, for bipartite matching constraints, a well-known special case of matroid intersection, we present a new technique to obtain hardness bounds that are significantly stronger than those obtained with prior approaches. Prior results left it open whether a 2-approximation may exist in this setting, and only a complexity-theoretic hardness of 1.91 was known. We prove an unconditional hardness of 2.69.

Cite as

Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. Submodular Maximization Subject to Matroid Intersection on the Fly. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.ESA.2022.52,
  author =	{Feldman, Moran and Norouzi-Fard, Ashkan and Svensson, Ola and Zenklusen, Rico},
  title =	{{Submodular Maximization Subject to Matroid Intersection on the Fly}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{52:1--52:14},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.52},
  URN =		{urn:nbn:de:0030-drops-169902},
  doi =		{10.4230/LIPIcs.ESA.2022.52},
  annote =	{Keywords: Submodular Maximization, Matroid Intersection, Streaming Algorithms}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2022.59

Streaming Submodular Maximization Under Matroid Constraints

Authors: Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract

Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniques fail to give a similar understanding for natural generalizations, including matroid constraints. This paper aims at closing this gap. For a single matroid of rank k (i.e., any solution has cardinality at most k), our main results are: - A single-pass streaming algorithm that uses Õ(k) memory and achieves an approximation guarantee of 0.3178. - A multi-pass streaming algorithm that uses Õ(k) memory and achieves an approximation guarantee of (1-1/e - ε) by taking a constant (depending on ε) number of passes over the stream. This improves on the previously best approximation guarantees of 1/4 and 1/2 for single-pass and multi-pass streaming algorithms, respectively. In fact, our multi-pass streaming algorithm is tight in that any algorithm with a better guarantee than 1/2 must make several passes through the stream and any algorithm that beats our guarantee of 1-1/e must make linearly many passes (as well as an exponential number of value oracle queries). Moreover, we show how the approach we use for multi-pass streaming can be further strengthened if the elements of the stream arrive in uniformly random order, implying an improved result for p-matchoid constraints.

Cite as

Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. Streaming Submodular Maximization Under Matroid Constraints. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 59:1-59:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.ICALP.2022.59,
  author =	{Feldman, Moran and Liu, Paul and Norouzi-Fard, Ashkan and Svensson, Ola and Zenklusen, Rico},
  title =	{{Streaming Submodular Maximization Under Matroid Constraints}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{59:1--59:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.59},
  URN =		{urn:nbn:de:0030-drops-164007},
  doi =		{10.4230/LIPIcs.ICALP.2022.59},
  annote =	{Keywords: Submodular maximization, streaming, matroid, random order}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2020.6

Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints

Authors: Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract

We study the problem of maximizing a non-monotone submodular function subject to a cardinality constraint in the streaming model. Our main contributions are two single-pass (semi-)streaming algorithms that use Õ(k)⋅poly(1/ε) memory, where k is the size constraint. At the end of the stream, both our algorithms post-process their data structures using any offline algorithm for submodular maximization, and obtain a solution whose approximation guarantee is α/(1+α)-ε, where α is the approximation of the offline algorithm. If we use an exact (exponential time) post-processing algorithm, this leads to 1/2-ε approximation (which is nearly optimal). If we post-process with the algorithm of [Niv Buchbinder and Moran Feldman, 2019], that achieves the state-of-the-art offline approximation guarantee of α = 0.385, we obtain 0.2779-approximation in polynomial time, improving over the previously best polynomial-time approximation of 0.1715 due to [Feldman et al., 2018]. One of our algorithms is combinatorial and enjoys fast update and overall running times. Our other algorithm is based on the multilinear extension, enjoys an improved space complexity, and can be made deterministic in some settings of interest.

Cite as

Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh. Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alaluf_et_al:LIPIcs.ICALP.2020.6,
  author =	{Alaluf, Naor and Ene, Alina and Feldman, Moran and Nguyen, Huy L. and Suh, Andrew},
  title =	{{Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.6},
  URN =		{urn:nbn:de:0030-drops-124137},
  doi =		{10.4230/LIPIcs.ICALP.2020.6},
  annote =	{Keywords: Submodular maximization, streaming algorithms, cardinality constraint}
}

Document

DOI: 10.4230/LIPIcs.ESA.2018.57

Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities

Authors: Euiwoong Lee and Sahil Singla

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract

Online contention resolution schemes (OCRSs) were proposed by Feldman, Svensson, and Zenklusen [Moran Feldman et al., 2016] as a generic technique to round a fractional solution in the matroid polytope in an online fashion. It has found applications in several stochastic combinatorial problems where there is a commitment constraint: on seeing the value of a stochastic element, the algorithm has to immediately and irrevocably decide whether to select it while always maintaining an independent set in the matroid. Although OCRSs immediately lead to prophet inequalities, these prophet inequalities are not optimal. Can we instead use prophet inequalities to design optimal OCRSs? We design the first optimal 1/2-OCRS for matroids by reducing the problem to designing a matroid prophet inequality where we compare to the stronger benchmark of an ex-ante relaxation. We also introduce and design optimal (1-1/e)-random order CRSs for matroids, which are similar to OCRSs but the arrival order is chosen uniformly at random.

Cite as

Euiwoong Lee and Sahil Singla. Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.ESA.2018.57,
  author =	{Lee, Euiwoong and Singla, Sahil},
  title =	{{Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{57:1--57:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.57},
  URN =		{urn:nbn:de:0030-drops-95208},
  doi =		{10.4230/LIPIcs.ESA.2018.57},
  annote =	{Keywords: Prophets, Contention Resolution, Stochastic Optimization, Matroids}
}

Document

DOI: 10.4230/LIPIcs.ESA.2016.41

Distributed Signaling Games

Authors: Moran Feldman, Moshe Tennenholtz, and Omri Weinstein

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract

The study of the algorithmic and computational complexity of designing efficient signaling schemes for mechanisms aiming to optimize social welfare or revenue is a recurring theme in recent computer science literature. In reality, however, information is typically not held by a central authority, but is distributed among multiple sources (third-party "mediators"), a fact that dramatically changes the strategic and combinatorial nature of the signaling problem. In this paper we introduce distributed signaling games, while using display advertising as a canonical example for introducing this foundational framework. A distributed signaling game may be a pure coordination game (i.e., a distributed optimization task), or a non-cooperative game. In the context of pure coordination games, we show a wide gap between the computational complexity of the centralized and distributed signaling problems, proving that distributed coordination on revenue-optimal signaling is a much harder problem than its "centralized" counterpart. In the context of non-cooperative games, the outcome generated by the mediators' signals may have different value to each. The reason for that is typically the desire of the auctioneer to align the incentives of the mediators with his own by a compensation relative to the marginal benefit from their signals. We design a mechanism for this problem via a novel application of Shapley's value, and show that it possesses a few interesting economical properties.

Cite as

Moran Feldman, Moshe Tennenholtz, and Omri Weinstein. Distributed Signaling Games. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.ESA.2016.41,
  author =	{Feldman, Moran and Tennenholtz, Moshe and Weinstein, Omri},
  title =	{{Distributed Signaling Games}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.41},
  URN =		{urn:nbn:de:0030-drops-63536},
  doi =		{10.4230/LIPIcs.ESA.2016.41},
  annote =	{Keywords: Signaling, display advertising, mechanism design, shapley value}
}

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.160

Constrained Monotone Function Maximization and the Supermodular Degree

Authors: Moran Feldman and Rani Izsak

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

Abstract

The problem of maximizing a constrained monotone set function has many practical applications and generalizes many combinatorial problems such as k-Coverage, Max-SAT, Set Packing, Maximum Independent Set and Welfare Maximization. Unfortunately, it is generally not possible to maximize a monotone set function up to an acceptable approximation ratio, even subject to simple constraints. One highly studied approach to cope with this hardness is to restrict the set function, for example, by requiring it to be submodular. An outstanding disadvantage of imposing such a restriction on the set function is that no result is implied for set functions deviating from the restriction, even slightly. A more flexible approach, studied by Feige and Izsak [ITCS 2013], is to design an approximation algorithm whose approximation ratio depends on the complexity of the instance, as measured by some complexity measure. Specifically, they introduced a complexity measure called supermodular degree, measuring deviation from submodularity, and designed an algorithm for the welfare maximization problem with an approximation ratio that depends on this measure. In this work, we give the first (to the best of our knowledge) algorithm for maximizing an arbitrary monotone set function, subject to a k-extendible system. This class of constraints captures, for example, the intersection of k-matroids (note that a single matroid constraint is sufficient to capture the welfare maximization problem). Our approximation ratio deteriorates gracefully with the complexity of the set function and k. Our work can be seen as generalizing both the classic result of Fisher, Nemhauser and Wolsey [Mathematical Programming Study 1978], for maximizing a submodular set function subject to a k-extendible system, and the result of Feige and Izsak for the welfare maximization problem. Moreover, when our algorithm is applied to each one of these simpler cases, it obtains the same approximation ratio as of the respective original work. That is, the generalization does not incur any penalty. Finally, we also consider the less general problem of maximizing a monotone set function subject to a uniform matroid constraint, and give a somewhat better approximation ratio for it.

Cite as

Moran Feldman and Rani Izsak. Constrained Monotone Function Maximization and the Supermodular Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 160-175, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.APPROX-RANDOM.2014.160,
  author =	{Feldman, Moran and Izsak, Rani},
  title =	{{Constrained Monotone Function Maximization and the Supermodular Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{160--175},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.160},
  URN =		{urn:nbn:de:0030-drops-46950},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.160},
  annote =	{Keywords: supermodular degree, set function, submodular, matroid, extendible system}
}

13 Search Results for "Feldman, Moran"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as