Search Results

Documents authored by Huang, Zengfeng

Document
DOI: 10.4230/LIPIcs.SoCG.2024.82
Space Complexity of Euclidean Clustering

Authors: Xiaoyi Zhu, Yuxiang Tian, Lingxiao Huang, and Zengfeng Huang

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
The (k, z)-Clustering problem in Euclidean space ℝ^d has been extensively studied. Given the scale of data involved, compression methods for the Euclidean (k, z)-Clustering problem, such as data compression and dimension reduction, have received significant attention in the literature. However, the space complexity of the clustering problem, specifically, the number of bits required to compress the cost function within a multiplicative error ε, remains unclear in existing literature. This paper initiates the study of space complexity for Euclidean (k, z)-Clustering and offers both upper and lower bounds. Our space bounds are nearly tight when k is constant, indicating that storing a coreset, a well-known data compression approach, serves as the optimal compression scheme. Furthermore, our lower bound result for (k, z)-Clustering establishes a tight space bound of Θ(n d) for terminal embedding, where n represents the dataset size. Our technical approach leverages new geometric insights for principal angles and discrepancy methods, which may hold independent interest.
Cite as

Xiaoyi Zhu, Yuxiang Tian, Lingxiao Huang, and Zengfeng Huang. Space Complexity of Euclidean Clustering. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 82:1-82:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{zhu_et_al:LIPIcs.SoCG.2024.82,
  author =	{Zhu, Xiaoyi and Tian, Yuxiang and Huang, Lingxiao and Huang, Zengfeng},
  title =	{{Space Complexity of Euclidean Clustering}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{82:1--82:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.82},
  URN =		{urn:nbn:de:0030-drops-200279},
  doi =		{10.4230/LIPIcs.SoCG.2024.82},
  annote =	{Keywords: Space complexity, Euclidean clustering, coreset, terminal embedding}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.18
Dynamic Graph Stream Algorithms in o(n) Space

Authors: Zengfeng Huang and Pan Peng

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

Abstract
In this paper we study graph problems in dynamic streaming model, where the input is defined by a sequence of edge insertions and deletions. As many natural problems require Omega(n) space, where n is the number of vertices, existing works mainly focused on designing ~O(n) space algorithms. Although sublinear in the number of edges for dense graphs, it could still be too large for many applications (e.g. n is huge or the graph is sparse). In this work, we give single-pass algorithms beating this space barrier for two classes of problems. We present o(n) space algorithms for estimating the number of connected components with additive error epsilon*n and (1 + epsilon)-approximating the weight of minimum spanning tree. The latter improves previous ~O(n) space algorithm given by Ahn et al. (SODA 2012) for connected graphs with bounded edge weights. We initiate the study of approximate graph property testing in the dynamic streaming model, where we want to distinguish graphs satisfying the property from graphs that are epsilon-far from having the property. We consider the problem of testing k-edge connectivity, k-vertex connectivity, cycle-freeness and bipartiteness (of planar graphs), for which, we provide algorithms using roughly ~O(n^{1-epsilon}) space, which is o(n) for any constant epsilon. To complement our algorithms, we present Omega(n^{1-O(epsilon)}) space lower bounds for these problems, which show that such a dependence on epsilon is necessary.
Cite as

Zengfeng Huang and Pan Peng. Dynamic Graph Stream Algorithms in o(n) Space. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ICALP.2016.18,
  author =	{Huang, Zengfeng and Peng, Pan},
  title =	{{Dynamic Graph Stream Algorithms in o(n) Space}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{18:1--18:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.18},
  URN =		{urn:nbn:de:0030-drops-62801},
  doi =		{10.4230/LIPIcs.ICALP.2016.18},
  annote =	{Keywords: dynamic graph streams, sketching, property testing, minimum spanning tree}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.460
Communication Complexity of Approximate Matching in Distributed Graphs

Authors: Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic, and Qin Zhang

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
In this paper we consider the communication complexity of approximation algorithms for maximum matching in a graph in the message-passing model of distributed computation. The input graph consists of n vertices and edges partitioned over a set of k sites. The output is an \alpha-approximate maximum matching in the input graph which has to be reported by one of the sites. We show a lower bound on the communication complexity of \Omega(\alpha^2 k n) and show that it is tight up to poly-logarithmic factors. This lower bound also applies to other combinatorial problems on graphs in the message-passing computation model, including max-flow and graph sparsification.
Cite as

Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic, and Qin Zhang. Communication Complexity of Approximate Matching in Distributed Graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 460-473, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.STACS.2015.460,
  author =	{Huang, Zengfeng and Radunovic, Bozidar and Vojnovic, Milan and Zhang, Qin},
  title =	{{Communication Complexity of Approximate Matching in Distributed Graphs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{460--473},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.460},
  URN =		{urn:nbn:de:0030-drops-49348},
  doi =		{10.4230/LIPIcs.STACS.2015.460},
  annote =	{Keywords: approximate maximum matching, distributed computation, communication complexity}
}
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 About DROPS Imprint Privacy Contact