[3] Dash Associates, XPRESS-MP User Guide and Reference Manual, Dash Associates, (2008)
Ayami Suzuka, Ryuhei Miyashiro, Akiko Yoshise, Tomomi Matsui, A. Avidor, U. Zwick, ...
[4] D. de Werra, Geography, games and graphs, Discrete Appl. Math. 2 (1980) 327–337. [5] K. Easton, G.L. Nemhauser and M.A. Trick, Solving the travelling tournament problem: a combined integer...
Linear Time Approximation Algorithm for Multicoloring Lattice Graphs with Diagonals (2008)
Yuichiro Miyamoto, Tomomi Matsui
Let P be a subset of 2-dimensional integer lattice points P = {1, 2,..., m}× {1, 2,..., n} ⊆ Z 2. We consider the graph GP with vertex set P satisfying that two vertices in P are adjacent if and...
Aloupis, G., and others 1 Algorithms for Computing Geometric Measures of Melodic Similarity (2008)
Greg Aloupis, Thomas Fevens, Antonio Mesa, Yurai Nuñez, Stefan Langerman, Tomomi Matsui, ...
We have all heard numerous melodies, whether they come from commercial jingles, jazz ballads, operatic aria, or any of a variety of different sources. How a human detects similarities in melodies has...
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa
Rappaport k Godfried Toussaint \Lambda Abstract Consider two orthogonal closed chains on a cylinder. The chains are monotone with respect to the angle \Theta. We wish to rigidly move one chain so...
Ayami Suzuka, Ryuhei Miyashiro, Akiko Yoshise, Tomomi Matsui
Abstract: Suppose that we have a timetable of a round-robin tournament with a number of teams, and distances between their homes. The home-away assignment problem is to find a home-away assignment...
SUMMARY In this paper, we propose a new counting scheme for m * n contingency tables. Our scheme is a modification of Dyer and Greenhill's scheme for two rowed contingency tables [5]. We can...
Efficient Algorithms for the Electric Power Transaction Problem (2008)
Abstract. We present two efficient algorithms for solving the electric power transaction problem. The electric power transaction problem appears when maximizing the social benefit on electric power...
Perfectness and Imperfectness of the kth Power of Lattice Graphs (2008)
Yuichiro Miyamoto, Tomomi Matsui
Abstract. Given a pair of non-negative integers m and n, S(m, n) denotes a square lattice graph with a vertex set {0, 1, 2,...,m − 1} × {0, 1, 2,...,n − 1}, where a pair of two vertices is...
New approximation algorithms for MAX 2SAT and MAX DICUT (2008)
Abstract We propose a 0.935-approximation algorithm for MAX 2SAT and a 0.863-approximation algorithm for MAX DICUT. The approximation ratios improve upon the recent results of Zwick, which are equal...
Minimizing the Carry-Over Effects Value in a Round-Robin Tournament (2008)
Ryuhei Miyashiro, Tomomi Matsui
In this abstract, we deal with the problem of minimizing the carry-over effects value in a round-robin tournament. The carry-over effects value is an index of quality of a round-robin tournament...
Constructive Algorithms for the Constant (2008)
Distance Traveling Tournament, Nobutomo Fujiwara, Shinji Imahori, Tomomi Matsui, Ryuhei Miyashiro
defined by the number of moves of the team between team sites. Consecutive away games for a team constitute a road trip; consecutive home games are a home stand. The length of a road trip or home...
Calculating Power Indices of Weighted Majority Games (2007)
Tomomi Matsui, Eji N $ng$u$nitj
this paper, we discuss the problems for calculating ShapleyShubik index, Banzhaf index and Deegan-Packel index of weighted majority games.
Enumeration Algorithm for the Edge Coloring Problem on Bipartite Graphs (2007)
. In this paper, we propose an algorithm for finding all the edge colorings in bipartite graphs. Our algorithm requires O(T (n; m;1) + K minfn 2 + m; T (n; m;1)g) time and O(m1) space, where n...
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Godfried Toussaint
Consider two orthogonal closed chains on a cylinder. The chains are monotone with respect to the angle . We wish to rigidly move one chain so that the total area between the two chains is minimized....
Approximate counting scheme for m × n contingency tables (2007)
Shuji Kijima, Shuji Kijima, Tomomi Matsui, Tomomi Matsui
Abstract. In this paper, we propose a new counting scheme for m × n contingency tables. Our scheme is a modification of Dyer and Greenhill’s scheme for two rowed contingency tables [5]. We can...
for Perfect Complements * (2007)
Tomomi Matsui, Takahiro Watanabe, Tomomi Matsui I
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
Abstract. In this paper, we consider multi-object auctions in which each bidder has a positive reservation value for only one special subset of objects, called a necessary bundle. In the auction,...
Abstract. In this paper, we consider multi-object auctions in which each bidder has a positive reservation value for only one special subset of objects, called a necessary bundle. In the auction,...
Linear Time Approximation Algorithm for Multicoloring Lattice Graphs with Diagonals (2007)
Yuichiro Miyamoto, Yuichiro Miyamoto, Tomomi Matsui, Tomomi Matsui
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
Ryuhei Miyashiro, Ryuhei Miyashiro, Tomomi Matsui, Tomomi Matsui
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling (2006)
Ayami Suzuka †a, Ryuhei Miyashiro, Akiko Yoshise, Tomomi Matsui
SUMMARY Suppose that we have a timetable of a round-robin tournament with a number of teams, and distances among their homes. The home-away assignment problem is to find a home-away assignment that...
Semidefinite programming based approaches to the break minimization problem (2006)
Ayami Suzuka, Ryuhei Miyashiro, Akiko Yoshise, Tomomi Matsui
For a given schedule of a round-robin tournament and a matrix of distances between homes of teams, an optimal home-away assignment problem is to find a home-away assignment that minimizes the total...
Semidefinite programming based approaches to the break minimization problem (2006)
Ryuhei Miyashiro, Ryuhei Miyashiro, Tomomi Matsui, Tomomi Matsui
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
Semidefinite programming based approaches to the break minimization problem (2006)
Ryuhei Miyashiro, Tomomi Matsui
This paper considers the break minimization problem in sports timetabling. The problem is to find, under a given timetable of a round-robin tournament, a home-away assignment that minimizes the...
Semidefinite programming based approaches to the break minimization problem (2006)
Ayami Suzuka, Ryuhei Miyashiro, Akiko Yoshise, Tomomi Matsui
Abstract. For a given schedule of a round-robin tournament and a matrix of distances between homes of teams, an optimal home-away assignment problem is to find a home-away assignment that minimizes...
Semidefinite programming based approaches to the break minimization problem (2006)
Metr August, Ryuhei Miyashiro, Ryuhei Miyashiro, Tomomi Matsui, Tomomi Matsui
notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each...
Semidefinite programming based approaches to the break minimization problem (2006)
Ryuhei Miyashiro, Tomomi Matsui
This paper considers the break minimization problem in sports timetabling. The problem is to find, under a given timetable of a round-robin tournament, a home-away assignment that minimizes the...
Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling (2006)
SUZUKA, Ayami, MIYASHIRO, Ryuhei, YOSHISE, Akiko, MATSUI, Tomomi
Suppose that we have a timetable of a round-robin tournament with a number of teams, and distances among their homes. The home-away assignment problem is to find a home-away assignment that minimizes...
Minimum Span Channel Assignment Problems (2005)
Yuichiro Miyamoto, Tomomi Matsui, Yuichiro Miyamoto, Tomomi Matsui
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
2.1 Logarithmic Separable Concave Function......................... 2 (2005)
Shuji Kijima, Tomomi Matsui, Main Results
In this paper, we are concerned with random sampling of an n dimensional integral point on an (n − 1) dimensional simplex according to a multivariate discrete distribution. We employ sampling via...
Algorithms for Computing Geometric Measures of Melodic Similarity ∗ (2004)
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nuñez, ...
Consider two orthogonal closed chains on a cylinder. These chains are monotone with respect to the tangential Θ direction. We wish to rigidly move one chain so that the total area between the two is...
Multicoloring Unit Disk Graphs on Triangular Lattice Points (2004)
Yuichiro Miyamoto, Yuichiro Miyamoto, Tomomi Matsui, Tomomi Matsui
Given a pair of non-negative integers m and n, P (m, n) denotes a subset of 2-dimensional triangular lattice points defined by P (m, n) ...
Ryuhei Miyashiro, Tomomi Matsui
www.elsevier.com/locate/dsw A polynomial-time algorithm to find an equitable home–away assignment �
Computing a geometric measure of the similarity between two melodies (2003)
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nuñez, ...
Consider two orthogonal closed chains on a cylinder. The chains are monotone with respect to the angle Θ. We wish to rigidly move one chain so that the total area between the two chains is...
Hideya Iwasaki, Ryuhei Miyashiro, Ryuhei Miyashiro, Tomomi Matsui, Tomomi Matsui
Abstract. In sports timetabling, finding feasible pattern sets for a round robin tournament is a significant problem. Although this problem has been tackled in several ways, good characterization of...
Polynomial Time Perfect Sampler for Discretized Dirichlet Distribution (2003)
Tomomi Matsui, Tomomi Matsui, Shuji Kijima, Shuji Kijima
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
Shuji Kijima, Shuji Kijima, Tomomi Matsui, Tomomi Matsui
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
Computing a Geometric Measure of the Similarity between two Melodies (2003)
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nunez, ...
Consider two orthogonal closed chains on a cylinder. The chains are monotone with respect to the angle . We wish to rigidly move one chain so that the total area between the two chains is minimized....
Polynomial Time Perfect Sampler for Discretized Dirichlet Distribution (2003)
version: April 24th Abstract. In this paper, we propose a perfect (exact) sampling algorithm according to a discretized Dirichlet distribution. Our algorithm is a monotone coupling from the past...
Polynomial Time Approximate Sampler for Discretized Dirichlet Distribution (2003)
Tomomi Matsui, Mitsuo Motoki, Naoyuki Kamatani
Abstract. In this paper, we propose a Markov chain for sampling a random vector distributed according to a discretized Dirichlet distribution. We show that our Markov chain is rapidly mixing, that...
This paper proposes a polynomial time perfect (exact) sampling algorithm for 2 × n contingency tables. The algorithm is based on monotone coupling from the past (monotone CFTP) algorithm. The...
Ryuhei Miyashiro, Hideya Iwasaki, Tomomi Matsui
Abstract. In sports timetabling, creating an appropriate timetable for a round-robin tournament with home–away assignment is a significant problem. To solve this problem, we need to construct...
Polynomial Time Approximate Sampler for Discretized Dirichlet Distribution (2003)
Tomomi Matsui, Mitsuo Motoki, Naoyuki Kamatani
Abstract. In this paper, we propose a Markov chain for sampling a random vector distributed according to a discretized Dirichlet distribution. We show that our Markov chain is rapidly mixing, that...
Asano, Tetsuo, Fujikawa, Naoki, Katoh, Naoki, Matsui, Tomomi, Nagamochi, Hiroshi, Tokuyama, Takeshi, ...
0.863-Approximation Algorithm for MAX DICUT (2001)
In this paper, we propose 0.863-approximation algorithm for MAX DICUT. The approximation ratio is better than the previously known result by Zwick, which is equal to 0.8596434254. The algorithm...
0.935-Approximation Randomized Algorithm for MAX 2SAT and Its Derandomization (2001)
Abstract. In this paper, we propose 0.935-approximation algorithm for MAX 2SAT. The approximation ratio is better than the previously known result by Zwick, which is equal to 0.93109. The algorithm...
Peg solitaire is a one player game using pegs and a board with some holes. The game is classical, and nowadays sold in many parts of the world under the trade nameof Hi Q. In this paper, we dealt...
Tomomi Matsui, Takahiro Watanabe
Abstract. In this paper, we consider multi-object auctions in which each bidder has a positive reservation value for only one special subset of objects, called a necessary bundle. In the auction,...
. Unit disk graphs are the intersection graphs of equal sized circles in the plane. In this paper, we consider the maximum independent set problems on unit disk graphs. When the given unit disk graph...
A Minimum Taxrate Core Allocation of Bin Packing Games (1999)
This paper deals with a class of cooperative games called bin packing games. We give a precise definition of bin packing games in the next section. In [1], Faige and Kern showed that every bin...
NP-completeness for Calculating Power Indices of Weighted Majority Games (1998)
: In this paper, we prove that both problems for calculating the Banzhaf power index and the Shapley-Shubik power index for weighted majority games are NP-complete. Keywords: weighted majority game,...
Optimality of Mixed-level Supersaturated Designs (1998)
Shu Yamada, Shu Yamada, Tomomi Matsui, Tomomi Matsui
Supersaturated design is an important aspect of experimental design. Several properties of supersaturated designs have been obtained that enable supersaturated design to be constructed while...
A Flexible Algorithm For Generating All The Spanning Trees In Undirected Graphs (1997)
. In this paper, we propose an algorithm for generating all the spanning trees in undirected graphs. The algorithm requires O(n + m + øn) time where the given graph has n vertices, m edges and ø...
A Fast Bipartite Network Flow Algorithm for Selective Assembly (1997)
Satoru Iwata, Tomomi Matsui, S. Thomas Mccormick
Abstract Bipartite network flow problems naturally arise in applications such as selective assembly and preemptive scheduling. This paper presents fast algorithms for these problems that take...
A Fast Bipartite Network Flow Algorithm for Selective Assembly (1997)
Satoru Iwata, Tomomi Matsui, S. Thomas Mccormick
Bipartite network flow problems naturally arise in applications such as selective assembly and preemptive scheduling. This paper presents fast algorithms for these problems that take advantage of...
An Algorithm for Fractional Assignment Problems (1995)
Maiko Shigeno, Yasufumi Saruwatari, Tomomi Matsui
. In this paper, we propose a polynomial time algorithm for fractional assignment problems. The fractional assignment problem is interpreted as follows. Let G = (I; J; E) be a bipartite graph where I...
An Algorithm for Fractional Assignment Problems (1995)
Maiko Shigeno, Yasufumi Saruwatari, Tomomi Matsui
. In this paper, we propose a polynomial time algorithm for fractional assignment problems. The fractional assignment problem is interpreted as follows. Let G = (I; J; E) be a bipartite graph where I...
Is a Given Flow Uncontrollable? (1995)
this paper, we discuss the problem "Is a given flow uncontrollable?". We show that the problem is NP-complete.
An Enumeration Algorithm for the Edge Coloring Problem on Bipartite Graphs (1995)
. In this paper, we propose an algorithm for finding all the edge colorings in bipartite graphs. Our algorithm requires O(m log 1 + K minfn 2 + m;m log 1g) time and O(m1) space, where n denotes the...
A Linear Time Algorithm for the Minimum Spanning Tree Problem on a Planar Graph (1994)
: In this paper, we propose a linear time algorithm for finding a minimum spanning tree on a planar graph. Keywords: Combinatorial problems; graphs; spanning trees; planar graphs 1 Introduction...
NP-Completeness of Non-Adjacency Relations on Some 0-1 Polytopes (1994)
: In this paper, we discuss the adjacency structures of some classes of 0-1 polytopes including knapsack polytopes, set covering polytopes and 0-1 polytopes represented by complete sets of...
The Minimum Spanning Tree Problem on a Planar Graph (1994)
cle. A spanning forest of G is called a spanning tree when it is connected. In this note, we present a spanning forest as its edge set. Given a graph G and its edge e; Gne denotes the graph obtained...
: In this paper, we propose an O(n) time algorithm for the Hitchcock transportation problem with n demand points and fixed number of supply points. When the number of supply points is very small and...
Adjacency on Combinatorial Polyhedra (1993)
: This paper shows some useful properties of the adjacency structures of a class of combinatorial polyhedra including the equality constrained 0-1 polytopes. The class of polyhedra considered here...
An Algorithm for Finding All the Spanning Trees in Undirected Graphs (1993)
: In this paper, we propose an algorithm for finding all the spanning trees in undirected graphs. The algorithm requires O(n + m + øn) time and O(n + m) space, where the given graph has n vertices,...
A Note On k Best Solutions To The Chinese Postman Problem (1993)
Yasufumi Saruwatari, Tomomi Matsui
. The K-best problems on combinatorial optimization problems, in which K best solutions are considered instead of an optimal solution under the same conditions, have widely been studied. In this...
Adjacency on Combinatorial Polyhedra (1993)
Tomomi Matsui, S. Tamura, Sunao Tamura
: This paper shows some useful properties of the adjacency structures of a class of combinatorial polyhedra including the equality constrained 0-1 polytopes. The class of polyhedra considered here...
An Analysis of Dinkelbach's Algorithm for 0-1 Fractional Programming Problems (1992)
T. Matsui, Y. Saruwatari, Tomomi Matsui, Yasufumi Saruwatari, Maiko Shigeno
: The 0-1 fractional programming problem minimizes the fractional objective function (c 1 x 1 + c 2 x 2 + 1 1 1 + c n x n )=(d 1 x 1 + d 2 x 2 + 1 1 1 + d n x n ) = cx=dx under the condition that x =...
Finding All Minimum Cost Perfect Matchings in Bipartite Graphs (1991)
. The Hungarian method is an efficient algorithm for finding a minimal cost perfect matching in a weighted bipartite graph. This paper describes an efficient algorithm for finding all minimal cost...
Finding All The Perfect Matchings in Bipartite Graphs (1989)
This paper describes an algorithm for finding all the perfect matchings in a bipartite graph. By using the binary partitioning method, our algorithm requires O(c(n +m)+ n 2:5 ) computational effort...
On the Finiteness of the Criss-Cross Method (1989)
. In this short paper, we prove the finiteness of the criss-cross method by showing a certain binary number of bounded digits associated with each iteration increases monotonically. This new proof...