5 citations · 9 across the 12 of their papers we have counts for
13 papers
Two Proofs of a Structural Theorem of Decreasing Minimization on Integrally Convex Sets
Kazuo Murota, Akihisa Tamura
This paper gives two different proofs to a structural theorem of decreasing minimization (lexicographic optimization) on integrally convex sets. The theorem states that the set of…
Note on Minkowski Summation and Unimodularity in Discrete Convex Analysis
Kazuo Murota, Akihisa Tamura
This short note gives an elementary alternative proof for a theorem of Danilov and Koshevoy on Minkowski summation and unimodularity in discrete convex analysis. It is intended to…
Towards Optimal Subsidy Bounds for Envy-freeable Allocations
Yasushi Kawase, Kazuhisa Makino, Hanna Sumita +2
We study the fair division of indivisible items with subsidies among agents, where the absolute marginal valuation of each item is at most one. Under monotone valuations (where…
Decomposition of an Integrally Convex Set into a Minkowski Sum of Bounded and Conic Integrally Convex Sets
Kazuo Murota, Akihisa Tamura
Every polyhedron can be decomposed into a Minkowski sum (or vector sum) of a bounded polyhedron and a polyhedral cone. This paper establishes similar statements for some classes of…
Shapley-Folkman-type Theorem for Integrally Convex Sets
Kazuo Murota, Akihisa Tamura
The Shapley-Folkman theorem is a statement about the Minkowski sum of (non-convex) sets, expressing the closeness of the Minkowski sum to convexity in a quantitative manner. This p…
Recent Progress on Integrally Convex Functions
Kazuo Murota, Akihisa Tamura
Integrally convex functions constitute a fundamental function class in discrete convex analysis, including M-convex functions, L-convex functions, and many others. This paper aims…
Discrete Fenchel Duality for a Pair of Integrally Convex and Separable Convex Functions
Kazuo Murota, Akihisa Tamura
Discrete Fenchel duality is one of the central issues in discrete convex analysis. The Fenchel-type min-max theorem for a pair of integer-valued M-natural-convex functions generali…
Fair and Truthful Mechanism with Limited Subsidy
Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase +5
The notion of \emph{envy-freeness} is a natural and intuitive fairness requirement in resource allocation. With indivisible goods, such fair allocations are unfortunately not guara…
Directed Discrete Midpoint Convexity
Akihisa Tamura, Kazuya Tsurumi
For continuous functions, midpoint convexity characterizes convex functions. By considering discrete versions of midpoint convexity, several types of discrete convexities of functi…
Integrality of Subgradients and Biconjugates of Integrally Convex Functions
Kazuo Murota, Akihisa Tamura
Integrally convex functions constitute a fundamental function class in discrete convex analysis. This paper shows that an integer-valued integrally convex function admits an integr…
Discrete Midpoint Convexity
Satoko Moriguchi, Kazuo Murota, Akihisa Tamura +1
For a function defined on a convex set in a Euclidean space, midpoint convexity is the property requiring that the value of the function at the midpoint of any line segment is not…
Scaling, Proximity, and Optimization of Integrally Convex Functions
Satoko Moriguchi, Kazuo Murota, Akihisa Tamura +1
In discrete convex analysis, the scaling and proximity properties for the class of L-convex functions were established more than a decade ago and have been used to desig…
Trading Networks with Bilateral Contracts
Tamás Fleiner, Zsuzsanna Jankó, Akihisa Tamura +1
We consider a model of matching in trading networks in which firms can enter into bilateral contracts. In trading networks, stable outcomes, which are immune to deviations of arbit…