3 Search Results for "Fafianie, Stefan"


Document
Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time

Authors: Jianer Chen, Qin Huang, Iyad Kanj, Qian Li, and Ge Xia

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)


Abstract
We present streaming algorithms for the graph k-matching problem in both the insert-only and dynamic models. Our algorithms, while keeping the space complexity matching the best known upper bound, have optimal or near-optimal update time, significantly improving on previous results. More specifically, for the insert-only streaming model, we present a one-pass randomized algorithm that runs in optimal 𝒪(k²) space and has optimal 𝒪(1) update time, and that, w.h.p. (with high probability), computes a maximum weighted k-matching of a weighted graph. Previously, the best upper bound on the update time was 𝒪(log k), which was achieved by a deterministic streaming algorithm that however only works for unweighted graphs [Stefan Fafianie and Stefan Kratsch, 2014]. For the dynamic streaming model, we present a one-pass randomized algorithm that, w.h.p., computes a maximum weighted k-matching of a weighted graph in Õ(Wk²) space and with Õ(1) update time, where W is the number of distinct edge weights. Again the update time of our algorithm improves the previous best upper bound Õ(k²) [Rajesh Chitnis et al., 2016]. Moreover, we prove that in the dynamic streaming model, any randomized streaming algorithm for the problem requires k²⋅ Ω(W(log W+1)) bits of space. Hence, both the space and update-time complexities achieved by our algorithm in the dynamic model are near-optimal. A streaming approximation algorithm for k-matching is also presented, whose space complexity matches the best known upper bound with a significantly improved update time.

Cite as

Jianer Chen, Qin Huang, Iyad Kanj, Qian Li, and Ge Xia. Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2021.48,
  author =	{Chen, Jianer and Huang, Qin and Kanj, Iyad and Li, Qian and Xia, Ge},
  title =	{{Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{48:1--48:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.48},
  URN =		{urn:nbn:de:0030-drops-154816},
  doi =		{10.4230/LIPIcs.ISAAC.2021.48},
  annote =	{Keywords: streaming algorithms, matching, parameterized algorithms, lower bounds}
}
Document
Preprocessing Under Uncertainty: Matroid Intersection

Authors: Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, and Vuong Anh Quyen

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
We continue the study of preprocessing under uncertainty that was initiated independently by Assadi et al. (FSTTCS 2015) and Fafianie et al. (STACS 2016). Here, we are given an instance of a tractable problem with a large static/known part and a small part that is dynamic/uncertain, and ask if there is an efficient algorithm that computes an instance of size polynomial in the uncertain part of the input, from which we can extract an optimal solution to the original instance for all (usually exponentially many) instantiations of the uncertain part. In the present work, we focus on the Matroid Intersection problem. Amongst others we present a positive preprocessing result for the important case of finding a largest common independent set in two linear matroids. Motivated by an application for intersecting two gammoids we also revisit Maximum Flow. There we tighten a lower bound of Assadi et al. and give an alternative positive result for the case of low uncertain capacity that yields a Maximum Flow instance as output rather than a matrix.

Cite as

Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, and Vuong Anh Quyen. Preprocessing Under Uncertainty: Matroid Intersection. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{fafianie_et_al:LIPIcs.MFCS.2016.35,
  author =	{Fafianie, Stefan and Hols, Eva-Maria C. and Kratsch, Stefan and Quyen, Vuong Anh},
  title =	{{Preprocessing Under Uncertainty: Matroid Intersection}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{35:1--35:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.35},
  URN =		{urn:nbn:de:0030-drops-64490},
  doi =		{10.4230/LIPIcs.MFCS.2016.35},
  annote =	{Keywords: preprocessing, uncertainty, maximum flow, matroid intersection}
}
Document
Preprocessing Under Uncertainty

Authors: Stefan Fafianie, Stefan Kratsch, and Vuong Anh Quyen

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)


Abstract
In this work we study preprocessing for tractable problems when part of the input is unknown or uncertain. This comes up naturally if, e.g., the load of some machines or the congestion of some roads is not known far enough in advance, or if we have to regularly solve a problem over instances that are largely similar, e.g., daily airport scheduling with few charter flights. Unlike robust optimization, which also studies settings like this, our goal lies not in computing solutions that are (approximately) good for every instantiation. Rather, we seek to preprocess the known parts of the input, to speed up finding an optimal solution once the missing data is known. We present efficient algorithms that given an instance with partially uncertain input generate an instance of size polynomial in the amount of uncertain data that is equivalent for every instantiation of the unknown part. Concretely, we obtain such algorithms for minimum spanning tree, minimum weight matroid basis, and maximum cardinality bipartite matching, where respectively the weight of edges, weight of elements, and the availability of vertices is unknown for part of the input. Furthermore, we show that there are tractable problems, such as small connected vertex cover, for which one cannot hope to obtain similar results.

Cite as

Stefan Fafianie, Stefan Kratsch, and Vuong Anh Quyen. Preprocessing Under Uncertainty. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 33:1-33:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{fafianie_et_al:LIPIcs.STACS.2016.33,
  author =	{Fafianie, Stefan and Kratsch, Stefan and Anh Quyen, Vuong},
  title =	{{Preprocessing Under Uncertainty}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{33:1--33:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.33},
  URN =		{urn:nbn:de:0030-drops-57340},
  doi =		{10.4230/LIPIcs.STACS.2016.33},
  annote =	{Keywords: preprocessing, uncertainty, spanning trees, matroids, matchings}
}
  • Refine by Author
  • 2 Fafianie, Stefan
  • 2 Kratsch, Stefan
  • 1 Anh Quyen, Vuong
  • 1 Chen, Jianer
  • 1 Hols, Eva-Maria C.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 2 preprocessing
  • 2 uncertainty
  • 1 lower bounds
  • 1 matching
  • 1 matchings
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2016
  • 1 2021

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