14 citations · 49 across the 14 of their papers we have counts for
14 papers
On Computing the Shapley Value in Bankruptcy Games -llustrated by Rectified Linear Function Game-
Shunta Yamazaki, Tomomi Matsui
In this research, we discuss a problem of calculating the Shapley value in bankruptcy games. We show that the decision problem of computing the Shapley value in bankruptcy games is…
Solving break minimization problems in mirrored double round-robin tournament with QUBO solver
Koichi Fujii, Tomomi Matsui
The break minimization problem is a fundamental problem in sports scheduling. Recently, its quadratic unconstrained binary optimization (QUBO) formulation has been proposed, which…
Dynamic Programming and Linear Programming for Odds Problem
Sachika Kurokawa, Tomomi Matsui
This paper discusses the odds problem, proposed by Bruss in 2000, and its variants. A recurrence relation called a dynamic programming (DP) equation is used to find an optimal stop…
New Formulation for Coloring Circle Graphs and its Application to Capacitated Stowage Stack Minimization
Masato Tanaka, Tomomi Matsui
A circle graph is a graph in which the adjacency of vertices can be represented as the intersection of chords of a circle. The problem of calculating the chromatic number is known…
Monte Carlo Methods for Calculating Shapley-Shubik Power Index in Weighted Majority Games
Yuto Ushioda, Masato Tanaka, Tomomi Matsui
This paper addresses Monte Carlo algorithms for calculating the Shapley-Shubik power index in weighted majority games. First, we analyze a naive Monte Carlo algorithm and discuss t…
Pseudo Polynomial Size LP Formulation for Calculating the Least Core Value of Weighted Voting Games
Masato Tanaka, Tomomi Matsui
In this paper, we propose a pseudo polynomial size LP formulation for finding a payoff vector in the least core of a weighted voting game. The numbers of variables and constraints…
Trading Transforms of Non-weighted Simple Games and Integer Weights of Weighted Simple Games
Akihiro Kawana, Tomomi Matsui
This study investigates simple games. A fundamental research question in this field is to determine necessary and sufficient conditions for a simple game to be a weighted majority…
A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case
Yuko Kuroki, Tomomi Matsui
Transportation networks frequently employ hub-and-spoke network architectures to route flows between many origin and destination pairs. Hub facilities work as switching points for…
Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
Yuko Kuroki, Tomomi Matsui
We consider a single allocation hub-and-spoke network design problem which allocates each non-hub node to exactly one of given hub nodes so as to minimize the total transportation…
Additive Approximation Algorithms for Modularity Maximization
Yasushi Kawase, Tomomi Matsui, Atsushi Miyauchi
The modularity is a quality function in community detection, which was introduced by Newman and Girvan (2004). Community detection in graphs is now often conducted through modulari…
Characterizing a Set of Popular Matchings Defined by Preference Lists with Ties
Tomomi Matsui, Takayoshi Hamaguchi
In this paper, we give a simple characterization of a set of popular matchings defined by preference lists with ties. By employing our characterization, we propose a polynomial tim…
Fractional programming formulation for the vertex coloring problem
Tomomi Matsui, Noriyoshi Sukegawa, Atsushi Miyauchi
We devise a new formulation for the vertex coloring problem. Different from other formulations, decision variables are associated with the pairs of vertices. Consequently, colors w…
Lower Bounds for Bruss' Odds Problem with Multiple Stoppings
Tomomi Matsui, Katsunori Ano
We give asymptotic lower bounds of the value for Bruss' optimal stopping problem with multiple stopping chances. It interestingly consists of the asymptotic threshold values in the…
A 2.75-Approximation Algorithm for the Unconstrained Traveling Tournament Problem
Shinji Imahori, Tomomi Matsui, Ryuhei Miyashiro
A 2.75-approximation algorithm is proposed for the unconstrained traveling tournament problem, which is a variant of the traveling tournament problem. For the unconstrained traveli…