Abstracts of Papers

Dissertation: "Computational Algebraic Analyses for Unimodular or Lawrence-Type Integer Programs

There have been a number of studies of the application of computational
algebraic approaches to solve integer programming problems, using
Gr{\"o}bner bases or standard pairs. By connecting these methods with
existing combinatorial methods for integer programming problems, we can
understand both methods deeply, and they have allowed new analysis of
their structures and construction of algorithms.

For an ideal over a polynomial ring, Gr{\"o}bner bases and the set of
standard pairs have duality as a Gr{\"o}bner basis is a generator of
the initial ideal, while the standard pair decomposition is a nice
decomposition of the set of monomials which does not contained in the
initial ideal. Such duality and consideration of a subclass of integer
programming problems where the duality theorem holds might give deeper
relation of two methods, and yield complexity bounds by making use of
the characteristics of the subclass, which could not be derived for
general integer programming problems. This thesis focuses on subclasses
where the coefficient matrix is unimodular or of the Lawrence type.

Problems in which the coefficient matrix $A$ is unimodular are a
mathematically nice subclass in the sense that the system $yA\leq c$
becomes totally dual integral (TDI) and each standard pair corresponds
to a dual feasible basis. In this dissertation, the method using
standard pairs is shown to be equivalent to calculation of the reduced
cost for each basis. Therefore, the number of standard pairs, which is
equal to that of dual feasible bases, gives the complexity of this
approach. The maximum number of dual feasible bases can be described by
the normalized volume of the polytope, defined by homogenizing
$A$. These results give a unified approach to analyze the number of
vertices of dual polyhedron via Gr{\"o}bner bases and volume
computations.

We also focused on transportation problems and minimum cost flow
problems. The Gr{\"o}bner basis approach for minimum cost flow
problems is a variant of the classical cycle-canceling algorithm: i.e.,
for any feasible flow the polynomial size of negative-cost cycles in the
residual network is chosen based on various rules and the flow is
augmented along these cycles as great a degree as possible. On the other
hand, the standard pair approach first finds the set of standard pairs,
and solves linear systems of equations for each standard pair until a
non-negative integer solution is obtained.

For transportation problems, several results about the number of
primal and dual feasible polyhedra have been reported. We give
computational algebraic proof for these results using above
approach. Furthermore, we study minimum cost flow problems on acyclic
tournament graphs, which are the most fundamental type of directed
graphs. The size of dual feasible bases for minimum cost flow problems
is shown to be less than the Catalan number, and the lower bound for the
size of primal feasible bases is shown to be of exponential order. For a
network optimization problem, the duality between the Gr{\"o}bner basis
and the set of standard pairs corresponds to the relation between
circuits and dual feasible co-trees, dually, cutsets and primal feasible
trees. As this relation has not been clarified previously, our results
using the computational algebraic duality are of interest.

On the other hand, in combinatorial optimization, Lawrence-type matrices
arise in many situations, e.g., in capacitated integer programming
problems and some multidimensional transportation problems. Furthermore,
Lawrence-type matrices are used in mathematical statistics in sampling or
enumeration of multi-way contingency tables of type $2\times M\times\cdots \times N$ with fixed marginal sums. The problem that
counts the number of 2-dimensional contingency tables with fixed
marginal sums has been shown to be \#P-complete. On the other hand,
Markov Chain Monte Carlo methods that have polynomial-time mixing times
have been studied for tables of type $2\times\cdots\times 2\times N$.

While the relationship between vector matroids defined by matrices of
Lawrence type and Gr{\"o}bner bases has been studied in detail, there
have been few investigations of standard pairs for matrices of Lawrence
type. This dissertation focuses on standard pairs that correspond to
dual feasible bases. We present here a bijection between the set of such
standard pairs and the set of bases of the vector matroid, and describe the
matroidal structure of these standard pairs. In particular, in cases in
which the matrix is unimodular, this relation indicates that the number
of dual feasible bases is equal to the number of bases of the vector
matroid. As a corollary, we analyze (i) the number of dual feasible
bases for the capacitated minimum cost flow problem on an acyclic
tournament graph, (ii) the number of dual feasible bases for
multidimensional transportation problems of type $2\times 2\times\cdots\times 2\times M\times N$, and (iii) the number of primal
feasible bases for multidimensional transportation problems of type
$2\times \cdots\times 2\times 2\times N$.

博士論文：「単模および Lawrence 型整数計画問題に対する計算代数的解析」

うことにより，双方の手法の理解が高まり，新たな構造解析手法やアルゴリズム
の構築が期待される．

り，standard pair の集合は初項イデアルに含まれない単項式の集合の分解であ
るため，双対の関係にあると言える．このような双対性に着目し，さらに双対定

き，一般的な整数計画問題からは得られないような計算量の上下限を得ることが
できると期待される．本論文では，そのような整数計画問題のクラスとして，係

する，という点で性質の良い問題のクラスである．本論文では，係数行列が単模
であるような整数計画問題に対して standard pair を用いた方法が，その
standard pair に対応する基底での被約コストを計算することと等価であること
を示す．よって，standard pair の数(つまり，双対実行可能基底の数)がこの方

Gr{\"o}bner 基底から体積計算を通じて双対多面体の頂点数を解析するという統

さらに，本論文では特に輸送問題，および最小費用流問題に着目する．これらの

ゴリズム，つまり実行可能流に対して残余ネットワーク内の負閉路を見つけて流
し変えていく方法の変形である．一方，standard pair を用いたアプローチでは，
まず standard pair の集合を求め，非負整数解が得られるまで，各 pair に対

に既存の結果が知られているが，ここでは上のアプローチによる計算代数的な証

および主実行可能基底の数が少なくとも指数オーダになることを示す．ネットワー
ク最適化問題において，Gr{\"o}bner 基底と双対実行可能基底の関係はサーキッ
トと双対実行可能補木(双対的には，カットセットと主実行可能木)の関係に対応
する．これらの関係はほとんど明らかにされていないので，この結果は計算代数

る多次元輸送問題など，多くの問題に現れる．また，数理統計学において，各行

ングや数え上げに Lawrence 型の行列が用いられることが知られている．行和の

いる一方で， $2\times 2\times \cdots\times 2\times N$ 型の分割表に対して，
mixing time が多項式時間となるマルコフ連鎖モンテカルロ法が提案されている．

Lawrence 型の行列に対して，行列の定めるベクトルマトロイドと Gr{\"o}bner

いない．そこで本論文では，特に双対実行可能基底に対応する standard pair
に着目する．まず，双対実行可能基底に対応する standard pair の集合とベク
トルマトロイドの基集合の間の全単射を与え，さらにそのような standard pair
たちのマトロイド的な構造を示す．特に，この関係は双対実行可能基底の数とベ
クトルマトロイドの基の数が等しいことを表している．さらにその系として，無

無閉路トーナメントグラフのトーリックイデアルに対するグレブナ基底の解析 / Analysis of Groebner Bases for Toric Ideals of Acyclic Tournament Graphs

Applications of Groebner bases to some computationally hard problems
in combinatorics using the discreteness of toric ideals have been studied
in recent years. On the other hand, the properties of graphs may give
insight into Groebner bases. Although toric ideals of undirected
complete graphs and bipartite graphs, which are homogeneous ideals, have
been studied well, those of other graphs are not well understood. For
the case of directed graphs, their universal Groebner basis
corresponds to the set of all the circuits of the graphs, but their
toric ideals are not homogeneous with respect to ordinary grading. Thus
toric ideals of directed graphs are interesting to study in graph
theory. In this thesis, we analyze toric ideals of acyclic tournament
graphs, which are the most fundamental directed graphs. We focus
especially on the degree and the number of elements of its reduced
Groebner bases.

We first give the positive grading which makes the toric ideals
homogeneous. We next give reduced Groebner bases for toric ideals
with respect to some term orders for both this grading and ordinary
grading. We show that there exist term orders for which reduced
Groebner bases remain in polynomial order by characterizing reduced
Groebner bases in terms of circuits. Note that the universal
Groebner basis for these graphs is of exponential size.

We next analyze the number of elements and degree of reduced Groebner
bases with respect to various term orders. Generally the degree of reduced
Groebner bases for toric ideals is at most of exponential order, but
in both cases of these two gradings, the degree remains in polynomial order
since the matrix is unimodular. We are interested in how the number of
elements can be bounded for the toric ideals of acyclic tournament
graphs. Using properties of the cycle space of graphs, we show that the
Groebner bases we have given above are the examples achieving minimum
number of elements or maximum degree in the case of ordinary grading. We
next calculate for graphs with small number of vertices, and give upper
bounds for the number of elements in the case of the grading whose toric
ideal become homogeneous. We also analyze the number of elements for the
purely lexicographic order.

We finally discuss applications to the minimum cost flow
problem. Algorithms for integer programming using Groebner bases have
been studied recently, and those complexity depends on the size of the
corresponding Groebner basis. We apply our results using these
algorithm to the minimum cost flow problem, analyze the complexity of
algorithms and relate to the complexity of minimum mean cycle-canceling
algorithm in minimum cost flow problem.

ける計算困難な問題に適用する研究が行われている．逆に，グラフの性質を用い
て Groebner 基底に関する面白い知見が得られる可能性もある．無向完全グ
ラフや無向完全二部グラフのトーリックイデアルは同次イデアルになるため多く
の研究がなされているが，他のグラフについてはほとんど研究されていない．有

では，中でも最も基本的な有向グラフである無閉路トーナメントグラフのトーリッ
クイデアルについて解析する．特に，Groebner 基底の次数や要素数に着目する．

まず，トーリックイデアルが同次イデアルになる次数付けを与え，その次数付け
および一般の次数付けに対して、いくつかの項順序に対するトーリックイデアル
の被約 Groebner 基底を与える．我々は被約 Groebner 基底をサーキット
により特徴づけることにより，被約 Groebner 基底の要素数が多項式オーダ
になるような項順序が存在することを示す．ここで，このグラフに対する普遍
Groebner 基底は指数サイズになることに注意しておく．

なるが，この2つの次数付けの場合，行列が単模になるため次数は多項式オーダ
になる．我々は，無閉路トーナメントグラフのトーリックイデアルの場合には，

Groebner 基底が要素数最小の例や次数最大の例になっていることを示す．ま
た，トーリックイデアルを同次イデアルにする次数付けに対して，頂点数の少な
いグラフに対して実験を行い，要素数の上限を考える．さらに，項順序を辞書式

さらに，これらの結果の最小費用流問題への応用を考える．近年，整数計画問題に

ムを用いて我々の結果を最小費用流問題に適用し，計算量を解析し，さらに最小

トーナメントグラフのトーリックイデアルのグレブナ基底 / Groebner Bases for Toric Ideals of Tournament Graphs

Application of Groebner bases to combinatorics through toric ideals
has been studied in recent years. On the other hand, the properties of
graphs may give insight for Groebner bases. So the toric ideals of
graphs have been studied. However, for special graphs, for example the number
of elements of their reduced Groebner basis have not been
analyzed. In this paper we enumerate, for the case of acyclic
tournament graphs, reduced Groebner bases with respect to some term
orders and analyze the number of elements. We also analyze the degree
and the number of elements in reduced Groebner bases with respect to
general term orders. Finally, we discuss an application to the shortest
path problem for acyclic tournament graphs.

ついての研究が行われている．グラフを特化した場合でも，例えば既約 Groebner 基

ラフについて，ある項順序での Groebner 基底を列挙し，要素数を解析する．
また，一般の項順序に対する既約 Groebner 基底の次数や要素数について解

無閉路有向グラフのトーリックイデアルに対するグレブナ基底の複雑度/ Complexity of Groebner Bases for Toric Ideals of Acyclic Directed Graphs

Applications of Groebner bases to some computationally hard problems in
combinatorics using the discreteness of toric ideals have been studied in
recent years. On the other hand, the properties of graphs may give
insight into Groebner bases. In this paper, we analyze toric ideals of
acyclic tournament graphs, which are the most fundamental directed
graphs. We focus especially on the number of elements of its reduced
Groebner bases. We show that there exist term orders for which reduced
Groebner bases remain in polynomial order by characterizing the bases in
terms of circuits. We next analyze the number of elements of reduced
Groebner bases with respect to various term orders. We finally discuss
applications to the minimum cost flow problem.

では，最も基本的な有向グラフである，無閉路トーナメントグラフのトーリ
ックイデアルを解析する．特に，被約 Groebner 基底の数に注目する．まず，
Groebner 基底をサーキットで特徴づけることにより，被約 Groebner 基底の

無閉路トーナメントグラフのグレブナ基底とベキ単行列の群上の超幾何系/ Groebner Bases of Acyclic Tournament Graphs and Hypergeometric Systems on the Group of Unipotent Matrices

Gelfand, Graev and Postnikov have calculated the number of independent
solutions of hypergeometric systems on the group of unipotent matrices.
These hypergeometric systems are related with the vertex-edge incidence
matrices of acyclic tournament graphs. In this paper, we show that the
results of Gelfand, Graev and Postnikov can be obtained by analyzing the
Groebner bases for toric ideals of acyclic tournament graphs. Moreover,
we study an open problem given by Gelfand, Graev and Postnikov.

Gelfand, Graev and Postnikov はベキ単行列の群上の超幾何系の線形独立な

デアルの Groebner 基底を解析することにより，Gelfand, Graev and Postnikov
の結果が得られることを示す．さらに，Gelfand, Graev and Postnikov によ
る未解決問題についても考察を行う．

無閉路有向グラフのグレブナ基底と Conti-Traverso アルゴリズムにおける簡約 / Groebner Bases of Acyclic Directed Graphs and Reductions in Conti-Traverso Algorithm

Algebraic approaches to some optimization problems on graphs applying
Conti-Traverso algorithm to Groebner bases of finite graphs have been
studied in recent years. On the other hand, the complexity of normal
form algorithms in Conti-Traverso algorithm is not well understood.
In this paper, we study the number of steps of reductions in Conti-
Traverso algorithm. We especially focus on the minimum cost flow
problems and the transportation problems on acyclic directed graphs,
and experiment the number of reductions in Conti-Traverso algorithm.

-Traverso のアルゴリズムを適用することによる代数的なアプローチが研究さ
れている．一方で，Conti-Traverso アルゴリズムにおける normal form アル
ゴリズムの計算量は解析されていない．本論文では，Conti-Traverso アルゴ
リズムにおける簡約の回数について調べる．特に，無閉路有向グラフ上での最

無閉路有向グラフのトーリックイデアルのグレブナ基底と最小費用流問題への応用 / Groebner Bases for Toric Ideals of Acyclic Directed Graphs and their Applications to Minimum Cost Flow Problem

Applications of Groebner bases to some computationally hard problems
in combinatorics using the discreteness of toric ideals have been
studied in recent years. On the other hand, the properties of graphs
may give insight into Groebner bases. In this paper, we analyze toric
ideals of acyclic directed graphs, which are the most fundamental
directed graphs. We focus especially on the number of elements of
their reduced Groebner bases. We show that there exist term orders for
which reduced Groebner bases remain in polynomial order by characterizing
the bases in terms of circuits of graphs. We next analyze the number of
elements of reduced Groebner bases with respect to various term orders.
We finally discuss applications to the minimum cost flow problem.

では，最も基本的な有向グラフである，無閉路有向グラフのトーリックイデア
ルを解析する．特に，被約 Groebner 基底の要素数に着目する．まず，Groebner

なるような項順序が存在することを示す．次に，任意の項順序に対する被約
Groebner 基底の要素数を解析する．最後に，最小費用流問題への応用について

Toric ideal の standard pair 分解と最小費用流問題 / Standard pair decompositions of toric ideals and minimum cost flow problems

To integer programming problems, computational algebraic approaches
using Gr{\"o}bner bases or standard pairs via the discreteness of toric
ideals have been studied in recent years. Although these approaches do
not give improved time complexity bound compared with existing methods
for solving integer programming problems, these give algebraic analysis
of structure of integer programming problems. In this paper, we focus
on the minimum cost flow problems, whose structure is well-known, and
analyze using standard pairs. Especially, using results about Gr{\"o}bner
bases for toric ideals and hypergeometric functions, we show that the
number of vertices of the (nondegenerate) dual polyhedra for minimum
cost flow problems on acyclic directed graphs is more than 1 and less
than the Catalan number.

のアプローチは既存の整数計画問題の解法に比べて計算量の改善を与えるもの
ではないが，整数計画問題の構造について代数的な解析を与えている．本論文
では，構造の知られている最小費用流問題に着目し，standard pair を用いた

ていない)双対多面体の頂点数の最小値が1になること，および最大値がカタラ
ン数になることを示す．

最小費用流問題の双対問題におけるトーリックイデアルの解析 / Analysis of toric ideal on dual problem of minimum cost flow

Recently algebraical approaches using toric ideal have been carried out,
and now the methods with Gr{\"o}bner basis and standard pair are paid
attention to. In this study, we focus to minimum cost flow problem on an
acyclic tournament graph and investigate its dual problem. First we prove
that universal Gr{\"o}bner basis of toric ideal is associated with circuit.
Next we focus the case that a cost vector is negative, we explain that the
size of Gr{\"o}bner basis becomes minimum, that by standard pairs generated
by Gr{\"o}bner basis arithmetic degree is $(d-1)!$ where $d$ is the number
of vertices, and that one standard pair corresponds to one feasible spanning
tree in the graph in primal problem. Then we suggest a conjecture that
arithmetic degree in dual problems is of exponential order even in minimum
cases, as opposed to primal problems.

アプローチが行われており,具体的にはそのグレブナ基底やstandard pairを用
いた手法が注目されている. 本研究では,無閉路トーナメントグラフ上の最小費

のグレブナ基底はサーキットをなすことを示す.次いで特にコストベクトルが負
であるときを取り上げ,この時グレブナ基底のサイズが最小であること,またグ
レブナ基底より得られたstandard pairより $d$を点の数としてarithmetic degree
が$(d-1)!$となること,およびstandard pairと主問題における実行可能な全域

り,最小の場合でも指数オーダーになるとの予想を提示する.

3次元多面体の geometric shellings / Geometric Shellings of 3-polytopes

A total order of the facets of a polytope is a geometric shelling if
there exists a combinatorially equivalent polytope in which the corresponding
order of facets becomes a line shelling. The subject of this paper is
(geometric) shellings of 3-polytopes. Recently, a graph theoretical
characterization of geometric shellings of 3-polytopes was given
by Holt & Klee and Mihalisin \& Klee.
• We first give a characterization of shellings of 3-polytopes.
Then we show sufficient conditions for a shelling to be geometric:
• the first and the last facet being adjacent,
• any facet (except the first two) being adjacent to no less than
two previous facets or
• the induced orders being geometric shellings for two smaller
polytopes made by dividing the polytope at a triple of
facets adjacent to each other but not sharing a vertex.
Simple 3-polytopes allow perturbations of facets, thus might have more
chance a shelling is geometric. As sufficient conditions for this case
we show:
• the induced order being a geometric shelling for a smaller polytope
joining two consecutive facets in a shelling or
• the polytope only having triangular or quadrilateral facets.
nongeometric shelling of a (simplicial) 3-polytope was first shown by Smilansky.
• We show such example for a simple $3$-polytope, which is minimal
with respect to the number of facets.
The discussions proceed in the polar setting: as total orders of vertices of
the polar polytope. All of our main results can be stated in graph theoretical
terms. The proof techniques used are elementary topology, graph theory, network
flows and local changes of polytopes.

ことをいう．本論文の対象は，3次元多面体の(幾何的)シェリングである．最近
Holt & Klee, Mihalisin & Klee により，3次元多面体の幾何的シェリングのグ
ラフ論的特徴付けが示された．
• まず，3次元多面体のシェリングの特徴付けを与える．

• 最初と最後のファセットが隣接している，または
• (最初の2つ以外の)任意のファセットがそれまでの少なくとも2つのファセ
ットに隣接している，または
• お互いに隣接しているが同じ頂点を共有しない3つのファセットで多面体
を分割してできる2つの小さな多面体に対し，それぞれ誘導される順序が
幾何的シェリングになっている．
を示す．

る可能性が高い．この場合の十分条件として，
• 三角形または四角形のファセットを除去，あるいはシェリングの連続する
2つのファセットを結合してできる小さな多面体に対して，誘導される順序が幾
何的シェリングになっている，あるいは
• 多面体が三角形か四角形のファセットしか持たない
ことを示す．
(単体的)3次元多面体の幾何的でないシェリングは Smilansky によって最初に示
された．
• 単純3次元多面体に対して，ファセットの数が最小である幾何的でないシェ
リングの例を示す．

る．すべての結果はグラフ理論的な言葉で表される．証明で用いられる技法は，

2地点での車両観測情報からの全域的交通流解析 / Analysis of Traffic Flow Using Vehicle Data Sequences at Two Observation Points

2 地点で収集した車長・車高の時系列データから，各車両の対応付けを推定し，

2 次元の文字列アライメント問題に帰着し，動的計画法 (Dynamic Programming: DP)
を用いて解くアルゴリズムを提案し，その実用性を実験によって検証する．さらに，

Getting the real time information of traffic is one of the important steps
towards realization of ITS. For this purpose, we propose a new method for
estimating travel time between designated two points and detecting the
correspondances of vehicles, by utilizing the observed lengths and heights
of vehicles．We formulate the problem of detecting the correspondances of
vehicles as the pairwise sequence alignment problem, by ignoring changes of
the order of vehicles. We also consider the utilization of image information
to improve the accuracy of correspondance. We examine the practicality of
our formulation by several experiments.

2地点車両観測情報からの全域的交通流解析アルゴリズム / An Algorithm of Traffic Flow Analysis Using Vehicle Data Sequences at Two Observation Points

2 地点で収集した車長・車高の時系列データから，各車両の対応付けを推定し，

2 次元の文字列アライメント問題に帰着し，動的計画法 (Dynamic Programming; DP)
を用いて解くアルゴリズムを提案し，その実用性を実験によって検証する．

Getting the real time information of traffic is one of the important steps
towards realization of ITS. For this purpose, we propose a new method for
estimating travel time between designated two points and detecting the
correspondances of vehicles, by utilizing the observed lengths and heights
of vehicles．We formulate the problem of detecting the correspondances of
vehicles as the pairwise sequence alignment problem, by ignoring changes of
the order of vehicles. We examine the practicality of our formulation by
several experiments.

Back to Papers / Papers のページに戻る
Takayuki Ishizeki
Last Update: 11 June, 2002.