Search Results

Documents authored by Teruyama, Junichi

Document
DOI: 10.4230/OASIcs.ATMOS.2021.13
Locating Evacuation Centers Optimally in Path and Cycle Networks

Authors: Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh, and Junichi Teruyama

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
We present dynamic flow algorithms to solve the k-sink problem whose aim is to locate k sinks (evacuation centers) in such a way that the evacuation time of the last evacuee is minimized. In the confluent model, the evacuees originating from or passing through a vertex must evacuate to the same sink, and most known results on the k-sink problem adopt the confluent model. When the edge capacities are uniform (resp. general), our algorithms for non-confluent flow in the path networks run in O(n + k² log² n) (resp. O(n log(n) + k² log⁵ n)) time, where n is the number of vertices. Our algorithms for cycle networks run in O(k²n log² n) (resp. O(k²n log⁵ n)) time, when the edge capacities are uniform (resp. general).
Cite as

Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh, and Junichi Teruyama. Locating Evacuation Centers Optimally in Path and Cycle Networks. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{benkoczi_et_al:OASIcs.ATMOS.2021.13,
  author =	{Benkoczi, Robert and Bhattacharya, Binay and Higashikawa, Yuya and Kameda, Tsunehiko and Katoh, Naoki and Teruyama, Junichi},
  title =	{{Locating Evacuation Centers Optimally in Path and Cycle Networks}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{13:1--13:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.13},
  URN =		{urn:nbn:de:0030-drops-148825},
  doi =		{10.4230/OASIcs.ATMOS.2021.13},
  annote =	{Keywords: Efficient algorithms, facility location, minmax sink, evacuation problem, dynamic flow in network}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.58
Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs

Authors: Atsuki Nagao, Kazuhisa Seto, and Junichi Teruyama

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
The satisfiability of a given branching program is to determine whether there exists a consistent path from the root to 1-sink. In a syntactic read-k-times branching program, each variable appears at most k times in any path from the root to a sink. We provide a satisfiability algorithm for syntactic read-k-times branching programs with n variables and m edges that runs in time O\left(\poly(n, m^{k^2})\cdot 2^{(1-\mu(k))n}\right), where \mu(k) = \frac{1}{4^{k+1}}. Our algorithm is based on the decomposition technique shown by Borodin, Razborov and Smolensky [Computational Complexity, 1993].
Cite as

Atsuki Nagao, Kazuhisa Seto, and Junichi Teruyama. Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 58:1-58:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{nagao_et_al:LIPIcs.ISAAC.2017.58,
  author =	{Nagao, Atsuki and Seto, Kazuhisa and Teruyama, Junichi},
  title =	{{Satisfiability Algorithm for Syntactic Read-\$k\$-times Branching Programs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{58:1--58:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.58},
  URN =		{urn:nbn:de:0030-drops-82423},
  doi =		{10.4230/LIPIcs.ISAAC.2017.58},
  annote =	{Keywords: branching program, read-k-times, satisfiability, moderately exponential time, polynomial space}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.82
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression

Authors: Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama

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

Abstract
A Boolean function f:{0,1}^n -> {0,1} is weighted symmetric if there exist a function g: Z -> {0,1} and integers w_0, w_1, ..., w_n such that f(x_1, ...,x_n) = g(w_0+sum_{i=1}^n w_i x_i) holds. In this paper, we present algorithms for the circuit satisfiability problem of bounded depth circuits with AND, OR, NOT gates and a limited number of weighted symmetric gates. Our algorithms run in time super-polynomially faster than 2^n even when the number of gates is super-polynomial and the maximum weight of symmetric gates is nearly exponential. With an additional trick, we give an algorithm for the maximum satisfiability problem that runs in time poly(n^t)*2^{n-n^{1/O(t)}} for instances with n variables, O(n^t) clauses and arbitrary weights. To the best of our knowledge, this is the first moderately exponential time algorithm even for Max 2SAT instances with arbitrary weights. Through the analysis of our algorithms, we obtain average-case lower bounds and compression algorithms for such circuits and worst-case lower bounds for majority votes of such circuits, where all the lower bounds are against the generalized Andreev function. Our average-case lower bounds might be of independent interest in the sense that previous ones for similar circuits with arbitrary symmetric gates rely on communication complexity lower bounds while ours are based on the restriction method.
Cite as

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama. Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 82:1-82:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{sakai_et_al:LIPIcs.MFCS.2016.82,
  author =	{Sakai, Takayuki and Seto, Kazuhisa and Tamaki, Suguru and Teruyama, Junichi},
  title =	{{Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{82:1--82:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.82},
  URN =		{urn:nbn:de:0030-drops-64905},
  doi =		{10.4230/LIPIcs.MFCS.2016.82},
  annote =	{Keywords: exponential time algorithm, circuit complexity, circuit minimization, maximum satisfiability}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.90
Improved Exact Algorithms for Mildly Sparse Instances of Max SAT

Authors: Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
We present improved exponential time exact algorithms for Max SAT. Our algorithms run in time of the form O(2^{(1-mu(c))n}) for instances with n variables and m=cn clauses. In this setting, there are three incomparable currently best algorithms: a deterministic exponential space algorithm with mu(c)=1/O(c * log(c)) due to Dantsin and Wolpert [SAT 2006], a randomized polynomial space algorithm with mu(c)=1/O(c * log^3(c)) and a deterministic polynomial space algorithm with mu(c)=1/O(c^2 * log^2(c)) due to Sakai, Seto and Tamaki [Theory Comput. Syst., 2015]. Our first result is a deterministic polynomial space algorithm with mu(c)=1/O(c * log(c)) that achieves the previous best time complexity without exponential space or randomization. Furthermore, this algorithm can handle instances with exponentially large weights and hard constraints. The previous algorithms and our deterministic polynomial space algorithm run super-polynomially faster than 2^n only if m=O(n^2). Our second results are deterministic exponential space algorithms for Max SAT with mu(c)=1/O((c * log(c))^{2/3}) and for Max 3-SAT with mu(c)=1/O(c^{1/2}) that run super-polynomially faster than 2^n when m=o(n^{5/2}/log^{5/2}(n)) and m=o(n^3/log^2(n)) respectively.
Cite as

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama. Improved Exact Algorithms for Mildly Sparse Instances of Max SAT. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 90-101, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{sakai_et_al:LIPIcs.IPEC.2015.90,
  author =	{Sakai, Takayuki and Seto, Kazuhisa and Tamaki, Suguru and Teruyama, Junichi},
  title =	{{Improved Exact Algorithms for Mildly Sparse Instances of Max SAT}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{90--101},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.90},
  URN =		{urn:nbn:de:0030-drops-55747},
  doi =		{10.4230/LIPIcs.IPEC.2015.90},
  annote =	{Keywords: maximum satisfiability, weighted, polynomial space, exponential space}
}
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