| 1. |
Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Akira Suzuki, Algorithms for coloring reconfiguration under recolorability digraphs, Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), 10.4230/LIPIcs.ISAAC.2022.4, 4:1-4:19, 2022.12. |
| 2. |
Kei Kimura, Kotaro Nakayama, Neighborhood Persistency of the Linear Optimization Relaxation of Integer Linear Optimization, Lecture Notes in Computer Science, 10.1007/978-3-031-18530-4_23, 312-323, 2022.11. |
| 3. |
Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Quantaloidal approach to constraint satisfaction, Proceedings of the 4th International Conference on Applied Category Theory (ACT 2021), EPTCS 372, 289-305, 2022.10. |
| 4. |
Kei Kimura, Kotaro Nakayama, Neighborhood persistency of the linear optimization relaxation of integer linear optimization, CoRR, 10.1007/978-3-031-18530-4_23, arXiv:2203.04557, 312-323, 2022.03. |
| 5. |
Kei Kimura, Takuya Kamehashi, Computational complexity of three-dimensional discrete tomography with missing data, Japan Journal of Industrial and Applied Mathematics, 10.1007/s13160-021-00464-0, 38, 3, 823-858, 2021.09. |
| 6. |
Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Quantaloidal approach to constraint satisfaction., CoRR, abs/2107.01778, 2021.07. |
| 7. |
Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita, Optimal Matroid Partitioning Problems, Algorithmica, 10.1007/s00453-021-00797-9, 83, 6, 1653-1676, 2021.06. |
| 8. |
Kei Kimura, Akira Suzuki, Trichotomy for the reconfiguration problem of integer linear systems., Theor. Comput. Sci., 10.1016/j.tcs.2020.12.025, 856, 88-109, 2021.02. |
| 9. |
Kei KIMURA, Stronger Hardness Results on the Computational Complexity of Picross 3D, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 10.1587/transfun.2019eap1101, E103.A, 4, 668-676, 2020.04. |
| 10. |
Kei Kimura, Akira Suzuki, Trichotomy for the Reconfiguration Problem of Integer Linear Systems., Proceedings of the 14th International Conference and Workshops on Algorithms and Computation, LNCS 12049, 10.1007/978-3-030-39881-1_29, 336-341, 2020.03. |
| 11. |
Higuchi Yuta, Kimura Kei, NP-Completeness of Fill-a-Pix and Sigma(P)(2)-Completeness of Its Fewest Clues Problem, IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 10.1587/transfun.E102.A.1490, E102A, 11, 1490-1496, 2019.11. |
| 12. |
Kei Kimura, Akira Suzuki, Trichotomy for the reconfiguration problem of integer linear systems., CoRR, abs/1911.02786, 2019.11. |
| 13. |
Toshihiro Fujito, Kei Kimura, Yuki Mizuno, Approximating Partially Bounded Degree Deletion on Directed Graphs, Journal of Graph Algorithms and Applications, 10.7155/jgaa.00511, 23, 5, 759-780, 2019.10. |
| 14. |
Takuya Tamori, Kei Kimura, A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition., WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Guwahati, India, February 27 - March 2, 2019, Proceedings, 10.1007/978-3-030-10564-8_17, 209-218, 2019.02. |
| 15. |
Kei Kimura, Kazuhisa Makino, Linear Satisfiability Preserving Assignments (Extended Abstract)., Proceedings of the 27th International Joint Conference on Artificial Intelligence, 10.24963/ijcai.2018/797, 5622-5626, 2018.07. |
| 16. |
Norie Fu, Naonori Kakimura, Kei Kimura, Vorapong Suppakitpaisarn, Maximum lifetime coverage problem with battery recovery effect, Sustainable Computing: Informatics and Systems, 10.1016/j.suscom.2018.02.007, 18, 1-13, 2018.06. |
| 17. |
Kei Kimura, Takuya Kamehashi, Toshihiro Fujito, The Fewest Clues Problem of Picross 3D., 9th International Conference on Fun with Algorithms, FUN 2018, June 13-15, 2018, La Maddalena, Italy, 25:1-25:13, 2018.06. |
| 18. |
Toshihiro Fujito, Kei Kimura, Yuki Mizuno, Approximating Partially Bounded Degree Deletion on Directed Graphs, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10.1007/978-3-319-75172-6_4, 10755, 32-43, 2018.03, The Bounded Degree Deletion problem (BDD) is that of computing a minimum vertex set in a graph G=(V,E) with degree bound b: V=Z+, such that, when it is removed from G, the degree of any remaining vertex v is no larger than b(v). It is a classic problem in graph theory and various results have been obtained including an approximation ratio of 2+In bmax [30], where bmax is the maximum degree bound. This paper considers BDD on directed graphs containing unbounded vertices, which we call Partially Bounded Degree Deletion (PBDD). Despite such a natural generalization of standard BDD, it appears that PBDD has never been studied and no algorithmic results are known, approximation or parameterized. It will be shown that (1) in case all the possible degrees are bounded, in-degrees by and out-degrees by, BDD on directed graphs can be approximated within, and (2) although it becomes NP-hard to approximate PBDD better than bmax (even on undirected graphs) once unbounded vertices are allowed, it can be within when only in-degrees (and none of out-degrees) are partially bounded by b.. |
| 19. |
Kei Kimura, Kazuhisa Makino, Autark assignments of Horn CNFs, Japan Journal of Industrial and Applied Mathematics, 10.1007/s13160-017-0284-6, 35, 1, 297-309, 2018.03, In this paper, we consider autark and linear autark assignments of Horn CNFs. We first study maximal autark assignments of Horn CNFs and devise a linear time algorithm of computing these assignments. This complements the previous work by Marek which reveals the properties of minimal autark assignments of Horn CNFs. We then consider linear autark assignments of Horn CNFs and give a combinatorial characterization of the existence of such an assignment. By making use of this characterization, we devise a linear time algorithm of finding linear autark assignments of Horn CNFs.. |
| 20. |
Kei Kimura, Kazuhisa Makino, Linear Satisfiability Preserving Assignments, Journal of Artificial Intelligence Research, 10.1613/jair.5658, 61, 291-321, 2018.02, In this paper, we study several classes of satisfiability preserving assignments to the constraint satisfaction problem (CSP). In particular, we consider fixable, autark and satisfying assignments. Since it is in general NP-hard to find a nontrivial (i.e., nonempty) satisfiability preserving assignment, we introduce linear satisfiability preserving assignments, which are defined by polyhedral cones in an associated vector space. The vector space is obtained by the identification, introduced by Kullmann, of assignments with real vectors. We consider arbitrary polyhedral cones, where only restricted classes of cones for autark assignments are considered in the literature. We reveal that cones in certain classes are maximal as a convex subset of the set of the associated vectors, which can be regarded as extensions of Kullmann's results for autark assignments of CNFs. As algorithmic results, we present a pseudo-polynomial time algorithm that computes a linear fixable assignment for a given integer linear system, which implies the well known pseudo-polynomial solvability for integer linear systems such as two-variable-per-inequality (TVPI), Horn and q-Horn systems..  |
| 21. |
Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita, Optimal matroid partitioning problems, Leibniz International Proceedings in Informatics, LIPIcs, 10.4230/LIPIcs.ISAAC.2017.51, 92, 51:1-51:13, 2017.12, This paper studies optimal matroid partitioning problems for various objective functions. Inthe problem, we are given a finite set E and k weighted matroids (E, Ii,wi), i = 1, . . . , k, andour task is to find a minimum partition (I1, . . . , Ik) of E such that Ii 2 Ii for all i. For eachobjective function, we give a polynomial-Time algorithm or prove NP-hardness. In particular, forthe case when the given weighted matroids are identical and the objective function is the sum ofthe maximum weight in each set (i.e.,Pk i=1 maxe2Ii wi(e)), we show that the problem is strongly NP-hard but admits a PTAS.. |
| 22. |
Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita, Optimal Matroid Partitioning Problems, CoRR, abs/1710.00950, 2017.10. |
| 23. |
Kei Kimura, Kazuhisa Makino, Trichotomy for integer linear systems based on their sign patterns, DISCRETE APPLIED MATHEMATICS, 10.1016/j.dam.2015.07.004, 200, 67-78, 2016.02, In this paper, we consider solving the integer linear systems, i.e., given a matrix A is an element of R-mxn a vector b is an element of R-m, and a positive integer d, to compute an integer vector x is an element of D-n such that Ax >= b or to determine the infeasibility of the system, 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 eta which depends only on the sign pattern of A. For a real gamma, let ILS(gamma) denote the family of the problem instances I with eta(I) = gamma. We then show the following trichotomy:
ILS(gamma) is solvable in linear time, if gamma ILS(gamma) is weakly NP-hard and pseudo-polynomially solvable, if gamma = 1,
ILS(gamma) is strongly NP-hard, if gamma > 1.
This, for example, includes the previous results that Horn systems and two-variable-perinequality (TVPI) systems can be solved in pseudo-polynomial time. (C) 2015 Elsevier B.V. All rights reserved.. |
| 24. |
Norie Fu, Vorapong Suppakitpaisarn, Kei Kimura, Naonori Kakimura, Maximum Lifetime Coverage Problems with Battery Recovery Effects, 2014 IEEE GLOBAL COMMUNICATIONS CONFERENCE (GLOBECOM 2014), 10.1109/GLOCOM.2014.7036794, 118-124, 2014.12, Scheduling sensors to prolong the lifetime of covering targets in the field is one of the central problems in wireless sensor networks. This problem, called the maximum lifetime coverage problem (MLCP), can be formulated as a linear programming problem with exponential size, and has a constant-factor approximation algorithm. In reality, however, batteries of sensors have recovery effects, which is a phenomenon that the deliverable energy in batteries can be replenished by itself if it is left idling for sufficient duration. Thanks to that effects, we can obtain much longer lifetime of sensors if each sensor is forced to take a sleep at some interval. In this paper, we introduce two models that extend the MLCP, incorporating battery recovery effects. The first model represents battery recovery effects in a deterministic way, while the second one uses a probabilistic model to imitate the effects. We then propose efficient algorithms that work for both models by extending approximation algorithms for the original MLCP. Numerical experiments show that the lifetime of our schedule is 10-40% longer than one without battery recovery effects.. |
| 25. |
Kei Kimura, Kazuhisa Makino, Satisfiability Preserving Assignments and Their Local and Linear Forms, MATHEMATICAL ENGINEERING TECHNICAL REPORTS, 2014-34, University of Tokyo, 2014.11. |
| 26. |
Kei Kimura, Kazuhisa Makino, Trichotomy for Integer Linear Systems Based on Their Sign Patterns, 29TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, (STACS 2012), 10.4230/LIPIcs.STACS.2012.613, 14, 613-623, 2012.03, In this paper, we consider solving the integer linear systems, i.e., given a matrix A is an element of R-mxn, a vector b is an element of R-m, and a positive integer d, to compute an integer vector x is an element of 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 eta which is based only on the sign pattern of A. For a real gamma, let ILS=(gamma) denote the family of the problem instances I with eta(I) = gamma. We then show the following trichotomy:
ILS=(gamma) is linearly solvable, if gamma ILS=(gamma) is weakly NP-hard and pseudo-polynomially solvable, if gamma = 1, and
ILS=(gamma) is strongly NP-hard, if gamma > 1.
This, for example, includes the existing results that quadratic systems and Horn systems can be solved in pseudo-polynomial time.. |
| 27. |
Kei Kimura, Kazuhisa Makino, Trichotomy for Integer Linear Systems Based on Their Sign Patterns, MATHEMATICAL ENGINEERING TECHNICAL REPORTS, METR 2012-2, University of Tokyo, 2012.01. |
