Search Results

Documents authored by Kimura, Kei

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.47
A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems

Authors: Kei Kimura and Kazuhisa Makino

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Linear programming (LP) problems with gainfree Leontief substitution systems have been intensively studied in economics and operations research, and include the feasibility problem of a class of Horn systems, which arises in, e.g., polyhedral combinatorics and logic. This subclass of LP problems admits a strongly polynomial time algorithm, where devising such an algorithm for general LP problems is one of the major theoretical open questions in mathematical optimization and computer science. Recently, much attention has been paid to devising certifying algorithms in software engineering, since those algorithms enable one to confirm the correctness of outputs of programs with simple computations. Devising a combinatorial certifying algorithm for the feasibility of the fundamental class of Horn systems remains open for almost a decade. In this paper, we provide the first combinatorial (and strongly polynomial time) certifying algorithm for LP problems with gainfree Leontief substitution systems. As a by-product, we resolve the open question on the feasibility of the class of Horn systems.
Cite as

Kei Kimura and Kazuhisa Makino. A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kimura_et_al:LIPIcs.ISAAC.2023.47,
  author =	{Kimura, Kei and Makino, Kazuhisa},
  title =	{{A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.47},
  URN =		{urn:nbn:de:0030-drops-193492},
  doi =		{10.4230/LIPIcs.ISAAC.2023.47},
  annote =	{Keywords: linear programming problem, certifying algorithm, Horn system}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.4
Algorithms for Coloring Reconfiguration Under Recolorability Digraphs

Authors: Soichiro Fujii, Yuni Iwamasa, Kei Kimura, and Akira Suzuki

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

Abstract
In the k-Recoloring problem, we are given two (vertex-)colorings of a graph using k colors, and asked to transform one into the other by recoloring only one vertex at a time, while at all times maintaining a proper k-coloring. This problem is known to be solvable in polynomial time if k ≤ 3, and is PSPACE-complete if k ≥ 4. In this paper, we consider a (directed) recolorability constraint on the k colors, which forbids some pairs of colors to be recolored directly. The recolorability constraint is given in terms of a digraph R, whose vertices correspond to the colors and whose arcs represent the pairs of colors that can be recolored directly. We provide algorithms for the problem based on the structure of recolorability constraints R, showing that the problem is solvable in linear time when R is a directed cycle or is in a class of multitrees.
Cite as

Soichiro Fujii, Yuni Iwamasa, Kei Kimura, and Akira Suzuki. Algorithms for Coloring Reconfiguration Under Recolorability Digraphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fujii_et_al:LIPIcs.ISAAC.2022.4,
  author =	{Fujii, Soichiro and Iwamasa, Yuni and Kimura, Kei and Suzuki, Akira},
  title =	{{Algorithms for Coloring Reconfiguration Under Recolorability Digraphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{4:1--4:19},
  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.4},
  URN =		{urn:nbn:de:0030-drops-172896},
  doi =		{10.4230/LIPIcs.ISAAC.2022.4},
  annote =	{Keywords: combinatorial reconfiguration, graph coloring, recolorability, recoloring}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.25
The Fewest Clues Problem of Picross 3D

Authors: Kei Kimura, Takuya Kamehashi, and Toshihiro Fujito

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
Picross 3D is a popular single-player puzzle video game for the Nintendo DS. It is a 3D variant of Nonogram, which is a popular pencil-and-paper puzzle. While Nonogram provides a rectangular grid of squares that must be filled in to create a picture, Picross 3D presents a rectangular parallelepiped (i.e., rectangular box) made of unit cubes, some of which must be removed to construct an image in three dimensions. Each row or column has at most one integer on it, and the integer indicates how many cubes in the corresponding 1D slice remain when the image is complete. It is shown by Kusano et al. that Picross 3D is NP-complete. We in this paper show that the fewest clues problem of Picross 3D is Sigma_2^P-complete and that the counting version and the another solution problem of Picross 3D are #P-complete and NP-complete, respectively.
Cite as

Kei Kimura, Takuya Kamehashi, and Toshihiro Fujito. The Fewest Clues Problem of Picross 3D. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kimura_et_al:LIPIcs.FUN.2018.25,
  author =	{Kimura, Kei and Kamehashi, Takuya and Fujito, Toshihiro},
  title =	{{The Fewest Clues Problem of Picross 3D}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.25},
  URN =		{urn:nbn:de:0030-drops-88168},
  doi =		{10.4230/LIPIcs.FUN.2018.25},
  annote =	{Keywords: Puzzle, computational complexity, fewest clues problem}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.51
Optimal Matroid Partitioning Problems

Authors: Yasushi Kawase, Kei Kimura, Kazuhisa Makino, and Hanna Sumita

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

Abstract
This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given a finite set E and k weighted matroids (E, \mathcal{I}_i, w_i), i = 1, \dots, k, and our task is to find a minimum partition (I_1,\dots,I_k) of E such that I_i \in \mathcal{I}_i for all i. For each objective function, we give a polynomial-time algorithm or prove NP-hardness. In particular, for the case when the given weighted matroids are identical and the objective function is the sum of the maximum weight in each set (i.e., \sum_{i=1}^k\max_{e\in I_i}w_i(e)), we show that the problem is strongly NP-hard but admits a PTAS.
Cite as

Yasushi Kawase, Kei Kimura, Kazuhisa Makino, and Hanna Sumita. Optimal Matroid Partitioning Problems. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.ISAAC.2017.51,
  author =	{Kawase, Yasushi and Kimura, Kei and Makino, Kazuhisa and Sumita, Hanna},
  title =	{{Optimal Matroid Partitioning Problems}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{51:1--51:13},
  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.51},
  URN =		{urn:nbn:de:0030-drops-82712},
  doi =		{10.4230/LIPIcs.ISAAC.2017.51},
  annote =	{Keywords: Matroids, Partitioning problem, PTAS, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.613
Trichotomy for Integer Linear Systems Based on Their Sign Patterns

Authors: Kei Kimura and Kazuhisa Makino

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
In this paper, we consider solving the integer linear systems, i.e., given a matrix A in R^{m*n}, a vector b in R^m, and a positive integer d, to compute an integer vector x in D^n such that Ax <= b, where m and n denote positive integers, R denotes the set of reals, and D={0,1,..., d-1}. The problem is one of the most fundamental NP-hard problems in computer science. For the problem, we propose a complexity index h which is based only on the sign pattern of A. For a real r, let ILS_=(r) denote the family of the problem instances I with h(I)=r. We then show the following trichotomy: - ILS_=(r) is linearly solvable, if r < 1, - ILS_=(r) is weakly NP-hard and pseudo-polynomially solvable, if r = 1, and - ILS_=(r) is strongly NP-hard, if r > 1. This, for example, includes the existing results that quadratic systems and Horn systems can be solved in pseudo-polynomial time.
Cite as

Kei Kimura and Kazuhisa Makino. Trichotomy for Integer Linear Systems Based on Their Sign Patterns. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 613-623, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{kimura_et_al:LIPIcs.STACS.2012.613,
  author =	{Kimura, Kei and Makino, Kazuhisa},
  title =	{{Trichotomy for Integer Linear Systems Based on Their Sign Patterns}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{613--623},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.613},
  URN =		{urn:nbn:de:0030-drops-34367},
  doi =		{10.4230/LIPIcs.STACS.2012.613},
  annote =	{Keywords: Integer linear system, Sign pattern, Complexity index, TVPI system, Horn system}
}
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