6 papers
UTVPI-representable integer point sets: discrete convexity, polymorphisms, and pairwise closure
Kei Kimura, Kazuhisa Makino, Shota Yamada +1
We study subsets of the integer lattice represented by single-variable-per-inequality (SVPI), difference-constraint (DC), unit two-variable-per-inequality (UTVPI), and two-variable…
Characterizing the integer points in 2-decomposable polyhedra by closedness under operations
Kei Kimura, Kazuhisa Makino, Shota Yamada +1
Characterizing the solution sets in a problem by closedness under operations is recognized as one of the key aspects of algorithm development, especially in constraint satisfaction…
A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems
Kei Kimura, Kazuhisa Makino
Linear programming (LP) problems with gainfree Leontief substitution systems have been intensively studied in economics and operations research, and include the feasibility problem…
Neighborhood persistency of the linear optimization relaxation of integer linear optimization
Kei Kimura, Kotaro Nakayama
For an integer linear optimization (ILO) problem, persistency of its linear optimization (LO) relaxation is a property that for every optimal solution of the relaxation that assign…
Quantaloidal Approach to Constraint Satisfaction
Soichiro Fujii, Yuni Iwamasa, Kei Kimura
The constraint satisfaction problem (CSP) is a computational problem that includes a range of important problems in computer science. We point out that fundamental concepts of the…
Optimal Matroid Partitioning Problems
Yasushi Kawase, Kei Kimura, Kazuhisa Makino +1
This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given a finite set and weighted matroids $(E, \mathcal{I}_i…