2 Search Results for "Terao, Tatsuya"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.104
Faster Matroid Partition Algorithms

Authors: Tatsuya Terao

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In the matroid partitioning problem, we are given k matroids ℳ₁ = (V, ℐ_1), … , ℳ_k = (V, ℐ_k) defined over a common ground set V of n elements, and we need to find a partitionable set S ⊆ V of largest possible cardinality, denoted by p. Here, a set S ⊆ V is called partitionable if there exists a partition (S_1, … , S_k) of S with S_i ∈ ℐ_i for i = 1, …, k. In 1986, Cunningham [Cunningham, 1986] presented a matroid partition algorithm that uses O(n p^{3/2} + k n) independence oracle queries, which was the previously known best algorithm. This query complexity is O(n^{5/2}) when k ≤ n. Our main result is to present a matroid partition algorithm that uses Õ(k^{1/3} n p + k n) independence oracle queries, which is Õ(n^{7/3}) when k ≤ n. This improves upon previous Cunningham’s algorithm. To obtain this, we present a new approach edge recycling augmentation, which can be attained through new ideas: an efficient utilization of the binary search technique by Nguyễn [Nguyen, 2019] and Chakrabarty-Lee-Sidford-Singla-Wong [Chakrabarty et al., 2019] and a careful analysis of the number of independence oracle queries. Our analysis differs significantly from the one for matroid intersection algorithms, because of the parameter k. We also present a matroid partition algorithm that uses Õ((n + k) √p) rank oracle queries.
Cite as

Tatsuya Terao. Faster Matroid Partition Algorithms. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 104:1-104:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{terao:LIPIcs.ICALP.2023.104,
  author =	{Terao, Tatsuya},
  title =	{{Faster Matroid Partition Algorithms}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{104:1--104:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.104},
  URN =		{urn:nbn:de:0030-drops-181566},
  doi =		{10.4230/LIPIcs.ICALP.2023.104},
  annote =	{Keywords: Matroid Partition, Matroid Union, Combinatorial Optimization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.47
One-Face Shortest Disjoint Paths with a Deviation Terminal

Authors: Yusuke Kobayashi and Tatsuya Terao

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
For an undirected graph G and distinct vertices s₁, t₁, … , s_k, t_k called terminals, the shortest k-disjoint paths problem asks for k pairwise vertex-disjoint paths P₁, … , P_k such that P_i connects s_i and t_i for i = 1, … , k and the sum of their lengths is minimized. This problem is a natural optimization version of the well-known k-disjoint paths problem, and its polynomial solvability is widely open. One of the best results on the shortest k-disjoint paths problem is due to Datta et al. [Datta et al., 2018], who present a polynomial-time algorithm for the case when G is planar and all the terminals are on one face. In this paper, we extend this result by giving a polynomial-time randomized algorithm for the case when all the terminals except one are on some face of G. In our algorithm, we combine the arguments of Datta et al. with some results on the shortest disjoint (A + B)-paths problem shown by Hirai and Namba [Hirai and Namba, 2018]. To this end, we present a non-trivial bijection between k disjoint paths and disjoint (A + B)-paths, which is a key technical contribution of this paper.
Cite as

Yusuke Kobayashi and Tatsuya Terao. One-Face Shortest Disjoint Paths with a Deviation Terminal. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 47:1-47:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2022.47,
  author =	{Kobayashi, Yusuke and Terao, Tatsuya},
  title =	{{One-Face Shortest Disjoint Paths with a Deviation Terminal}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{47:1--47:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.47},
  URN =		{urn:nbn:de:0030-drops-173322},
  doi =		{10.4230/LIPIcs.ISAAC.2022.47},
  annote =	{Keywords: shortest disjoint paths, polynomial time algorithm, planar graph}
}
  • Refine by Author
  • 2 Terao, Tatsuya
  • 1 Kobayashi, Yusuke

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Matroids and greedoids
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Discrete optimization

  • Refine by Keyword
  • 1 Combinatorial Optimization
  • 1 Matroid Partition
  • 1 Matroid Union
  • 1 planar graph
  • 1 polynomial time algorithm
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact