東川 雄哉

Evacuation in emergency situations can be modeled by a dynamic flow network.<br /> Two criteria have been used before: one is the evacuation completion time and<br /> the other is the aggregate evacuation time of individual evacuees. The aim of<br /> this paper is to optimize the aggregate evacuation time in the simplest case,<br /> where the network is a path and only one evacuation center (called a sink) is<br /> to be introduced. The evacuees are initially located at the vertices, but their<br /> precise numbers are unknown, and are given by upper and lower bounds. Under<br /> this assumption, we compute the sink location that minimizes the maximum<br /> &quot;regret.&quot; We present an $O(n^2\log n)$ time algorithm to solve this problem,<br /> improving upon the previously fastest $O(n^3)$ time algorithm, where $n$ is the<br /> number of vertices.

A Dynamic Graph Network is a graph in which each edge has an associated<br /> travel time and a capacity (width) that limits the number of items that can<br /> travel in parallel along that edge. Each vertex in this dynamic graph network<br /> begins with the number of items that must be evacuated into designated sink<br /> vertices. A $k$-sink evacuation protocol finds the location of $k$ sinks and<br /> associated evacuation movement protocol that allows evacuating all the items to<br /> a sink in minimum time. The associated evacuation movement must impose a<br /> confluent flow, i.e, all items passing through a particular vertex exit that<br /> vertex using the same edge. In this paper we address the $k$-sink evacuation<br /> problem on a dynamic path network. We provide solutions that run in $O(n \log<br /> n)$ time for $k=1$ and $O(k n \log^2 n)$ for $k &gt;1$ and work for arbitrary edge<br /> capacities.

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.

A dynamic network ${\cal N} = (G,c,\tau,S)$ where $G=(V,E)$ is a graph,<br /> integers $\tau(e)$ and $c(e)$ represent, for each edge $e\in E$, the time<br /> required to traverse edge $e$ and its nonnegative capacity, and the set<br /> $S\subseteq V$ is a set of sources. In the $k$-{\sc Sink Location} problem, one<br /> is given as input a dynamic network ${\cal N}$ where every source $u\in S$ is<br /> given a nonnegative supply value $\sigma(u)$. The task is then to find a set of<br /> sinks $X = \{x_1,\ldots,x_k\}$ in $G$ that minimizes the routing time of all<br /> supply to $X$. Note that, in the case where $G$ is an undirected graph, the<br /> optimal position of the sinks in $X$ needs not be at vertices, and can be<br /> located along edges. Hoppe and Tardos showed that, given an instance of<br /> $k$-{\sc Sink Location} and a set of $k$ vertices $X\subseteq V$, one can find<br /> an optimal routing scheme of all the supply in $G$ to $X$ in polynomial time,<br /> in the case where graph $G$ is directed. Note that when $G$ is directed, this<br /> suffices to obtain polynomial-time solvability of the $k$-{\sc Sink Location}<br /> problem, since any optimal position will be located at vertices of $G$.<br /> However, the computational complexity of the $k$-{\sc Sink Location} problem on<br /> general undirected graphs is still open. In this paper, we show that the<br /> $k$-{\sc Sink Location} problem admits a fully polynomial-time approximation<br /> scheme (FPTAS) for every fixed $k$, and that the problem is $W[1]$-hard when<br /> parameterized by $k$.

構造体の動きが元々の構造体の合同変換のみである場合,その構造体は剛であるとする.剛な棒材(bar)とピン接合(joint)で構成される構造体をbar-jointフレームワークとよぶ.剛な構造体からどの棒材を1つ取り除いた場合にも,剛ではなくなる(柔軟となる)フレームワークのことを極小剛とよぶ.本研究では,空間充填立体のbar-jointフレームワークに対して,最小本数のブレースを追加することで極小剛とする手法を示す.

本研究では,凸多面体をpanel-hingeフレームワークとみなしたとき,端点を共有しない辺(マッチング辺)のヒンジを全て取り除いても,フレームワークが無限小剛のままであることを証明する.また,同様のフレームワークから互いに頂点を共有しないパネルを全て取り除いても無限小剛のままであるための十分条件を示す.ただし本研究はヒンジが一般的な配置,すなわち各ヒンジを表す直線間に代数的な依存関係がない状態を前提としている.

本研究では、直交する 3 種類の長方形パネルに限定した剛な panel-hinge フレームワークを実現する問題を考察する。Higashikawa らは最近、極小剛な panel-hinge graph をすべて導出するアルゴリズムを提案しているが、われわれが考察するフレームワークは generic ではないので、このアルゴリズムは適用できない。そこで、panel-hinge framework を導出する新たな操作を捉案し、それにもとづき、直交するパネルによるフレームワーク生成法を構築する。

本研究では、直交する 3 種類の長方形パネルに限定した剛な panel-hinge フレームワークを実現する問題を考察する。Higashikawa らは最近、極小剛な panel-hinge graph をすべて導出するアルゴリズムを提案しているが、われわれが考察するフレームワークは generic ではないので、このアルゴリズムは適用できない。そこで、panel-hinge framework を導出する新たな操作を捉案し、それにもとづき、直交するパネルによるフレームワーク生成法を構築する。

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.

本論文では,body-hingeグラフGがk-辺連結(k≧3)であることは,Gが(k-1)-edge-rigidであるための必要十分条件であることを示す.ここで,任意の(k-1)本の辺をbody-hingeグラフGから取り除いてできるグラフが剛であるとき,Gはk-edge-rigidであるとする.さらに,body-hingeグラフGがk-vertex-rigidであるとき,Gはk-連結であり,Gが(k+2)-連結であるとき,hを0≦h≦k-1として,Gが(k-h,h+2)-rigidであることを示す(k≧1).ここで,任意の(k-1)個の頂点をbody-hingeグラフGから取り除いてできるグラフが剛であるとき,Gはk-vertex-rigidであるとし,任意の(i-1)個の頂点をGから取り除いてできるグラフがj-edge-rigidであるとき,Gは(i,j)-rigidであるとする.

本論文では,動的パスネットワークにおけるk-施設配置問題を扱う.本モデルにおいて動的パスネットワークは,正のサプライ(避難者数)が与えられた頂点及び正の辺長と一様な辺容量をもつ辺からなるパス状の無向グラフによって構成される.あるk-避難施設配置xが与えられたとき,xに対する最適避難においては各避難者の動線が交差する事は無い.さらに本論文では,同一頂点に与えられたすべての避難者は同一施設に避難することを仮定している.したがって各隣接施設の間には,ある点より左側の避難者は左の最寄り施設へ,右側の避難者は右の最寄り施設へ避難するような境界点が必ず1つ存在し,それらを表すk-1次元ベクトルをdとする.このとき問題の目的は,k個の避難施設配置x及びk-1個の境界点配置dによって定まる避難完了時間を最小化するようなx及びdを決定することである.本論文では,以上の問題に対してO(kn log n)時間アルゴリズムを提案した.ここでnはネットワークの頂点数である.

本論文では,最大後悔値最小化を目的とする,動的パスネットワーク上における施設配置問題を扱う.動的パスネットワークは,正の辺長と一様な辺容量をもつ無向パスによって構成される.各頂点においてはサプライ(避難者)のインターバルが与えられており,各頂点に対してインターバルを満たすような供給の割り当てをシナリオと呼ぶ.あるシナリオsの下で1つの施設(避難所)の位置をxと決定したとき,シナリオsにおける施設配置飢のコストを,sの与えるネットワーク上のすべてのサプライがxへの避難を完了するために必要な最小時間として定義する.このとき,sにおけるxの後悔値を,sのコストからsにおける最適配置のコストを引いたものと定義する.さらに,sの最大後悔値を,sの後悔値のすべての可能なシナリオに対する最大値と定義するとき,問題の目的は最大後悔値を最小化する施設配置を求めることである.本論文では,以上の問題に対して0 log n)時間アルゴリズムを提案した.ここでnはネットワークの頂点数である.この結果は[6]によって提案されたアルゴリズムの計算時間を改善している.

本論文は極小剛なbody-hingeグラフの列挙問題を扱っている.3次元bar-jointフレームワークの剛性に対する組合せ的特徴付けは知られていないが,その特殊構造であるbody-hingeフレームワークに対しては組合せ的特徴づけが知られている.剛体(body)を頂点,剛体どうしをつなぐヒンジを辺で表したグラフをbody-hingeグラフとよぶ.本研究では極小剛なbody-hingeフレームワークを表すbody-hingeグラフをすべて列挙する問題を考察する.まず,所与のbody-hingeグラフからより大きなサイズのbody-hingeグラフを生成する4つの操作を提案し,この操作によりすべてのbody-hingeグラフが生成可能であることを証明する.これにより,すべてのbody-hingeグラフを生成するアルゴリズムを提案する.計算時間は一つのbody-hingeグラフあたり多項式時間で済む.

本論文は極小剛なbody-hingeグラフの列挙問題を扱っている．3次元bar-jointフレームワークの剛性に対する組合せ的特徴付けは知られていないが，その特殊構造であるbody-hingeフレームワークに対しては組合せ的特徴づけが知られている．剛体(body)を頂点，剛体どうしをつなぐヒンジを辺で表したグラフをbody-hingeグラフとよぶ．本研究では極小剛なbody-hingeフレームワークを表すbody-hingeグラフをすべて列挙する問題を考察する．まず，所与のbody-hingeグラフからより大きなサイズのbody-hingeグラフを生成する4つの操作を提案し，この操作によりすべてのbody-hingeグラフが生成可能であることを証明する．これにより，すべてのbody-hingeグラフを生成するアルゴリズムを提案する．計算時間は一つのbody-hingeグラフあたり多項式時間で済む．

本論文は極小剛なbody-hingeグラフの列挙問題を扱っている.3次元bar-jointフレームワークの剛性に対する組合せ的特徴付けは知られていないが,その特殊構造であるbody-hingeフレームワークに対しては組合せ的特徴づけが知られている.剛体(body)を頂点,剛体どうしをつなぐヒンジを辺で表したグラフをbody-hingeグラフとよぶ.本研究では極小剛なbody-hingeフレームワークを表すbody-hingeグラフをすべて列挙する問題を考察する.まず,所与のbody-hingeグラフからより大きなサイズのbody-hingeグラフを生成する4つの操作を提案し,この操作によりすべてのbody-hingeグラフが生成可能であることを証明する.これにより,すべてのbody-hingeグラフを生成するアルゴリズムを提案する.計算時間は一つのbody-hingeグラフあたり多項式時間で済む.

We consider an online traveling salesman 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 its all 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.We consider an online traveling salesman 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 its all 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.

本研究では複数人の探索者によるオンライングラフ探索問題を扱う.探索の目的は,すべての頂点が少なくとも1人の探索者によって到達されることである.すべての探索者は同一の頂点を探索の始点とし,同一の移動速度で探索を行う.また,すべての探索者は他の探索者が新しく入手した情報を常に共有することが出来る.本稿では特にグラフクラスをサイクル,木とする問題に対するアルゴリズムをそれぞれ与え,競合比解析を行う.具体的には探索者数を2とするサイクルの探索に対して最適な競合比3/2を達成するアルゴリズムを与え,さらに探索者数をpとする木の探索に対して最適な競合比(p/(log p))+o(1)を達成するアルゴリズムを与える.

本研究では複数人の探索者によるオンライングラフ探索問題を扱う.探索の目的は,すべての頂点が少なくとも1人の探索者によって到達されることである.すべての探索者は同一の頂点を探索の始点とし,同一の移動速度で探索を行う.また,すべての探索者は他の探索者が新しく入手した情報を常に共有することが出来る.本稿では特にグラフクラスをサイクル,木とする問題に対するアルゴリズムをそれぞれ与え,競合比解析を行う.具体的には探索者数を2とするサイクルの探索に対して最適な競合比3/2を達成するアルゴリズムを与え,さらに探索者数をpとする木の探索に対して最適な競合比(p/(log p))+o(1)を達成するアルゴリズムを与える.