加藤 直樹

n個の実数の重みw1，w2，．．．，wnが一次元配列に与えられている。このとき［1，n］の部分区間1に属する重み集合と[1，n］?Iに属する重み集合．のクラス間分散を最大にする区間1を求める問題を解くO（nlogn）時間アルゴリズムを提案する。さらにこのアルゴリズムを二次元配列の問題に拡張する。つまり，実数の重みがN×Nの二次元配列に与えられた場合に、クラス間分散を最大にする矩形領域を求める問題に対するO（N^3）時間アルゴリズムを提案する。Given n real weights w1, w2, . . . , wn that are stored in one-dimensional array, we shall consider the problem of finding an interval I ∈ [1, n] that maximizes the interclass variance between weights in I and [1, n]-I. We shall present an O(nlogn) time algorithm for this problem. We then extend this algorithm to two-dimensional Case. Namely, given a N × N two-dimensional array in which each component is associated with real weight, the problem seeks to find a rectangular subarray R such that the interclass variance between weights in R and A-R is maximized. We shall present an O(N^3) algorithm for this problem.

本論文では単一デポを有する木構造ネットワーク上の配送計画問題を考察する。顧客は，木の頂点上に位置し，正の需要を持っている。同一の積載量制限のある車両群がデポを出発し，顧客の需要を満たしなからデポに戻って来る。また，一人の顧客の需要は分割可能であるとする（二台以上の車両によってその顧客の総需要を満たすことが許される）。このとき，全顧客の需要を満たす車両配送計画のなかで総走行距離を最小する配送計画を求める問題である。本論文はこの問題がNP?完全であることを示すとともに、近似比1.5の近似アルゴリズムを提案する。In this paper we deal with a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint. We show that the problem is NP-complete and propose a 1.5-approximlation algorithm for the problem. We also give some computational results.

本論文では、整数値ポリマトロイドに関するパラメトリックな最適基底の数を、重みがパラメターに関して線形である場合に解析し、漸近的に最適な理論的上界を与えた。この結果は、計算幾何学における最近の注目すべき結果であるTanal Deyによるkセットの数及びアレンジメントのkレベル（図1）の複雑度のO(k^<1/3>n)の上界、David Eppsteinによる線形パラメトリックマトロイドの基底の数の最適下界、アレンジメントのat-most-kレベルに対する古典的なΘ(kn)の最適下界の3つを統一し、一般化したものになっている。更に、幾何学的応用として、Welzlによるアレンジメントの多重レベルの複雑度の上界を改良し、さらに平面点集合の平行線による等分の個数の上界を与えている。We give an optimal bound on the number of transitions of the minimum weight base of an integer valued parametric polymatroid. This generalizes and unifies Tamal Dey's O(k^<1/3n>) upper bound on the number of k-set (and complexity of k-level of an arrangement), David Eppstein's lower bound on the transition of the minimum weight base of a parametric matroid, and also the Θ(kn) bound for the complexity of at-most-k level (union of i-levels for i=1,2,..,k) of the arrangement. As applications, we improve Welzl's upper bound of the sum of complexities of multiple levels, and considered the number of different equal-sized-bucketing of a planar point set with parallel partition lines.

平面上に点集合Sが与えられた時、固定された原点とSの高々k点を通る巡回路をSのk巡回路と呼ぶ。我々の目的は、Sのすべての点をk巡回路の集合で被覆しその総長を最小化することである。kが定数のとき、この問題に対してHaimovichとRinnooy Kanによる多項式時間近似スキームが知られている。本稿では別の考え方に基づく多項式時間近似スキームを与える。この結果はdが定数である限りd次元空間における問題に拡張できる。対照的に、点集合が一般的な計量空間に置かれた場合にはこの問題はAPX完全であることを示す。Let S be a set of points in the plane. A k-tour through S is a tour in the plane that starts and ends at the fixed origin and visits at most k points of S. Our goal is to cover all the points of S by k-tours while minimizing the total length of the tours. When k is fixed, a polynomial time approximation scheme (PTAS) due to Haimovich and Rinnooy Kan is known. We give an alternative PTA for fixed k. This result extends to the d-dimensional space, as long as d is a constant. In contrast, we show that the non-geometric version of this problem, in which the points are placed in a general metric space, is APX-complete for any fixed k.

画像データから特定の対象物に対応する領域を抽出する問題をイメージ切り出し(image segmentation)という。イメージ切り出しは画像処理における重要かつ難しい問題であり,たとえば航空写真から特定の建物などの対象物の抽出,文字などのパターン認識などに応用される。この問題はかなり古くから研究されており多くの手法が開発されているが,最適化問題として定式化して手法の構築を試みているものはあまりみられない。本論文では白黒のディジタル画像に限定し,与えられた画像を二つの領域に分割したい,つまり画像から背景部分を取り除いて対象物を抽出する問題に限定したイメージ切り出しの問題を組合せ最適化問題に定式化し,その高速アルゴリズムを最近で共同開発したので,その方法について解説をおこなう。ここでは,抽出したい対象物は1つの連結領域からなる場合を扱う。計算機実験によるとわれわれの開発した手法はかなり良好であるという結果が得られている。本論文の構成は以下の通りである。2節では本論文で扱うイメージ切り出し問題の定義をおこない,組合せ最適化問題としての定式化を与える。抽出したい領域に対する制約として,"領域が連結である"というだけでは一般にNP困難であることが分かっているので,抽出される領域にさらに制限を加え,抽出領域が一本のx-単調な曲線で区切られている場合(第3節),さらに二本のx-単調な曲線で区切られている場合について考察し(第4節),これらの場合に対する多項式時間アルゴリズムの概略について述べる。

本論文では、平面曲線を格子点を結ぶ多角形チェインで近似する効率のよいアルゴリズムを提案する。すなわち、m×nの格子平面上にx方向に単調な曲線y=f（）が与えられたとき、この曲線を格子点を直線で結ぶ多角形チェインによって近似するのが問題である。与えられた曲線と近似多角形チェインによって囲まれた領域の面積や面積の2乗を最小化するなどの最適化基準について論じる。入力の曲線は幾つかのx方向に単調な曲線をつなげたものとして定義されていてもよい。近似に用いる線分の（水平方向の）長さの上限をkとしたとき、提案するアルゴリズムは（）時間とO（）の記憶量で最適解を見つけることができる。ただし、与えられた曲線の積分値などの基本的な計算が定数時間でできることを仮定している。この時間複雑度は入力関数の値域のサイズを表わすmに依存しないことに注意されたい。最小コストパス問題に還元するというのが基本的な考え方である。This paper presents efficient algorithms for approximating a curve by a polygonal chain with vertices on grid points. Precisely, we are given an x-monotone curve y=f(x) in some m×n grid plane. We want to approximate the curve by an x-monotone polygonal chain whose Vertices are grid points. For that, we discuss several optimization criteria such as minimizing the area or squared area of the region bounded by the given curve and the polygonal chain. Notice that the curve can be defined as a chain of x-monotone curves. When the horizontal length of a line segment to be used for approximation is restricted to be at most k, the proposed algorithm finds an optimal x-monotone polygonal chain in O(kn) time and O(n) space if we assume that some basic computations (e.g, the integral of a given curve) can be computed in constant time. This time complexity does not depend on m, the size of the value range of the input function. The key idea behind it is the reduction to that of finding a minimum-cost path.

Gをn個の節点をもつ無向グラフとする。Kargerはグラフの最小カット問題に対してランダムアルゴリズムを与えた。そのアルゴリズムは確率Ω（^<?2>）でグラフのある特定の最小カットを見つける。本論文はKargerのアルゴリズムに対して新しい確率的評価を与える。ランダムグラフの特定の最小カットを見つける確率の期待値はΩ（/）であることを示す。ただし、pは枝を選ぶ確率である。さらに、密な一般グラフに対しても新しい結果を示す。Recently Karger proposed a new randomized algorithm for finding a minimum cut of an n-vertex graph with probability Ω(n^<-2&gt). In this paper we present a new probabilistic evaluation of Karger's randomized algorithm. For random graphs whose edges are selected with a given probability p, (log n)/n 〓 p 〓 1, we show that the expectation of success probability of the algorithm is Ω(p/n). We also investigate a class of graphs with special structure that consists of two n-cliques and γ(n-1) edges between the two cliques. Here γ is a parameter satisfying 0<γ<1 that makes γ(n-1) edges a unique minimum cut. We show that the algorithm finds the unique minimum cut with probability Ω(γ/(n^γ)). A tighter bound is also given for general dense graphs.

2値のエッジ画像から直線、円、楕円などのディジタル曲線成分を検出することは、パターン認識における最も基本的な問題の一つである。本論文では、ある条件を満たす様々な平面曲線について、そのすべての成分を抽出するための統一的な手法を提案する。曲線族の複雑度を反映する一つの測度dを導入し、提案するアルゴリズムがO（^）の時間と線形記憶領域だけで実行できることを示す。ただし、nはエッジ点の個数である。One of the most fundamental problems in pattern recognition is to detect digital components of planar curves such as lines, circles and ellipses in a binary edge image. In this paper we present a unified scheme for detecting all possible components of various planar curves satisfying a certain constraint. We introduce some measure d to reflect the complexity of a family of curves and show that the algorithm to be presented runs in O(n^d) time and linear space where n is the number of points.

画像処理に関する研究は最近の入出力機器の高性能化に伴って質的な変革を遂げようとしている。計算機の鮭力が非常に限定されていた頃には64×64画素の画像が実験に使われた時代もある。今や1000×1000の画像ですら当り前になって来ている。この入力サイズの爆発は計算時間と記憶スペースの面でも深刻な影響をもたらしている。画像のサイズが一定であれば、小手先の修正（たとえば、ある部分を機械語で置き換えるなど）で効果を上げることもできたが、対象画像のサイズがこのように大きくなって来ると計算量のオーダーを解析してアルゴリズムを設計することが必要になるものと思われる。ここでは、2値画像から直線成分を検出する問題に計算幾何学の分野で考え出されたアルゴリズム設計の方法論が役に立つことを示したい。

画像処理に関する研究は最近の入出力機器の高性能化に伴って質的な変革を遂げようとしている.計算機の能力が非常に限定されていた頃には64×64画素の画像が実験に使われた時代もある.今や1000×1000の画像ですら当り前になって来ている.この入力サイズの爆発な計算時間と記憶スペースの面でも深刻な影響をもたらしている.画像のサイズが一定であれば,小手先の修正(たとえば,ある部分を機械語で置き換えるなど)で効果を上げることもできたが,対象画像のサイズがこのように大きくなって来ると計算量のオーダーを解析してアルゴリズムを設計することが必要になるものと思われる.ここでは,2値画像から直接成分を検出する問題に計算斜何学の分野で考え出されたアルゴリズム設計の方法論が役に立つことを示したい.

ディジタル画像から直線成分を検出する問題は、パターン認識やロボット・ビジョンなどにおける基本的な問題である。この目的のために双対平面における投票に基づくHough変換法が広く利用されているようであるが、計算複雑度と直線抽出能力の関係を理論的に解析した研究は少ない。本論文では、ディジタル画像に含まれる極大な直線成分をもれなく確実に抽出するアルゴリズムを提案する。整数論の定理に基づいて効率を改善しているのが特徴である。上記の直線抽出能力を達成するために最低限必要な時間で処理を終えることができる。The problem of detecting lines components in a digital image is one of the most fundamental problems in pattern recognition and robot vision. Hough transform which is based on voting in the dual plane is widely used for this purpose. However, there have been few theoretical studies on the relationship between its computational complexity and ability of detecting straight lines. In this paper we present an algorithm for detecting every maximal line component contained in a digital image. This algorithm is designed to run efficiently based on Number Theory. It can complete the required task in least time needed to achieve the above-mentioned ability of line detection.

当論文は、ある問題に対して、部分的動的アルゴリズム(rtially dynamic algorit)が与えられた時、その問題に対する準オンライン動的アルゴリズム(lly dynamic semi?Online algorit)を求める手法を提案している。ここで、準オンラインの問題とは、オンライン問題の特殊な版であり、各更新リクエストσ時に、その後のk個の更新リクエストによって削除される要素を含むO（）のサイズの集合SS_σと全部のリクエストの数lが与えられているものである。もし、k=lであれば、問題は通常のオフライン問題になり、k=1ならば、全リクエストサイズが与えられた時のオンライン問題となる。最初に、O（√<#d+1>・)時間のサブセットサム問題の準オンラインアルゴリズムを与える。ここで、Kは目的の値であり、1個のリクエストのうち、#d個の削除リクエストがあるとする。また、（）連結問題に対するO（√<l（+）>√<#d>√<α（，）>+l，α（，））時間のアルゴリズム（は点の数である） （）整数ナップサック問題に対するO（√<#d・K>√<α(^<1．5>，）>+l・α(^<1．5>，））時間のアルゴリズム（は目標の値である） （）0?1ナップサック問題に対するO（^<9/4>c（#d+）^<1/4>）時間のアルゴリズム（は最適値である）を与える。また、サブセットサム問題の準オンラインアルゴリズムの応用として、最大各差最小の等分割問題がO（+n^<2．5>）時間で解けることを示す。これらの時間限界は、著者らの知る限り、新しく自明ではない。This paper proposes a new approach to obtain a semi-online dynamic algorithm, given a partially dynamic algorithm. A semi-online problem is a special case of online problems, in which for each update request σ we are given a superset SS_σ of size O(k) which contains all items to be deleted in the succeeding k update requests as well as the total number of requests as well as the total number of requests. Thus, a semi-online problem has properties both of online and office problems. Notice that an offline problem is also a semi-online problem. We first develop an O(√<#d+1>・lK) time algorithm for the semi-online dynamic Subset Sum problem where K is a target value and a series of l requests, including #d deletions, is made to the initially empty set. We also devise the following semi-online dynamic algorithms: (a) an O(√<l'l+n)>√<3D>√<α(l, n)>+l・α(l, n)) time algorithm for the connectivity problem where l (resp. #d) is the number of all (resp, delete) requests and n is the number of vertices, (b) an O(√<#d・K&gtl√<α(lK^<1.5>, K>+l・α(lK^<1.5>, K)) time algorithm for the Integer Knapsack problem where K is the target value, and (c) an O(l^<9/4> c(#d+1)^<1/4>) time algorithm for the optimization 0-1 Knapsack problem where c is the optimal value. As an application of the semi-online dynamic Subset Sum problem, we devise an O(m+n^<2.>5) time algorithm for the minimum range balanced cut problem. To the authors' knowledge, these bounds are new and nontrivial.

G=（，）をn個の節点とm本の枝からなる連結な無向グラフとするとき、Gの初等的カットのなかで枝数最小のカット（最小カット）を求める確率的アルゴリズムを提案し、その性能を計算機実験で評価する。アルゴリズムは最大格差最小カットを求める高速解法にもとずくもので、その理論的評価は未解決であるが、計算機実験の結果、最小カットを求める厳密解法と比較すると少ない計算量で最小カットに近いカットが求められることが確かめられた。また同様の手法をGを等分割する最小カットを求める問題（グラフの2分割問題）に対しても開発し、その性能を従来の Kernighan and Lin による近似解法と比較実験した。Let G=(V,E) be a connected undirected graph with n vertices and m. We shall propose a new randomized algorithm for finding a minimum cut based on a fast algorithm for finding a minimum range cut. Though the theoretical evaluation has not been done yet, computer experiments show that our algorithm outputs a cut very close to the exact minimum cut with the running time shorter than the best known algorithm for the minimum cut problem. We also propose a randomized algorithm based on the similar idea for finding a minimum cut of G into equal sizes. We also report the results of computer experiments that compare our algorithm with Kernighan and Lin's algorithm.

データベースシステムのスケジューラはデータの首尾一貫性を保証するために，各トランザクションのデータ項目への読出し()・書込み(i)要求の発生時に，その要求の遅延か許可，もしくはトランザクションのアボートを判断する．このうち先読みスケジューラは，データベースに様々な障害が起こった場合を除く正常な実行の範囲内において，後退復帰を必要とせず，デッドロックが生じないという優れた特性を持っている．すなわち，時刻印方式や二相ロック方式に見られるような，並行処理制御の方法自体が原因となるアボートは生じないことが保証されているため，デッドロックに対する対策は不要である．しかし実際問題として，ごくまれにトランザクションレベルあるいはシステムレベルでの障害の可能性はあるため，障害回復への対策は先読みスケジューラといえども避けることはできない．本稿では，単版方式においては，アボートが起こったとしてももとのデータ項目の値を回復できるようなアボート影響回避先読みスケジューラを提案し，一方多版方式においては，あるトランザクションのアボートが他の正常なトランザクションのアボートを引き起こすことのない，連鎖的アボート回避先読みスケジューラを提案する．Recovery control is an important issue in the practical design of transaction schedulers for database concurrency control. In view of this, we propose a single-version cautious scheduler which outputs strict schedules and a multiversion cautious scheduler which does not cause cascading aborts. Our main idea is to always assign each read operation to a committed write operation in order to avoid cascading aborts. Furthermore, it is not to allow executing each write operation until the last write on the same data item is committed in order to output strict schedules. We shall also compare the degree of concurrency attained by our schedulers with that by existing cautious scheduler.

平面上にn点の集合S={p_1，p_2，．．．，p_n}が与えられているものとする。Sの中の点対によって定まる（^n_）個のL_P距離を小さい順にd_1&le;d_2&le;・・・&le;d_<（^n_）>とする。本論文では次の2つの問題を扱う。（）（^n_）個のL_p距離のうち、最大のものからk個求める。（）（^n_）個のL_p距離のうち、最小のものからk個求める。この2つの問題に対するO(n{n^2，n+（^<4/3>/log^<1/3>）}log ）時間アルゴリズムを提案する。Given a finite set S of n points p_1,p_2,...,p_n in the plane, let d_1&le;d_2&le;・・・&le;d(^n_2) be the L_p-distances determined by the pairs of points in S, This paper considers the following two problems: Problem 1: For a given positive integer k&le;(^n_2), enumerate k pairs of points which realize d_<(^n_2)-k+1>,...,d_<(^n_2)>. Problem 2: For a given positive integer k&le;<(^n_2)>, enumerate k pairs of points which realized d_1,...d_k. We shall present an O(min{n^2,n+(k^<4/3>/log^<1/3>k)}log n) time algorithm for both problems.

Let MC stand for a class of logs (i.e. sequence of read/write steps) that are serializable when multiple versions of the data items are maintained. In this paper we propose three types of multiversion cautious schedulers which dynamically impose serialization constraints. The first scheduler always imposes rw(read-write)-constraints as well aas a subset of wr(write-read)-constraints. The second (resp. the third) scheduler always imposes only a subset of rw- and wr- (resp. ww-) constraints. These constraints are determined in an online manner in terms of a scheduler. We shall show that (i) all of these schedulers can be executed in polynomial time (ii) the degrees of concurrency of all these schedulers are higher than any of existing cautious schedulers such as CSm(MWW) and CSm(MWRW) if concurrency is measured in terms of their fixed point sets and (iii) they do not exhibit cancellation or augmentation anomaly. It is also shown that transactions need not predeclare their readsets and that all write requests can be immediately granted by these schedulers.Let MC stand for a class of logs (i.e., sequence of read/write steps) that are serializable when multiple versions of the data items are maintained. In this paper we propose three types of multiversion cautious schedulers which dynamically impose serialization constraints. The first scheduler always imposes rw(read-write)-constraints as well aas a subset of wr(write-read)-constraints. The second (resp. the third) scheduler always imposes only a subset of rw- and wr- (resp. ww-) constraints. These constraints are determined in an online manner in terms of a scheduler. We shall show that (i) all of these schedulers can be executed in polynomial time, (ii) the degrees of concurrency of all these schedulers are higher than any of existing cautious schedulers such as CSm(MWW) and CSm(MWRW), if concurrency is measured in terms of their fixed point sets, and (iii) they do not exhibit cancellation or augmentation anomaly. It is also shown that transactions need not predeclare their readsets, and that all write requests can be immediately granted by these schedulers.

平面上の与えられたn点から分散，直径最小のk点を求める問題に対して、それぞれO(k^2n + n log n) O(k^＆ｌｔ；2.5＆ｇｔ；n log k + n log n)時間のアルゴリズムを与える。両問題で、高次のVoronoi図を利用し、直径最小のk点を求める問題では、幾何的制約を有する2部グラフ上での最大独立点集合問題を幾何情報を十分利用しながら用いる。その過程で、高次のVoronoi図に関する新たな数え上げの結果も示す。The problems of finding a subset of k points with minimum variance and diameter among n given points in the plane are considered, and O(k^2n + n log n)-time and O(k^＆ｌｔ；2.5＆ｇｔ；n log k + n log n)-time, respectively, algorithms are given. Both algorithms make use of higher order Voronoi diagrams, and, the algorithm for finding k points with minimum diameter utilizes an independent set algorithm on a bipartite graph obtained from points by geometric conditions. New extremal results on the higher order Voronoi diagram are also established, which are used in the analysis of the algorithms.