4 citations · 9 across the 14 of their papers we have counts for
18 papers
A Matroid Generalization of Weighted Popular Matching: Characterization and Algorithm
Yuni Iwamasa, Yusuke Kobayashi, Ryoga Mahara +1
We study a problem that unifies two major generalizations of popular matchings in the one-sided preference model. In a bipartite graph in which each vertex, or applicant, on one si…
On the Equivalence of the Graph-Structural and Optimization-Based Characterizations of Popular Matchings
Yuga Kanaya, Kenjiro Takazawa
Popular matchings provide a model of matching under preferences in which a solution corresponds to a Condorcet winner in voting systems. In a bipartite graph in which the vertices…
A Unified Model of Congestion Games with Priorities: Two-Sided Markets with Ties, Finite and Non-Affine Delay Functions, and Pure Nash Equilibria
Kenjiro Takazawa
The study of equilibrium concepts in congestion games and two-sided markets with ties has been a primary topic in game theory, economics, and computer science. Ackermann, Goldberg,…
Popular Maximum-Utility Matchings with Matroid Constraints
Gergely Csáji, Tamás Király, Kenjiro Takazawa +1
We investigate weighted settings of popular matching problems with matroid constraints. The concept of popularity was originally defined for matchings in bipartite graphs, where ve…
Pure Nash Equilibria in Weighted Congestion Games with Complementarities and Beyond
Kenjiro Takazawa
Congestion games offer a primary model in the study of pure Nash equilibria in non-cooperative games, and a number of generalized models have been proposed in the literature. One l…
Finding a Maximum Restricted -Matching via Boolean Edge-CSP
Yuni Iwamasa, Yusuke Kobayashi, Kenjiro Takazawa
The problem of finding a maximum -matching without short cycles has received significant attention due to its relevance to the Hamilton cycle problem. This problem is generalize…
A Faster Deterministic Approximation Algorithm for TTP-2
Yuga Kanaya, Kenjiro Takazawa
The traveling tournament problem (TTP) is to minimize the total traveling distance of all teams in a double round-robin tournament. In this paper, we focus on TTP-2, in which each…
Finding popular branchings in vertex-weighted digraphs
Kei Natsui, Kenjiro Takazawa
Popular matchings have been intensively studied recently as a relaxed concept of stable matchings. By applying the concept of popular matchings to branchings in directed graphs, Ka…
Notes on Equitable Partitions into Matching Forests in Mixed Graphs and into -branchings in Digraphs
Kenjiro Takazawa
An equitable partition into branchings in a digraph is a partition of the arc set into branchings such that the sizes of any two branchings differ at most by one. For a digraph who…
Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications
Yuni Iwamasa, Kenjiro Takazawa
For two matroids and with the same ground set and two cost functions and on , we consider the problem of finding bases of and of…
A Note on a Nearly Uniform Partition into Common Independent Sets of Two Matroids
Satoru Fujishige, Kenjiro Takazawa, Yu Yokoi
The present note is a strengthening of a recent paper by K. Takazawa and Y. Yokoi (A generalized-polymatroid approach to disjoint common independent sets in two matroids, Discrete…
M-convexity of the minimum-cost packings of arborescences
Kenjiro Takazawa
The aim of this paper is to reveal the discrete convexity of the minimum-cost packings of arborescences and branchings. We first prove that the minimum-cost packings of disjoint $k…
A Generalized-Polymatroid Approach to Disjoint Common Independent Sets in Two Matroids
Kenjiro Takazawa, Yu Yokoi
In this paper, we investigate the classes of matroid intersection admitting a solution for the problem of partitioning the ground set into common independent sets, where $E…
The -bibranching Problem: TDI System, Packing, and Discrete Convexity
Kenjiro Takazawa
In this paper, we introduce the -bibranching problem in digraphs, which is a common generalization of the bibranching and -branching problems. The bibranching problem, introd…
The -branching problem in digraphs
Naonori Kakimura, Naoyuki Kamiyama, Kenjiro Takazawa
In this paper, we introduce the concept of -branchings in digraphs, which is a generalization of branchings serving as a counterpart of -matchings. Here is a positive int…
Excluded -factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-matchings, and Matroids
Kenjiro Takazawa
We propose a framework for optimal -matchings excluding the prescribed -factors in bipartite graphs. The proposed framework is a generalization of the nonbipartite matching p…
Relationship of Two Formulations for Shortest Bibranchings
Kazuo Murota, Kenjiro Takazawa
The shortest bibranching problem is a common generalization of the minimum-weight edge cover problem in bipartite graphs and the minimum-weight arborescence problem in directed gra…
Posimodular Function Optimization
Toshimasa Ishii, Kazuhisa Makino
Given a posimodular function on a finite set , we consider the problem of finding a nonempty subset of that minimizes . Posimodular functio…