8 Search Results for "Ene, Alina"


Document
Track A: Algorithms, Complexity and Games
Faster Submodular Maximization for Several Classes of Matroids

Authors: Monika Henzinger, Paul Liu, Jan Vondrák, and Da Wei Zheng

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


Abstract
The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often wish to enforce various constraints; the matroid constraint has been investigated extensively due to its algorithmic properties and expressive power. Though tight approximation algorithms for general matroid constraints exist in theory, the running times of such algorithms typically scale quadratically, and are not practical for truly large scale settings. Recent progress has focused on fast algorithms for important classes of matroids given in explicit form. Currently, nearly-linear time algorithms only exist for graphic and partition matroids [Alina Ene and Huy L. Nguyen, 2019]. In this work, we develop algorithms for monotone submodular maximization constrained by graphic, transversal matroids, or laminar matroids in time near-linear in the size of their representation. Our algorithms achieve an optimal approximation of 1-1/e-ε and both generalize and accelerate the results of Ene and Nguyen [Alina Ene and Huy L. Nguyen, 2019]. In fact, the running time of our algorithm cannot be improved within the fast continuous greedy framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák, 2014]. To achieve near-linear running time, we make use of dynamic data structures that maintain bases with approximate maximum cardinality and weight under certain element updates. These data structures need to support a weight decrease operation and a novel Freeze operation that allows the algorithm to freeze elements (i.e. force to be contained) in its basis regardless of future data structure operations. For the laminar matroid, we present a new dynamic data structure using the top tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et al., 2005] that maintains the maximum weight basis under insertions and deletions of elements in O(log n) time. This data structure needs to support certain subtree query and path update operations that are performed every insertion and deletion that are non-trivial to handle in conjunction. For the transversal matroid the Freeze operation corresponds to requiring the data structure to keep a certain set S of vertices matched, a property that we call S-stability. While there is a large body of work on dynamic matching algorithms, none are S-stable and maintain an approximate maximum weight matching under vertex updates. We give the first such algorithm for bipartite graphs with total running time linear (up to log factors) in the number of edges.

Cite as

Monika Henzinger, Paul Liu, Jan Vondrák, and Da Wei Zheng. Faster Submodular Maximization for Several Classes of Matroids. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 74:1-74:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ICALP.2023.74,
  author =	{Henzinger, Monika and Liu, Paul and Vondr\'{a}k, Jan and Zheng, Da Wei},
  title =	{{Faster Submodular Maximization for Several Classes of Matroids}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{74:1--74:18},
  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.74},
  URN =		{urn:nbn:de:0030-drops-181267},
  doi =		{10.4230/LIPIcs.ICALP.2023.74},
  annote =	{Keywords: submodular optimization, dynamic data structures, matching algorithms}
}
Document
Track A: Algorithms, Complexity and Games
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 Õ(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-dev.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
Track A: Algorithms, Complexity and Games
A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint

Authors: Alina Ene and Huy L. Nguyen

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


Abstract
We consider the problem of maximizing a monotone submodular function subject to a knapsack constraint. Our main contribution is an algorithm that achieves a nearly-optimal, 1 - 1/e - epsilon approximation, using (1/epsilon)^{O(1/epsilon^4)} n log^2{n} function evaluations and arithmetic operations. Our algorithm is impractical but theoretically interesting, since it overcomes a fundamental running time bottleneck of the multilinear extension relaxation framework. This is the main approach for obtaining nearly-optimal approximation guarantees for important classes of constraints but it leads to Omega(n^2) running times, since evaluating the multilinear extension is expensive. Our algorithm maintains a fractional solution with only a constant number of entries that are strictly fractional, which allows us to overcome this obstacle.

Cite as

Alina Ene and Huy L. Nguyen. A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 53:1-53:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{ene_et_al:LIPIcs.ICALP.2019.53,
  author =	{Ene, Alina and Nguyen, Huy L.},
  title =	{{A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{53:1--53:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.53},
  URN =		{urn:nbn:de:0030-drops-106290},
  doi =		{10.4230/LIPIcs.ICALP.2019.53},
  annote =	{Keywords: submodular maximization, knapsack constraint, fast algorithms}
}
Document
Track A: Algorithms, Complexity and Games
Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint

Authors: Alina Ene and Huy L. Nguyen

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


Abstract
We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is to obtain the best possible running times for important matroids. We develop a new algorithm for a general matroid constraint with a 1 - 1/e - epsilon approximation that achieves a fast running time provided we have a fast data structure for maintaining an approximately maximum weight base in the matroid through a sequence of decrease weight operations. We construct such data structures for graphic matroids and partition matroids, and we obtain the first algorithms for these classes of matroids that achieve a nearly-optimal, 1 - 1/e - epsilon approximation, using a nearly-linear number of function evaluations and arithmetic operations.

Cite as

Alina Ene and Huy L. Nguyen. Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{ene_et_al:LIPIcs.ICALP.2019.54,
  author =	{Ene, Alina and Nguyen, Huy L.},
  title =	{{Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.54},
  URN =		{urn:nbn:de:0030-drops-106303},
  doi =		{10.4230/LIPIcs.ICALP.2019.54},
  annote =	{Keywords: submodular maximization, matroid constraints, fast running times}
}
Document
Approximation Algorithms for Stochastic k-TSP

Authors: Alina Ene, Viswanath Nagarajan, and Rishi Saket

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)


Abstract
This paper studies the stochastic variant of the classical k-TSP problem where rewards at the vertices are independent random variables which are instantiated upon the tour's visit. The objective is to minimize the expected length of a tour that collects reward at least k. The solution is a policy describing the tour which may (adaptive) or may not (non-adaptive) depend on the observed rewards. Our work presents an adaptive O(log k)-approximation algorithm for Stochastic k-TSP, along with a non-adaptive O(log^2 k)-approximation algorithm which also upper bounds the adaptivity gap by O(log^2 k). We also show that the adaptivity gap of Stochastic k-TSP is at least e, even in the special case of stochastic knapsack cover.

Cite as

Alina Ene, Viswanath Nagarajan, and Rishi Saket. Approximation Algorithms for Stochastic k-TSP. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{ene_et_al:LIPIcs.FSTTCS.2017.27,
  author =	{Ene, Alina and Nagarajan, Viswanath and Saket, Rishi},
  title =	{{Approximation Algorithms for Stochastic k-TSP}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.27},
  URN =		{urn:nbn:de:0030-drops-83910},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.27},
  annote =	{Keywords: Stochastic TSP, algorithms, approximation, adaptivity gap}
}
Document
Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs

Authors: Chandra Chekuri, Alina Ene, and Marcin Pilipczuk

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)


Abstract
We study the problem of routing symmetric demand pairs in planar digraphs. The input consists of a directed planar graph G = (V, E) and a collection of k source-destination pairs M = {s_1t_1, ..., s_kt_k}. The goal is to maximize the number of pairs that are routed along disjoint paths. A pair s_it_i is routed in the symmetric setting if there is a directed path connecting s_i to t_i and a directed path connecting t_i to s_i. In this paper we obtain a randomized poly-logarithmic approximation with constant congestion for this problem in planar digraphs. The main technical contribution is to show that a planar digraph with directed treewidth h contains a constant congestion crossbar of size Omega(h/polylog(h)).

Cite as

Chandra Chekuri, Alina Ene, and Marcin Pilipczuk. Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:LIPIcs.ICALP.2016.7,
  author =	{Chekuri, Chandra and Ene, Alina and Pilipczuk, Marcin},
  title =	{{Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.7},
  URN =		{urn:nbn:de:0030-drops-62737},
  doi =		{10.4230/LIPIcs.ICALP.2016.7},
  annote =	{Keywords: Disjoint paths, symmetric demands, planar directed graph}
}
Document
On Routing Disjoint Paths in Bounded Treewidth Graphs

Authors: Alina Ene, Matthias Mnich, Marcin Pilipczuk, and Andrej Risteski

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)


Abstract
We study the problem of routing on disjoint paths in bounded treewidth graphs with both edge and node capacities. The input consists of a capacitated graph G and a collection of k source-destination pairs M = (s_1, t_1), ..., (s_k, t_k). The goal is to maximize the number of pairs that can be routed subject to the capacities in the graph. A routing of a subset M' of the pairs is a collection P of paths such that, for each pair (s_i, t_i) in M', there is a path in P connecting s_i to t_i. In the Maximum Edge Disjoint Paths (MaxEDP) problem, the graph G has capacities cap(e) on the edges and a routing P is feasible if each edge e is in at most cap(e) of the paths of P. The Maximum Node Disjoint Paths (MaxNDP) problem is the node-capacitated counterpart of MaxEDP. In this paper we obtain an O(r^3) approximation for MaxEDP on graphs of treewidth at most r and a matching approximation for MaxNDP on graphs of pathwidth at most r. Our results build on and significantly improve the work by Chekuri et al. [ICALP 2013] who obtained an O(r * 3^r) approximation for MaxEDP.

Cite as

Alina Ene, Matthias Mnich, Marcin Pilipczuk, and Andrej Risteski. On Routing Disjoint Paths in Bounded Treewidth Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{ene_et_al:LIPIcs.SWAT.2016.15,
  author =	{Ene, Alina and Mnich, Matthias and Pilipczuk, Marcin and Risteski, Andrej},
  title =	{{On Routing Disjoint Paths in Bounded Treewidth Graphs}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.15},
  URN =		{urn:nbn:de:0030-drops-60378},
  doi =		{10.4230/LIPIcs.SWAT.2016.15},
  annote =	{Keywords: Algorithms and data structures, disjoint paths, treewidth}
}
Document
Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture

Authors: Alina Ene and Jan Vondrák

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


Abstract
We consider the Minimum Submodular Cost Allocation (MSCA) problem. In this problem, we are given k submodular cost functions f_1, ... , f_k: 2^V -> R_+ and the goal is to partition V into k sets A_1, ..., A_k so as to minimize the total cost sum_{i = 1}^k f_i(A_i). We show that MSCA is inapproximable within any multiplicative factor even in very restricted settings; prior to our work, only Set Cover hardness was known. In light of this negative result, we turn our attention to special cases of the problem. We consider the setting in which each function f_i satisfies f_i = g_i + h, where each g_i is monotone submodular and h is (possibly non-monotone) submodular. We give an O(k log |V|) approximation for this problem. We provide some evidence that a factor of k may be necessary, even in the special case of HyperLabel. In particular, we formulate a simplex-coloring conjecture that implies a Unique-Games-hardness of (k - 1 - epsilon) for k-uniform HyperLabel and label set [k]. We provide a proof of the simplex-coloring conjecture for k=3.

Cite as

Alina Ene and Jan Vondrák. Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 144-159, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{ene_et_al:LIPIcs.APPROX-RANDOM.2014.144,
  author =	{Ene, Alina and Vondr\'{a}k, Jan},
  title =	{{Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{144--159},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.144},
  URN =		{urn:nbn:de:0030-drops-46943},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.144},
  annote =	{Keywords: Minimum Cost Submodular Allocation, Submodular Optimization, Hypergraph Labeling}
}
  • Refine by Author
  • 7 Ene, Alina
  • 3 Nguyen, Huy L.
  • 2 Pilipczuk, Marcin
  • 2 Vondrák, Jan
  • 1 Alaluf, Naor
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Submodular optimization and polymatroids
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Mathematics of computing → Submodular optimization and polymatroids
  • 1 Theory of computation → Data structures design and analysis
  • Show More...

  • Refine by Keyword
  • 2 submodular maximization
  • 1 Algorithms and data structures
  • 1 Disjoint paths
  • 1 Hypergraph Labeling
  • 1 Minimum Cost Submodular Allocation
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 2016
  • 2 2019
  • 1 2014
  • 1 2018
  • 1 2020
  • 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