東川 雄哉

This paper considers the minimax regret 1-median problem in dynamic path networks. In our model, we are given a dynamic path network consisting of an undirected path with positive edge lengths, uniform positive edge capacity, and nonnegative vertex supplies. Here, each vertex supply is unknown but only an interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Given a scenario s and a sink location x in a dynamic path network, let us consider the evacuation time to x of a unit supply given on a vertex by s. The cost of x under s is defined as the sum of evacuation times to x for all supplies given by s, and the median under s is defined as a sink location which minimizes this cost. The regret for x under s is defined as the cost of x under s minus the cost of the median under s. Then, the problem is to find a sink location such that the maximum regret for all possible scenarios is minimized. We propose an O(n3) time algorithm for the minimax regret 1-median problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network.

We address the problem of locating k sinks on dynamic flow path networks with n vertices in such a way that the evacuation completion time to them is minimized. Our two algorithms run in O(n log n + k2 log4 n) and O(n log3 n) time, respectively. When all edges have the same capacity, we also present two algorithms which run in O(n + k2 log2 n) time and O(n log n) time, respectively. These algorithms together improve upon the previously most efficient algorithms, which have time complexities O(kn log2 n) [1] and O(kn) [11], in the general and uniform edge capacity cases, respectively. The above results are achieved by organizing relevant data for subpaths in a strategic way during preprocessing, and the final results are obtained by extracting/ merging them in an efficient manner.

In the air-traffic control, the information related to each air-plane needs to be always displayed as the label. Motivated by this appli-cation, de Berg and Gerrits (Comput. Geom. 2012) presented free-label maximization problem, where the goal is to maximize the number of intersection-free labels. In this paper, we introduce an alternative label-ing problem for the air-traffic control, called point-overlap minimization. In this problem, we focus on the number of overlapping labels at a point in the plane, and minimize the maximum among such numbers. Instead of maximizing the number of readable labels as in the free-label maximiza-tion, we here minimize the cost required for making unreadable labels readable. We provide a 4-approximation algorithm using LP rounding for arbitrary rectangular labels and a faster combinatorial 8-approximation algorithm for unit-square labels.

We first consider the weighted p-center problem, in which the centers are constrained to lie on two axis-parallel lines. Given a set of n points in the plane, which are sorted according to their x-coordinates, we show how to test in O(n log n) time if p piercing points placed on two lines, parallel to the x-axis, can pierce all the disks of different radii centered at the n given points. This leads to an O(n log(2) n) time algorithm for the weighted p-center problem. We then consider the unweighted case, where the centers are constrained to be on two perpendicular lines. Our algorithm runs in O(n log(2) n) time in this case as well.

This paper considers the minimax regret 1-median problem in dynamic path networks. In our model, we are given a dynamic path network consisting of an undirected path with positive edge lengths, uniform positive edge capacity, and nonnegative vertex supplies. Here, each vertex supply is unknown but only an interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Given a scenario s and a sink location x in a dynamic path network, let us consider the evacuation time to x of a unit supply given on a vertex by s. The cost of x under s is defined as the sum of evacuation times to x for all supplies given by s, and the median under s is defined as a sink location which minimizes this cost. The regret for x under s is defined as the cost of x under s minus the cost of the median under s. Then, the problem is to find a sink location such that the maximum regret for all possible scenarios is minimized. We propose an O(n(3)) time algorithm for the minimax regret 1-median problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network.

A dynamic network introduced by Ford and Fulkerson is a directed graph with capacities and transit times on its arcs. The quickest transshipment problem is one of the most fundamental problems in dynamic networks. In this problem, we are given sources and sinks. Then, the goal of this problem is to find a minimum time limit such that we can send exactly the right amount of flow from sources to sinks. In this paper, we introduce a variant of this problem called the mixed evacuation problem. This problem models an emergent situation in which people can evacuate on foot or by car. The goal is to organize such a mixed evacuation so that an efficient evacuation can be achieved. In this paper, we study this problem from the theoretical and practical viewpoints. In the first part, we prove the polynomial-time solvability of this problem in the case where the number of sources and sinks is not large, and also prove the polynomial-time solvability and computational hardness of its variants with integer constraints. In the second part, we apply our model to the case study of Minabe town in Wakayama prefecture, Japan.

In this paper, we characterize the redundant rigidity and the redundant global rigidity of body-hinge graphs in R-d in terms of graph connectivity. Although an efficient algorithm which determines mixed-connectivity is still not known, our result implies that both edge-redundancy for rigidity and edge-redundancy for global rigidity can be checked via efficient graph-connectivity algorithms. (C) 2015 Elsevier B.V. All rights reserved.

We consider the bracing problem of a square grid framework possibly with holes and present an efficient algorithm for making the framework infinitesimally rigid by augmenting it with the minimum number of diagonal braces. This number of braces matches the lower bound given by Gaspar, Radics and Recski [2]. Our contribution extends the famous result on bracing the rectangular grid framework by Bolker and Crapo [1]. (C) 2015 Elsevier B.V. All rights reserved.

This paper considers the k-sink location problem in dynamic path networks. A dynamic path network consists of an undirected path with positive edge lengths, uniform edge capacity, and positive vertex supplies. A path can be considered as a road, edge lengths as the distance along a road segment and vertex supplies as the number of people at a location. The edges all have a fixed common capacity, which limits the number of people that can enter that edge in a unit of time. The problem is to find the optimal location of k sinks (exits) on the path such that each evacuee is sent to one of the k sinks. The existence of capacities causes congestion, which can slow evacuation down in unexpected ways. Let x be a vector denoting the location of the k sinks. The optimal evacuation policy for x is (k - 1)-dimensional vector d, called (k - 1)-divider. Each component of d corresponds to a boundary dividing all evacuees between adjacent two sinks into two groups, i.e., all supplies to the right of the boundary evacuate to the right sink and all the others to the left sink. In this paper, we consider optimality defined by two different criteria, the minimax criterion and the minisum one. We prove that the minimax problem can be solved in O(kn) time and the minisum problem in O(n(2) . min{root k logn + logn, 2(root logk log logn)}) time, where n is the number of vertices in the given network. (C) 2015 Elsevier B.V. All rights reserved.

This paper considers the minimax regret 1-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths and uniform edge capacity, and each vertex supply which is non-negative value is unknown but only the interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location is defined as the minimum time to complete the evacuation for all supplies (evacuees), and the regret of a sink location x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a point as a sink such that the maximum regret for all possible scenarios is minimized. We propose an O(n logn) time algorithm for the minimax regret 1-sink location problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network. (C) 2014 Elsevier B.V. All rights reserved.

A d-dimensional body-hinge framework is a collection of d-dimensional rigid bodies connected by hinges, where a hinge is a (d - 2)-dimensional affine subspace, i.e., pin-joints in 2-space, line-hinges in 3-space, plane-hinges in 4-space and etc. Bodies are allowed to move continuously in R-d so that the relative motion of any two bodies connected by a hinge is a rotation around it and the framework is called rigid if every motion provides a framework isometric to the original one. A body-hinge framework is expressed as a pair (G, p) of a multigraph G = (V, E) and a mapping p from e is an element of E to a (d - 2)-dimensional affine subspace p(e) in R-d. Namely, v is an element of V corresponds to a body and uv is an element of E corresponds to a hinge p(uv) which joins the two bodies corresponding to u and v. Then, G is said to be realized as a body-hinge framework (G, p) in R-d, and is called a body-hinge graph. It is known [9,12] that the infinitesimal rigidity of a generic body-hinge framework (G, p) is determined only by its underlying graph G. So, a graph G is called (minimally) rigid if G can be realized as a (minimally) infinitesimally rigid body-hinge framework in d-dimension. In this paper, we shall present an inductive construction for minimally rigid body-hinge simple graphs in d-dimension with d >= 3. (C) 2014 Elsevier B.V. All rights reserved.

This paper deals with online graph exploration problems by multiple searchers. The information on the graph is given online. As the exploration proceeds, searchers gain more information on the graph. Assuming an appropriate communication model among searchers, searchers can share the information about the environment. Thus, a searcher must decide which vertex to visit next based on the partial information on the graph gained so far by searchers. We assume that all searchers initially start the exploration at the origin vertex, and the goal is that each vertex is visited by at least one searcher and all searchers finally return to the origin vertex. The objective is to minimize the time when the goal is achieved. We study the case of cycles and trees. For the former, we give an optimal online exploration algorithm in terms of competitive ratio, and for the latter, we also give an online exploration algorithm which is optimal among greedy algorithms.

This paper addresses the minimax regret sink location problem in dynamic tree networks. In our model, a dynamic tree network consists of an undirected tree with positive edge lengths and uniform edge capacity, and the vertex supply which is nonnegative value is unknown but only the interval of supply is known. A particular realization of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location x is defined as the minimum time to complete the evacuation to x for all supplies (evacuees), and the regret of x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a sink location minimizing the maximum regret for all possible scenarios. We present an O(n(2) log(2) n) time algorithm for the minimax regret sink location problem in dynamic tree networks with uniform capacity, where n is the number of vertices in the network. As a preliminary step for this result, we also address the minimum cost sink location problem in a dynamic tree networks under a fixed scenario and present an O(n log n) time algorithm, which improves upon the existing time bound of O(n log(2) n) by [11] if edges of a tree have uniform capacity.

We consider the bracing problem of a square grid framework possibly with holes and present an efficient algorithm for making the framework infinitesimally rigid by augmenting it with the minimum number of diagonal braces. This number of braces matches the lower bound given by Gaspar, Radics and Recski [2]. Our contribution extends the famous result on bracing the rectangular grid framework by Bolker and Crapo [1].

This paper considers the k-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths, uniform edge capacity, and positive vertex supplies. Here, each vertex supply corresponds to a set of evacuees. Then, the problem requires to find the optimal location of k sinks in a given path so that each evacuee is sent to one of k sinks. Let x denote a k-sink location. Under the optimal evacuation for a given x, there exists a (k-1)-dimensional vector d, called (k-1)-divider, such that each component represents the boundary dividing all evacuees between adjacent two sinks into two groups, i.e., all supplies in one group evacuate to the left sink and all supplies in the other group evacuate to the right sink. Therefore, the goal is to find x and d which minimize the maximum cost or the total cost, which are denoted by the minimax problem and the minisum problem, respectively. We study the k-sink location problem in dynamic path networks with continuous model, and prove that the minimax problem can be solved in O(kn log n) time and the minisum problem can be solved in O(kn(2)) time, where n is the number of vertices in the given network.

This paper addresses the minimax regret sink location problem in dy- namic tree networks. In our model, a dynamic tree network consists of an undirected tree with positive edge lengths and uniform edge capacity, and the vertex supply which is a positive value is unknown but only the interval of supply is known. A particular realization of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location x is defined as the minimum time to complete the evacuation to x for all supplies (evacuees), and the regret of x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a sink location which minimizes the maximum regret for all possible scenarios. We present an O(n2 log2 n) time algorithm for the minimax regret sink location problem in dynamic tree networks with uniform capacity, where n is the number of vertices in the network. As a preliminary step for this result, we also address the minimum cost sink location problem in a dy- namic tree networks under a fixed scenario and present an O(n log n) time algorithm, which improves upon the existing time bound of O(n log2 n) by [14] if edges of a tree have uniform capacity.

This paper considers online vertex exploration problems in a simple polygon where starting from a point in the inside of a simple polygon, a searcher is required to explore a simple polygon to visit all its vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm.

This paper considers minimax regret 1-sink location problems in dynamic path networks. A dynamic path network consists of an undirected path with positive edge lengths and constant edge capacity and the vertex supply which is nonnegative value, called weight, is unknown but only the interval of weight is known. A particular assignment of weight to each vertex is called a scenario. Under any scenario, the cost of a sink is defined as the minimum time to complete evacuation for all weights (evacuees), and the regret of a sink location x is defined as the cost of x minus the cost of an optimal sink. Then, the problem is to find a point as a sink such that the maximum regret for all possible scenarios is minimized. We present an O(n log2 n) time algorithm for minimax regret 1-sink location problems in dynamic path networks, where n is the number of vertices in the network. © Springer-Verlag Berlin Heidelberg 2013.

In this paper, we propose an inductive construction of minimally rigid body-hinge simple graphs. Inductive construction is one of well-studied topics in Combinatorics and Combinatorial Optimization. We develop an inductive construction for minimally rigid body-hinge simple graphs in d-dimension with d ≥ 3 by which we can develop a polynomial-time algorithm for enumerating all minimally rigid body-hinge simple graphs. © Springer International Publishing 2013.

This paper considers an online exploration problem in a simple polygon where starting from a point in the interior of a simple polygon, the searcher is required to explore a simple polygon to visit all its vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm. © 2012 Springer-Verlag.