Miyamoto Yuichiro

This paper discusses the problem of determining whether a given plane graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangulation. There exist theorems which characterize Delaunay graphs and yield polynomial time algorithms for the problem only by solving some linear inequality systems. A polynomial time algorithm proposed by Hodgson, Rivin and Smith solves a linear inequality system given by Rivin, which is based on sophisticated arguments about hyperbolic geometry. Independently, Hiroshima, Miyamoto and Sugihara gave another linear inequality system and a polynomial time algorithm. Although their discussion is based on primitive arguments on Euclidean geometry, their proofs are long and intricate, unfortunately. In this paper, we give a simple proof of the theorem shown by Hiroshima et al. by employing the fixed point theorem.

This study uses a mathematical optimization approach to design safe walking routes from school to home for children. Children are thought to be safer when walking together in groups rather than alone. Thus, we assume that the risk of walking along a given road segment in a group is smaller than that of walking the same segment alone. At the same time, the walking route between school and home for each child should not deviate substantially from the shortest route. We propose a bi-objective model that minimizes both the total risk (particularly, the total distance walked alone) and the total walking distance for all children. We present an integer programming formulation of the proposed problem and apply this formulation to two instances based on actual road networks. We obtain Pareto optimal solutions using a mathematical programming solver and analyze the characteristics of the solutions and their potential applicability to real situations. The results show that the proposed model produces much better solutions compared with the solution where each child walks along the shortest path from school to home. In some optimal solutions, only a small deviation from the shortest path results in a dramatic reduction of the risk objective.

Modularity proposed by Newman and Girvan is a quality function for community detection. Numerous heuristics for modularity maximization have been proposed because the problem is NP-hard. However, the accuracy of these heuristics has yet to be properly evaluated because computational experiments typically use large networks whose optimal modularity is unknown. In this study, we propose two powerful methods for computing a nontrivial upper bound of modularity. More precisely, our methods can obtain the optimal value of a linear programming relaxation of the standard integer linear programming for modularity maximization. The first method modifies the traditional row generation approach proposed by Grotschel and Wakabayashi to shorten the computation time. The second method is based on a row and column generation. In this method, we first solve a significantly small subproblem of the linear programming and iteratively add rows and columns. Owing to the speed and memory efficiency of these proposed methods, they are suitable for large networks. In particular, the second method consumes exceedingly small memory capacity, enabling us to compute the optimal value of the linear programming for the Power Grid network (consisting of 4941 vertices and 6594 edges) on a standard desktop computer.

In this study, we address a road infrastructure planning problem by relieving traffic congestion and thereby reducing CO2 emission. We model it as a mathematical optimization problem whose objective is to minimize the total travel time by improving road-infrastructures under the given budget. We take into account the interactions between vehicles at road intersections. By introducing an approximation technique for the interactions, the proposed model is practical in terms of both computational time and accuracy of the obtained planning. Computational results show that the obtained optimal plan for the improvement of road-infrastructures significantly reduces CO2 emission.

In simulation of evaluating a park-and-ride system, a timetable of associated public transportation strongly affects the simulation results. Conventional traffic-flow simulators that examine the effectiveness of a park-and-ride system are insufficient, because it is not practically possible to consider all timetables of the public transportation. In this study, using a mathematical optimization technique, we develop a method to obtain an optimal train timetable for a road network employing a park-and-ride system. The proposed method enables us to assess the effectiveness of a park-and-ride system more accurately to reduce congestion on a road network.

This paper considers an auction-based scheduling system in a job shop equipped with ubiquitous network environment to cope with dynamically changing market demands. Under such environment all machines and jobs are assumed to have computing and communication devices and can serve as intelligent agents. The functions for an auctioneer and for a participant are investigated to install the scheduling system as a distributed multi-agent system. The systems sending and receiving messages for the auction form a distributed system on a network, enabling an autonomous scheduling.

An orientation of an undirected graph G is a directed graph D on V(G) with exactly one of directed edges (u, v) and (vu) for each pair of vertices u and v adjacent in G. For integer k >= 3, we say a directed graph D is k-cyclic if every edge of D belongs to a directed cycle in D of length at most k. We consider the problem of deciding if a given graph has a k-cyclic orientation. We show that this problem is NP-complete for every fixed k >= 3 for general graphs and for every fixed k >= 4 for planar graphs. We give a polynomial time algorithm for planar graphs with k = 3, which constructs a 3-cyclic orientation when the answer is affirmative.

In this paper, we address the shortest path query problem, i.e., constructing a data structure of a given network to answer the shortest path length of two given points in a short time. We present a method named Levelwise Mesh Sparsification for the problem. The key idea is to divide the network into meshes and to sparsify the network in each mesh by removing unnecessary edges and vertices that are never used when the shortest path passes through the mesh. In large real-world road networks in the United States, our method is about 1,500 times faster than Dijkstra's algorithm, which is competitive with existing methods. The time taken to construct the data structure is a few hours on a typical PC. Unlike previous methods, our geometric partition method succeeded in reducing the data for connecting the sparsified network. As a result, our method uses additional data that is only about 10% of the original data size, while existing methods use more than 2000%. Our method has considerable extensibility because it is independent of search algorithms. Thus, it can be used with Dijkstra's algorithm and A*-search among others, and with several models such as negative costs, time-dependent costs, and so on. These are rarely handled by previous methods.

Given a finite set of 2-dimensional points P c R 2 and a positive real d, a unit disk graph, denoted by (P. d), is an undirected graph with vertex set P such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. 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) (def) double under bar {(xe(1) + ye(2)) vertical bar x is an element of {0, 1, . . . , m - 1}, y is an element of {0, 1, . . . , n - 1 } } where e(1) (def) double under bar (1, 0), e(2) (def) under bar (1/2, root-3/2). Let T(m,n)(d) be a unit disk graph defined on a vertex set P(m, n) and a positive real d. Let T(m,n)(k) be the kth power of T(m,n)(1). In this paper, we show necessary and sufficient conditions that [for all m, T(m,n)(d) is perfect] and/or [for all m, T(m,n)(k) is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (T(m,n)(d), w) and (T(m,n)(k), w). (C) 2008 Elsevier B.V. All rights reserved.

Given an undirected and edge-weighted graph G together with a set of ordered vertex-pairs, called st-pairs, we consider the problems of finding an orientation of all edges in G: MIN-SUM ORIENTATION is to minimize the sum of the shortest directed distances between all st-pairs; and MIN-MAX ORIENTATION is to minimize the maximum shortest directed distance among all st-pairs. In this paper, we first show that both problems are strongly NP-hard for planar graphs even if all edge-weights are identical, and that both problems can be solved in polynomial time for cycles. We then consider the problems restricted to cacti, winch form a graph class that contains trees and cycles but is a subclass of planar graphs. Then, MIN-SUM ORIENTATION is solvable in polynomial time, whereas MIN-MAX ORIENTATION remains NP-hard even for two st-pairs. However, based on LP-relaxation, we present a polynomial-tine 2-approximation algorithm for MIN-MAX ORIENTATION. Finally, we give a fully polynomial-time approximation scheme (FPTAS) for MIN-MAX ORIENTATION on cacti if the number of st-pairs is a fixed constant.

In this paper, we propose the levelwise mesh sparsification method for the shortest path query problem. Several sparse networks are obtained by sparsifying the original network, and the shortest path problem is solved by finding the shortest path in these networks. The obtained networks are sparse and small, thus the computational time is short. Computational experiments on real world data show the efficiency of our method in terms of computational time and memory efficiency. Compared with existing approaches, the advantage of our method is that it can deal with negative costs and time-dependent costs, and uses only a small amount of memory.

The shortest path problem is one of the most fundamental problems in computer science. Although several quasi linear time algorithms have been proposed, even an optimal algorithm does not terminate in sufficiently short time for large-scale networks, such as web networks and road networks. An approach to solving this problem is to construct data structures that enable us to find solutions in a short time. This approach is efficient for applications in which the networks are fixed and we have to answer possibly many questions in a short time, such as in car navigation systems. In this paper, we propose the levelwise mesh sparsification method for the problem. Several sparse networks are obtained by sparsifying the original network, and the shortest path problem is solved by finding the shortest path in these networks. The obtained networks are sparse and small, thus the computational time is short. Computational experiments on real world data show the efficiency of our method in terms of computational time and memory efficiency. Compared with existing approaches, the advantage of our method is that it can deal with negative costs and time-dependent costs, and uses only a small amount of memory.

By the recent dissemination of the information network and distributed computation environment, distributed and real time scheduling in job shops is becoming a strong tool to respond quickly and efficiently to the dynamic changes in the market demands. In this study, auction based scheduling is considered as a scheduling method which can utilize the soon coming ubiquitous environment in job shops. Based on simulation studies of a basic auction procedure considered firstly, a two-way auction procedure is proposed to overcome drawbacks of the basic procedure, enabling to seek a match between machine and job for high performance of the shop. Simulation studies are performed on a job shop model taken from a real factory and demonstrated the effectiveness of the proposed scheduling method based on a two-way auction.

We propose polynomial time approximation algorithms for minimum span channel (frequency) assignment problems, which is known to be NP-hard. Let alpha be the approximation ratio of our algorithm and W >= 2 be the maximum of numbers of channels required in vertices. If an instance is defined on a perfect graph G, then alpha <= 1 + (1 + 1/W-1) H-omega((G)), where Hi denotes the i-th harmonic number. For any instance defined on a unit disk graph G, alpha is less than or equal to (1 + 1/w-1)(3H(omega)((G))-1). If a given graph is 4 or 3 colorable, a is bounded by (2.5 + W-1 (2 + 1/W-1), respectively. We also discuss well-known practical instances called, Philadelphia instances and propose an algorithm with alpha < 12/5.

Given a pair of non-negative integers m and n, P(m, a) denotes a subset, of 2-dimensional triangular lattice points defined by P(m, n) (def) double under bar. {(xe(1) + ye(2)) vertical bar x is an element of {0, 1, ... , m - 1} y is an element of {0, 1, ... , n - 1 } } where e(1) (def) double under bar. (1, 0), e(2) (def) double under bar. (1/2, root 3/2). Let T(m,n)(d) be an undirected graph defined on vertex set. P(m, n) satisfying that two vertices are adjacent. if and only if the Euclidean distance between the pair is less than or equal to d. This paper discusses a necessary and sufficient condition that T(m,n)(d) is perfect; we show that [for all m is an element of Z(+), T(m,n)(d) is perfect] if and only if d >= root n(2)-3n+3. Given a non-negative vertex weight. vector w is an element of Z(+)(P(m, n)), a multicoloring of (T(m,n)(d), w) is an assignment, of colors to P(m, n) such that each vertex v is an element of P(m, n) admits w(v) colors and every adjacent pair of two vertices does not share a common color. We also give an efficient algorithm for multicoloring (T(m,n) (d), w) when P(m, n) is perfect. In general case, our results on the perfectness of P(m, n) implies a polynomial time approximation algorithm for multicoloring (T(m,n) (d), w). Our algorithm finds a multicoloring which uses at most alpha(d)omega + O(d(3)) colors, where w denotes the weighted clique number. When d = 1, root 3, 2, root 7, 3, the approximation ratio alpha(d) = (4/3), (5/3), (5/3), (7/4), (7/4), respectively. When d > 1, we showed that alpha(d) <= (1 + 2/root 3-1 2 root 3-3/d) < 1 + 2/root 3 < 2.155.

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} x {0, 1, 2, ..., n - 1}, where a pair of two vertices is adjacent if and only if the distance is equal to 1. A triangular lattice graph T(m, n) has a vertex set {(xe(1) + ye(2)) | x is an element of {0, 1, 2, ..., m - 1}, y is an element of {0, 1, 2, ..., n - 1 } } where e(1)(def) = (1, 0), e(2)(def) = (1/2, root 3/2), and an edge set consists of a pair of vertices with unit distance. Let S-k (m, n) and T-k (m, n) be the kth power of the graph S(m, n) and T(m, n), respectively. Given an undirected graph G = (V, E) and a non-negative vertex weight function w : V -> Z(+), a multicoloring of G is an assignment of colors to V such that each vertex v is an element of V admits w(v) colors and every adjacent pair of two vertices does not share a common color. In this paper, we show necessary and sufficient conditions that [for all m, the S-k(m,n) is perfect] and/or [for all m, T-k(m,n) is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (S-k(m,n),w) and (T-k(m,n),w).

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)={(ze_1+ye_2)|x∈{0,1,…,m-1},y∈{0,1,…,n-1 } } where e_1=^^<def>(1,0),e_2=^^<def>(1/2,√<3>/2). Let T_<m, n>(d) be an undirected graph defined on vertex set P(m, n) satisfying that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. In this paper, we discuss a necessary and sufficient condition that T_<m, n>(d) is perfect. More precisely, we show that ∀m∈Z_+, T_<m, n>(d) is perfect ] if and only if d≧√<n^2-3n+3>. Given a non-negative vertex weight vector ω∈Z^<P(m, n)>_+, a multicoloring of (T_<m, n>(d),ω) is an assignment of colors to P(m, n) such that each vertex υ∈P(m, n) admits ω(υ) colors and every adjacent pair of two vertices does not share a common color. We also give an efficient algorithm for muliticoloring (T_m, n(d), ω) when P(m, n) is perfect. In general case, our results on the perfectness of P(m, n) implies a polynomial time approximation algorithm for multicoloring (T_m, n(d), ω). Our algorithm finds a multicoloring which uses at most α(d)ω+O(d^3) colors, where ω denotes the weighted clique number. When d=1, √<3>, 2,√<7>, 3, the approximation ratio α(d)=(4/3), (5/3), (5/3), (7/4), (7/4), respectively. When d>1, we showed that α(d)≦(1+2/√<3>+(√^2<3>-3)/d). We also showed the NP-completeness of the problem to determine the existence of a multicoloring of (T_m, n(d), ω) with strictly less than (4/3)ω colors.

This paper is concerned with the input-or-output test that is a kind of interval capacity consistency tests. And an O(n(2) log(2) n) algorithm dealing with the test is proposed, where n denotes the number of jobs. In literature, an O(n(4)) algorithm has been known. The tests can be effectively used to reduce the search space of time- and resource-constrained scheduling problems. Computational results show that our new algorithm is about 3 times faster for instances of 30 jobs than the existing algorithm.

Let P be a subset of 2-dimensional integer lattice points P = {1,2,... m} x {1,2,...,n} subset of or equal to Z(2). We consider the graph G(p) with vertex set P satisfying that two vertices in P are adjacent if and only if Euclidean distance between the pair is less than or equal to root2. Given a non-negative vertex weight vector w is an element of Z(+)(P), a multicoloring of (G(p), w) is an assignment of colors to P such that each vertex v is an element of P admits w(v) colors and every adjacent pair of two vertices does not share a common color. We show the NP-completeness of the problem to determine the existence of a multicoloring of (G(p), w) with strictly less than (4/3)w colors where w denotes the weight of a maximum weight clique. We also propose an O(mn) time approximation algorithm for multicoloring (G(p), w). Our algorithm finds a multicoloring with at most (4/3)w + 4 colors Our algorithm based on the property that when n = 3, we can find a multicoloring of (G(p), w) with W colors easily, since an undirected graph associated with (G(p), w) becomes a perfect graph.

We consider the item assortment problem of a vending machine. Our goal is to determine the optimal assortment of items and the optimal replenishment cycle time of the vending machine. We model the problem as mathematical programming problems. We formulate this problem as an integer linear programming problem to get tight lower bounds and apply the column generation method for its linear relaxation problem. We also propose two algorithms to get upper bounds, one based on tabu search and the other on multiple start local search. Our numerical experiments on a real world instance and randomly generated instances show that our methods generate good solutions within a reasonable computational time.

In this paper, we present an integrated vender managed inventory system currently being developed for large soft drink firms in Japan. The heart of our system is a heuristic algorithm for the inventory routing problem that is concerned with the supply of a set of products from a single depot to a set of customers over a given planning horizon. The objective is to minimize the sum of distribution, inventory, and shortage costs during the planning periods. Our two-phase algorithm determines the set of customers to be supplied each day and finds routes for vehicles to serve those customers. The first phase of the algorithm constructs an initial feasible solution using an insertion method, and the second improves the initial solution using a local search based on Cross-opt neighborhood. Due to the size and complexity of our real application, we adopt sophisticated data structures and speed-up techniques. Typical problems involve a depot and about 700 vending machines. For the problems, the system has been saving about 40% of total working hours and the number of roots.

This paper presents a new proof to polynomial-time algorithm for determining whether a given embedded graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangulation. The problem of recognizing the Delaunay graph had long been open. Recently Hodgson et al. gave a combinatorial characterization of the Delaunay graph, and thus constructed the polynomial-time algorithm for recognizing the Delaunay graphs. Their proof is based on sophisticated discussions on hyperbolic geometry. On the other hand, this paper gives another and simpler proof based on primitive arguments on Euclidean geometry. Moreover, the algorithm is applied to study the distribution of non-Delaunay graphs.