Search Results

Documents authored by Li, Qian

Document
DOI: 10.4230/LIPIcs.ISAAC.2021.48
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.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
DOI: 10.4230/LIPIcs.STACS.2017.51
On the Sensitivity Complexity of k-Uniform Hypergraph Properties

Authors: Qian Li and Xiaoming Sun

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
In this paper we investigate the sensitivity complexity of hypergraph properties. We present a k-uniform hypergraph property with sensitivity complexity O(n^{ceil(k/3)}) for any k >= 3, where n is the number of vertices. Moreover, we can do better when k = 1 (mod 3) by presenting a k-uniform hypergraph property with sensitivity O(n^{ceil(k/3)-1/2}). This result disproves a conjecture of Babai, which conjectures that the sensitivity complexity of k-uniform hypergraph properties is at least Omega(n^{k/2}). We also investigate the sensitivity complexity of other weakly symmetric functions and show that for many classes of transitive-invariant Boolean functions the minimum achievable sensitivity complexity can be O(N^{1/3}), where N is the number of variables. Finally, we give a lower bound for sensitivity of k-uniform hypergraph properties, which implies the sensitivity conjecture of k-uniform hypergraph properties for any constant k.
Cite as

Qian Li and Xiaoming Sun. On the Sensitivity Complexity of k-Uniform Hypergraph Properties. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 51:1-51:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.STACS.2017.51,
  author =	{Li, Qian and Sun, Xiaoming},
  title =	{{On the Sensitivity Complexity of k-Uniform Hypergraph Properties}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{51:1--51:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.51},
  URN =		{urn:nbn:de:0030-drops-69825},
  doi =		{10.4230/LIPIcs.STACS.2017.51},
  annote =	{Keywords: Sensitivity Complexity, k-uniform Hypergraph Properties, Boolean Function, Turan's question}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.32
Universal Guard Problems

Authors: Sándor P. Fekete, Qian Li, Joseph S. B. Mitchell, and Christian Scheffer

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We provide a spectrum of results for the Universal Guard Problem, in which one is to obtain a small set of points ("guards") that are "universal" in their ability to guard any of a set of possible polygonal domains in the plane. We give upper and lower bounds on the number of universal guards that are always sufficient to guard all polygons having a given set of n vertices, or to guard all polygons in a given set of k polygons on an n-point vertex set. Our upper bound proofs include algorithms to construct universal guard sets of the respective cardinalities.
Cite as

Sándor P. Fekete, Qian Li, Joseph S. B. Mitchell, and Christian Scheffer. Universal Guard Problems. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ISAAC.2016.32,
  author =	{Fekete, S\'{a}ndor P. and Li, Qian and Mitchell, Joseph S. B. and Scheffer, Christian},
  title =	{{Universal Guard Problems}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{32:1--32:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.32},
  URN =		{urn:nbn:de:0030-drops-68022},
  doi =		{10.4230/LIPIcs.ISAAC.2016.32},
  annote =	{Keywords: Art Gallery Problem, universal guarding, polygonization, worst-case bounds, robust covering}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.51
On the Optimality of Tape Merge of Two Lists with Similar Size

Authors: Qian Li, Xiaoming Sun, and Jialin Zhang

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
The problem of merging sorted lists in the least number of pairwise comparisons has been solved completely only for a few special cases. Graham and Karp [TAOCP, 1999] independently discovered that the tape merge algorithm is optimal in the worst case when the two lists have the same size. Stockmeyer and Yao [SICOMP, 1980], Murphy and Paull [Inform. Control, 1979], and Christen [1978] independently showed when the lists to be merged are of size m and n satisfying m leq n leq floor(3/2 m) + 1, the tape merge algorithm is optimal in the worst case. This paper extends this result by showing that the tape merge algorithm is optimal in the worst case whenever the size of one list is no larger than 1.52 times the size of the other. The main tool we used to prove lower bounds is Knuth’s adversary methods [TAOCP, 1999]. In addition, we show that the lower bound cannot be improved to 1.8 via Knuth's adversary methods. We also develop a new inequality about Knuth's adversary methods, which might be interesting in its own right. Moreover, we design a simple procedure to achieve constant improvement of the upper bounds for 2m - 2 leq n leq 3m.
Cite as

Qian Li, Xiaoming Sun, and Jialin Zhang. On the Optimality of Tape Merge of Two Lists with Similar Size. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ISAAC.2016.51,
  author =	{Li, Qian and Sun, Xiaoming and Zhang, Jialin},
  title =	{{On the Optimality of Tape Merge of Two Lists with Similar Size}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.51},
  URN =		{urn:nbn:de:0030-drops-68219},
  doi =		{10.4230/LIPIcs.ISAAC.2016.51},
  annote =	{Keywords: comparison-based sorting, tape merge, optimal sort, adversary method}
}
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