3 Search Results for "Zhang, Ting"


Document
APPROX
Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs

Authors: Chun-Hsiang Chan, Bundit Laekhanukit, Hao-Ting Wei, and Yuhao Zhang

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


Abstract
In the k-Connected Directed Steiner Tree problem (k-DST), we are given a directed graph G = (V,E) with edge (or vertex) costs, a root vertex r, a set of q terminals T, and a connectivity requirement k > 0; the goal is to find a minimum-cost subgraph H of G such that H has k edge-disjoint paths from the root r to each terminal in T. The k-DST problem is a natural generalization of the classical Directed Steiner Tree problem (DST) in the fault-tolerant setting in which the solution subgraph is required to have an r,t-path, for every terminal t, even after removing k-1 vertices or edges. Despite being a classical problem, there are not many positive results on the problem, especially for the case k ≥ 3. In this paper, we present an O(log k log q)-approximation algorithm for k-DST when an input graph is quasi-bipartite, i.e., when there is no edge joining two non-terminal vertices. To the best of our knowledge, our algorithm is the only known non-trivial approximation algorithm for k-DST, for k ≥ 3, that runs in polynomial-time Our algorithm is tight for every constant k, due to the hardness result inherited from the Set Cover problem.

Cite as

Chun-Hsiang Chan, Bundit Laekhanukit, Hao-Ting Wei, and Yuhao Zhang. Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 63:1-63:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.APPROX/RANDOM.2020.63,
  author =	{Chan, Chun-Hsiang and Laekhanukit, Bundit and Wei, Hao-Ting and Zhang, Yuhao},
  title =	{{Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{63:1--63:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  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.2020.63},
  URN =		{urn:nbn:de:0030-drops-126667},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.63},
  annote =	{Keywords: Approximation Algorithms, Network Design, Directed Graphs}
}
Document
A Tight Lower Bound for Streett Complementation

Authors: Yang Cai and Ting Zhang

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)


Abstract
Finite automata on infinite words (omega-automata) proved to be a powerful weapon for modeling and reasoning infinite behaviors of reactive systems. Complementation of omega-automata is crucial in many of these applications. But the problem is non-trivial; even after extensive study during the past two decades, we still have an important type of omega-automata, namely Streett automata, for which the gap between the current best lower bound 2^(Omega(n lg nk)) and upper bound 2^(O (nk lg nk)) is substantial, for the Streett index size k can be exponential in the number of states n. In a previous work we showed a construction for complementing Streett automata with the upper bound 2^(O(n lg n+nk lg k)) for k = O(n) and 2^(O(n^2 lg n)) for k = omega(n). In this paper we establish a matching lower bound 2^(Omega (n lg n+nk lg k)) for k = O(n) and 2^(Omega (n^2 lg n)) for k = omega(n), and therefore showing that the construction is asymptotically optimal with respect to the ^(Theta(.)) notation.

Cite as

Yang Cai and Ting Zhang. A Tight Lower Bound for Streett Complementation. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 339-350, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.FSTTCS.2011.339,
  author =	{Cai, Yang and Zhang, Ting},
  title =	{{A Tight Lower Bound for Streett Complementation}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{339--350},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.339},
  URN =		{urn:nbn:de:0030-drops-33474},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.339},
  annote =	{Keywords: omega-automata, Streett automata, complementation, lower bounds}
}
Document
Tight Upper Bounds for Streett and Parity Complementation

Authors: Yang Cai and Ting Zhang

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)


Abstract
Complementation of finite automata on infinite words is not only a fundamental problem in automata theory, but also serves as a cornerstone for solving numerous decision problems in mathematical logic, model-checking, program analysis and verification. For Streett complementation, a significant gap exists between the current lower bound 2^{Omega(n*log(n*k))} and upper bound 2^{O(n*k*log(n*k))}, where n is the state size, k is the number of Streett pairs, and k can be as large as 2^{n}. Determining the complexity of Streett complementation has been an open question since the late 80's. In this paper we show a complementation construction with upper bound 2^{O(n*log(n)+n*k*log(k))} for k=O(n) and 2^{O(n^{2}*log(n))} for k=Omega(n), which matches well the lower bound obtained in the paper arXiv:1102.2963. We also obtain a tight upper bound 2^{O(n*log(n))} for parity complementation.

Cite as

Yang Cai and Ting Zhang. Tight Upper Bounds for Streett and Parity Complementation. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 112-128, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.CSL.2011.112,
  author =	{Cai, Yang and Zhang, Ting},
  title =	{{Tight Upper Bounds for Streett and Parity Complementation}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{112--128},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.112},
  URN =		{urn:nbn:de:0030-drops-32269},
  doi =		{10.4230/LIPIcs.CSL.2011.112},
  annote =	{Keywords: Streett automata, omega-automata, parity automata, complementation, upper bounds}
}
  • Refine by Author
  • 2 Cai, Yang
  • 2 Zhang, Ting
  • 1 Chan, Chun-Hsiang
  • 1 Laekhanukit, Bundit
  • 1 Wei, Hao-Ting
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Routing and network design problems

  • Refine by Keyword
  • 2 Streett automata
  • 2 complementation
  • 2 omega-automata
  • 1 Approximation Algorithms
  • 1 Directed Graphs
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2011
  • 1 2020

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