5 Search Results for "Xiao, Mingyu"

Document
DOI: 10.4230/LIPIcs.ESA.2023.79
Connectivity in the Presence of an Opponent

Authors: Zihui Liang, Bakh Khoussainov, Toru Takisaka, and Mingyu Xiao

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
The paper introduces two player connectivity games played on finite bipartite graphs. Algorithms that solve these connectivity games can be used as subroutines for solving Müller games. Müller games constitute a well established class of games in model checking and verification. In connectivity games, the objective of one of the players is to visit every node of the game graph infinitely often. The first contribution of this paper is our proof that solving connectivity games can be reduced to the incremental strongly connected component maintenance (ISCCM) problem, an important problem in graph algorithms and data structures. The second contribution is that we non-trivially adapt two known algorithms for the ISCCM problem to provide two efficient algorithms that solve the connectivity games problem. Finally, based on the techniques developed, we recast Horn’s polynomial time algorithm that solves explicitly given Müller games and provide the first correctness proof of the algorithm. Our algorithms are more efficient than that of Horn’s algorithm. Our solution for connectivity games is used as a subroutine in the algorithm.
Cite as

Zihui Liang, Bakh Khoussainov, Toru Takisaka, and Mingyu Xiao. Connectivity in the Presence of an Opponent. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 79:1-79:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{liang_et_al:LIPIcs.ESA.2023.79,
  author =	{Liang, Zihui and Khoussainov, Bakh and Takisaka, Toru and Xiao, Mingyu},
  title =	{{Connectivity in the Presence of an Opponent}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{79:1--79:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.79},
  URN =		{urn:nbn:de:0030-drops-187324},
  doi =		{10.4230/LIPIcs.ESA.2023.79},
  annote =	{Keywords: Explicit M\"{u}ller games, games played on finite graphs, winning strategies, synthesis and analysis of games}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.83
Improved Approximation Algorithms for the Traveling Tournament Problem

Authors: Jingyang Zhao, Mingyu Xiao, and Chao Xu

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
The Traveling Tournament Problem (TTP) is a well-known benchmark problem in the field of tournament timetabling, which asks us to design a double round-robin schedule such that each pair of teams plays one game in each other’s home venue, minimizing the total distance traveled by all n teams (n is even). TTP-k is the problem with one more constraint that each team can have at most k consecutive home games or away games. The case where k = 3, TTP-3, is one of the most investigated cases. In this paper, we improve the approximation ratio of TTP-3 from (1.667+ε) to (1.598+ε), for any ε > 0. Previous schedules were constructed based on a Hamiltonian cycle of the graph. We propose a novel construction based on triangle packing. Then, by combining our triangle packing schedule with the Hamiltonian cycle schedule, we obtain the improved approximation ratio. The idea of our construction can also be extended to k ≥ 4. We demonstrate that the approximation ratio of TTP-4 can be improved from (1.750+ε) to (1.700+ε) by the same method. As an additional product, we also improve the approximation ratio of LDTTP-3 (TTP-3 where all teams are allocated on a straight line) from 4/3 to (6/5+ε).
Cite as

Jingyang Zhao, Mingyu Xiao, and Chao Xu. Improved Approximation Algorithms for the Traveling Tournament Problem. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 83:1-83:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{zhao_et_al:LIPIcs.MFCS.2022.83,
  author =	{Zhao, Jingyang and Xiao, Mingyu and Xu, Chao},
  title =	{{Improved Approximation Algorithms for the Traveling Tournament Problem}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{83:1--83:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.83},
  URN =		{urn:nbn:de:0030-drops-168813},
  doi =		{10.4230/LIPIcs.MFCS.2022.83},
  annote =	{Keywords: Sports scheduling, Traveling Tournament Problem, Approximation algorithm}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.ICALP.2018.112
Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable

Authors: Mingyu Xiao and Hiroshi Nagamochi

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In the bounded-degree cut problem, we are given a multigraph G=(V,E), two disjoint vertex subsets A,B subseteq V, two functions u_A, u_B:V -> {0,1,...,|E|} on V, and an integer k >= 0. The task is to determine whether there is a minimal (A,B)-cut (V_A,V_B) of size at most k such that the degree of each vertex v in V_A in the induced subgraph G[V_A] is at most u_A(v) and the degree of each vertex v in V_B in the induced subgraph G[V_B] is at most u_B(v). In this paper, we show that the bounded-degree cut problem is fixed-parameter tractable by giving a 2^{18k}|G|^{O(1)}-time algorithm. This is the first single exponential FPT algorithm for this problem. The core of the algorithm lies two new lemmas based on important cuts, which give some upper bounds on the number of candidates for vertex subsets in one part of a minimal cut satisfying some properties. These lemmas can be used to design fixed-parameter tractable algorithms for more related problems.
Cite as

Mingyu Xiao and Hiroshi Nagamochi. Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 112:1-112:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{xiao_et_al:LIPIcs.ICALP.2018.112,
  author =	{Xiao, Mingyu and Nagamochi, Hiroshi},
  title =	{{Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{112:1--112:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.112},
  URN =		{urn:nbn:de:0030-drops-91164},
  doi =		{10.4230/LIPIcs.ICALP.2018.112},
  annote =	{Keywords: FPT, Important Cuts, Graph Cuts, Graph Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.62
A Linear-Time Algorithm for Integral Multiterminal Flows in Trees

Authors: Mingyu Xiao and Hiroshi Nagamochi

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

Abstract
In this paper, we study the problem of finding an integral multiflow which maximizes the sum of flow values between every two terminals in an undirected tree with a nonnegative integer edge capacity and a set of terminals. In general, it is known that the flow value of an integral multiflow is bounded by the cut value of a cut-system which consists of disjoint subsets each of which contains exactly one terminal or has an odd cut value, and there exists a pair of an integral multiflow and a cut-system whose flow value and cut value are equal; i.e., a pair of a maximum integral multiflow and a minimum cut. In this paper, we propose an O(n)-time algorithm that finds such a pair of an integral multiflow and a cut-system in a given tree instance with n vertices. This improves the best previous results by a factor of Omega(n). Regarding a given tree in an instance as a rooted tree, we define O(n) rooted tree instances taking each vertex as a root, and establish a recursive formula on maximum integral multiflow values of these instances to design a dynamic programming that computes the maximum integral multiflow values of all O(n) rooted instances in linear time. We can prove that the algorithm implicitly maintains a cut-system so that not only a maximum integral multiflow but also a minimum cut-system can be constructed in linear time for any rooted instance whenever it is necessary. The resulting algorithm is rather compact and succinct.
Cite as

Mingyu Xiao and Hiroshi Nagamochi. A Linear-Time Algorithm for Integral Multiterminal Flows in Trees. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 62:1-62:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{xiao_et_al:LIPIcs.ISAAC.2016.62,
  author =	{Xiao, Mingyu and Nagamochi, Hiroshi},
  title =	{{A Linear-Time Algorithm  for Integral Multiterminal Flows in Trees}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{62:1--62:12},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.62},
  URN =		{urn:nbn:de:0030-drops-68311},
  doi =		{10.4230/LIPIcs.ISAAC.2016.62},
  annote =	{Keywords: Multiterminal flow; Maximum flow; Minimum Cut; Trees; Linear-time algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.89
An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two

Authors: Mingyu Xiao and Shaowei Kou

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

Abstract
The Traveling Tournament Problem is a complex combinatorial optimization problem in tournament timetabling, which asks a schedule of home/away games meeting specific feasibility requirements, while also minimizing the total distance traveled by all the n teams (n is even). Despite intensive algorithmic research on this problem over the last decade, most instances with more than 10 teams in well-known benchmarks are still unsolved. In this paper, we give a practical approximation algorithm for the problem with constraints such that at most two consecutive home games or away games are allowed. Our algorithm, that generates feasible schedules based on minimum perfect matchings in the underlying graph, not only improves the previous approximation ratio from (1+16/n) to about (1+4/n) but also has very good experimental performances. By applying our schedules on known benchmark sets, we can beat all previously-known results of instances with n being a multiple of 4 by 3% to 10%.
Cite as

Mingyu Xiao and Shaowei Kou. An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 89:1-89:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{xiao_et_al:LIPIcs.MFCS.2016.89,
  author =	{Xiao, Mingyu and Kou, Shaowei},
  title =	{{An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{89:1--89: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.89},
  URN =		{urn:nbn:de:0030-drops-64976},
  doi =		{10.4230/LIPIcs.MFCS.2016.89},
  annote =	{Keywords: sports scheduling, traveling tournament problem, approximation algorithms, timetabling combinatorial optimization}
}
  • Refine by Author
  • 5 Xiao, Mingyu
  • 2 Nagamochi, Hiroshi
  • 1 Khoussainov, Bakh
  • 1 Kou, Shaowei
  • 1 Liang, Zihui
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Fixed parameter tractability
  • Show More...

  • Refine by Keyword
  • 1 Approximation algorithm
  • 1 Explicit Müller games
  • 1 FPT
  • 1 Graph Algorithms
  • 1 Graph Cuts
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2016
  • 1 2018
  • 1 2022
  • 1 2023

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