Search Results

Documents authored by Chen, Jianer

Document
DOI: 10.4230/LIPIcs.STACS.2022.21
Near-Optimal Algorithms for Point-Line Covering Problems

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

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We study fundamental point-line covering problems in computational geometry, in which the input is a set S of points in the plane. The first is the Rich Lines problem, which asks for the set of all lines that each covers at least λ points from S, for a given integer parameter λ ≥ 2; this problem subsumes the 3-Points-on-Line problem and the Exact Fitting problem, which - the latter - asks for a line containing the maximum number of points. The second is the NP-hard problem Line Cover, which asks for a set of k lines that cover the points of S, for a given parameter k ∈ ℕ. Both problems have been extensively studied. In particular, the Rich Lines problem is a fundamental problem whose solution serves as a building block for several algorithms in computational geometry. For Rich Lines and Exact Fitting, we present a randomized Monte Carlo algorithm that achieves a lower running time than that of Guibas et al.’s algorithm [Computational Geometry 1996], for a wide range of the parameter λ. We derive lower-bound results showing that, for λ = Ω(√{n log n}), the upper bound on the running time of this randomized algorithm matches the lower bound that we derive on the time complexity of Rich Lines in the algebraic computation trees model. For Line Cover, we present two kernelization algorithms: a randomized Monte Carlo algorithm and a deterministic algorithm. Both algorithms improve the running time of existing kernelization algorithms for Line Cover. We derive lower-bound results showing that the running time of the randomized algorithm we present comes close to the lower bound we derive on the time complexity of kernelization algorithms for Line Cover in the algebraic computation trees model.
Cite as

Jianer Chen, Qin Huang, Iyad Kanj, and Ge Xia. Near-Optimal Algorithms for Point-Line Covering Problems. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2022.21,
  author =	{Chen, Jianer and Huang, Qin and Kanj, Iyad and Xia, Ge},
  title =	{{Near-Optimal Algorithms for Point-Line Covering Problems}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.21},
  URN =		{urn:nbn:de:0030-drops-158312},
  doi =		{10.4230/LIPIcs.STACS.2022.21},
  annote =	{Keywords: line cover, rich lines, exact fitting, kernelization, randomized algorithms, complexity lower bounds, algebraic computation trees}
}
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/DagSemProc.07281.5
Directed Feedback Vertex Set Problem is FPT

Authors: Jianer Chen, Yang Liu, and Songiian Lu

Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)

Abstract
To decide if the {sc parameterized feedback vertex set} problem in directed graph is fixed-parameter tractable is a long standing open problem. In this paper, we prove that the {sc parameterized feedback vertex set} in directed graph is fixed-parameter tractable and give the first FPT algorithm of running time $O((1.48k)^kn^{O(1)})$ for it. As the {sc feedback arc set} problem in directed graph can be transformed to a {sc feedback vertex set} problem in directed graph, hence we also show that the {sc parameterized feedback arc set} problem can be solved in time of $O((1.48k)^kn^{O(1)})$.
Cite as

Jianer Chen, Yang Liu, and Songiian Lu. Directed Feedback Vertex Set Problem is FPT. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:DagSemProc.07281.5,
  author =	{Chen, Jianer and Liu, Yang and Lu, Songiian},
  title =	{{Directed Feedback Vertex Set Problem is FPT}},
  booktitle =	{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7281},
  editor =	{Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.5},
  URN =		{urn:nbn:de:0030-drops-12333},
  doi =		{10.4230/DagSemProc.07281.5},
  annote =	{Keywords: Directed feedback vertex set problem, parameterized algorithm,}
}
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