# 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$.

### $BGn;NO@J8!'!VC1LO$*$h$S(B Lawrence $B7?@0?t7W2hLdBj$KBP$9$k7W;;Be?tE*2r@O!W(B

$B@0?t7W2hLdBj$KBP$7$F!$6aG/(B Gr{\"o}bner $B4pDl$d(B standard pair $B$rMQ$$?7W;;(B BBe?tE* B&3HKhj!APJ}N BN9=C[,4|BT5lk!%(B BB?9<04D>eN%%G%"%kK*$$$F!$(BGr{\"o}bner $B4pDl$O=i9%$%G%"%k$N@8@.7O$G$"(B $B$j!$(Bstandard pair $B$N=89g$O=i9%$%G%"%k$K4^$^$l$J$$C19<0N=89gNJ,2rG"(B Bk?a!APBPN4X78K"kH8@(k!%3Nh&JAPBP@-KCeL\7!$$5$i$KAPBPDj(B
$BM}$N@.$jN)$D@0?t7W2hLdBj$N%/%i%9$r9M$($k$3$H$K$h$j!$$hjK-+J66EO7,G(B B-!0lHLE*J@0?t7W2hLdBj+iOF@ilJ$$$h$&$J7W;;NL$N>e2<8B$rF@$k$3$H$,(B
$B$G$-$k$H4|BT$5$l$k!%K\O@J8$G$O!$$=Nh&J@0?t7W2hLdBjN%/%i%9H7F!78(B B?t9TNs,C1LONH-!$$*$h$S(B Lawrence $B7?$G$"$k$H$-$KCeL\$9$k!%(B $B78?t9TNs(B $A$ $B$,C1LO$G$"$k$h$&$JLdBj$O!$ITEy<07O(B $yA\leq c$ $B$,40A4AP(B
$BBP@0?t@-(B (TDI) $B$rK~$?$7!$$5iK3F(B standard pair B,APBP B9k!$$H$$&E@G@- BG"kh&J@0?t7W2hLdBjKBP7F(B standard pair BrMQ$$$?J}K!$,!$$=N(B standard pair BKBP1~9k4pDlGNHoLs%3%9%Hr7W;;9k3HHEy2AG"k3H(B Br<(9!%hCF!(Bstandard pair BN?t(B(BD^j!APBP BK!N7W;;NLrM?(k!%5iK!APBP B@F Gr{\"o}bner B4pDl+iBN@Q7W;;rDL8FAPBPB?LLBNND:E@?tr2r@O9kH$$$&E}(B
$B0lE*$J%"%W%m!<%A$rM?$($k$3$H$,$G$-$k!%(B $B$5$i$K!$K\O@J8$G$OFC$KM"AwLdBj!$$*hS:G>.HqMQN.LdBjKCeL\9k!%3liN(B BLdBjKBP9k(B Gr{\"o}bner B4pDlrMQ$$$?%"%W%m!<%A$O!$4{B8$NIiJDO)>C5n%"%k(B $B%4%j%:%!$$D^j%M%C%H%o!<%/FbNIiJDO)r8+D1FN.(B B7JQ(F$$$/J}K!$NJQ7A$G$"$k!%0lJ}!$(Bstandard pair $B$rMQ$$?%"%W%m!<%AGO!(B B^:(B standard pair BN=89gr5aa!HsIi@0?t2r,F@ilk^G!3F(B pair BKBP(B B1~9k@~7?O"N)J}Dx<0r2r/J}K!G"k!%(B BM"AwLdBjN BK4{B8N7k2L,CNilF$$$k$,!$$33GO>eN%"%W%m!<%AKhk7W;;Be?tE*J>Z(B BL@rM?(k!%5iK!L5JDO)%H!<%J%a%s%H%0%i%U>eN:G>.HqMQN.LdBjKCeL\7!(B B:G>.HqMQN.LdBjKBP9kAPBP B*hS/J/Hb;X?t%*!<%@KJk3Hr<(9!%%M%C%H%o!<(B B%/:GE,2=LdBjK*$$$F!$(BGr{\"o}bner $B4pDl$HAPBP $B%H$HAPBP $B$9$k!%$3$l$i$N4X78$O$[$H$s$IL@$i$+$K$5$l$F$$J$$$N$G!$$3N7k2LO7W;;Be?t(B BE*APBP@-rMQ$$$?2r@O$NLLGr$$7k2LG"k!%(B B0lJ}!AH9g;:GE,2=K*$$$F!$(BLawrence $B7?$N9TNs$OMFNLIU$-@0?t7W2hLdBj$d$"(B
$B$kB? $BOB$r8GDj$7$?(B $2\times M\times\cdots\times N$ $B7?$NB? $B%s%0$d?t$(>e$2$K(B Lawrence $B7?$N9TNs$,MQ$$ilk3H,CNilF$$$k!%9TOB$N(B
$B8GDj$5$l$?(B2$B85J,3dI=$r?t$(>e$2$kLdBj$,(B \#P-complete $B$G$"$k$3$H$,CN$i$l$F(B
$B$$k0lJ}G!(B 2\times 2\times \cdots\times 2\times N B7?NJ,3dI=KBP7F!(B mixing time B,B?9<0;~4VHJk%^%k%3%UO":?%b%s%F%+%k%mK!,Ds0F5lF$$$k!%(B

Lawrence $B7?$N9TNs$KBP$7$F!$9TNs$NDj$a$k%Y%/%H%k%^%H%m%$%I$H(B Gr{\"o}bner $B4pDl$H$N4X78$ONI$/8&5f$5$l$F$$k,!(Bstandard pair BKD$$$F$ONI$/J,$+$C$F(B $B$$J$$!%$=$3$GK\O@J8$G$O!$FC$KAPBP $B$KCeL\$9$k!%$^$:!$APBP $B%H%k%^%H%m%$%I$N4p=89g$N4V$NA4C1 $B$?$A$N%^%H%m%$%IE*$J9=B$$r<(9!%FCK!$$3$N4X78$OAPBP $B%/%H%k%^%H%m%$%I$N4p$N?t$,Ey$7$$3HrI=7F$$$k!%$5$i$K$=$N7O$H$7$F!$L5(B $BJDO)%H!<%J%a%s%H%0%i%U>e$G$NMFNLIU$-:G>.HqMQN.LdBj$KBP$9$kAPBP $BDl$N?t!$(B$2\times 2\times\cdots\times 2\times M\times N$$B7?$NB? $BBj$KBP$9$kAPBP 2\times N$ $B7?$NB?

### $BL5JDO)%H!<%J%a%s%H%0%i%U$N%H!<%j%C%/%$%G%"%k$KBP$9$k%0%l%V%J4pDl$N2r@O(B / 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. $B6aG/!$%H!<%j%C%/%$%G%"%k$NN%;6@-$rMQ$$F(B Groebner B4pDlrAH9g;O@K*(B B1k7W;;:FqJLdBjKE,MQ9k8&5f,9TolF$$$k!%5U$K!$%0%i%U$N@- $B$F(B Groebner $B4pDl$K4X$9$kLLGr$$CN8+,F@ilk2DG=@-b"k!%L58~40A4%0(B B%i%UdL58~40A4FsIt%0%i%UN%H!<%j%C%/%%G%"%kOF1 BN8&5f,J5lF$$$k$,!$B>$N%0%i%U$K$D$$FO[HsI8&5f5lF$$$J$$!%M-(B B8~%0%i%UN>l9g!IaJW(B Groebner B4pDlO%0%i%UN%5!<%-%C%HA4BNN=89gKBP(B B1~9k,!0lHLN B8NK!M-8~%0%i%UN%H!<%j%C%/%%G%"%kN8&5fO%0%i%UM}O@E*KLLGr$$!%K\8&5f(B $B$G$O!$Cf$G$b:G$b4pK\E*$JM-8~%0%i%U$G$"$kL5JDO)%H!<%J%a%s%H%0%i%U$N%H!<%j%C(B $B%/%$%G%"%k$K$D$$F2r@O9k!%FCK!(BGroebner B4pDlN B^:!%H!<%j%C%/%%G%"%k,F1 B*hS0lHLN BNHoLs(B Groebner B4pDlrM?(k!%2f!9OHoLs(B Groebner B4pDlr%5!<%-%C%H(B BKhjFCD'E1k3HKhj!HoLs(B Groebner B4pDlNMWAG?t,B?9<0%*!<%@(B BKJkh&J9=g=x,B8:_9k3Hr<(9!%33G!$$3$N%0%i%U$KBP$9$kIaJW(B Groebner $B4pDl$O;X?t%5%$%:$K$J$k$3$H$KCm0U$7$F$*$/!%(B

$B $B0lHL$K%H!<%j%C%/%$%G%"%k$NHoLs(B Groebner $B4pDl$N $B$J$k$,!$$3N(B2BDNl9g!9TNs,C1LOKJk?a BKJk!%2f!9O!L5JDO)%H!<%J%a%s%H%0%i%UN%H!<%j%C%/%%G%"%kN>l9gKO!(B BMWAG?trIl@1M^(k3H,G-k+K6=L#,"k!%K\8&5fGO!0lHLN BIU1KBP7F%0%i%UN%5%%/%k6u4VN@-eGM?(?HoLs(B Groebner B4pDl,MWAG?t:G>.NNcd B?!%H!<%j%C%/%%G%"%krF1/J(B B$$%0%i%U$KBP$7$Fe8B$r9M$($k!%$5$i$K!$9=g=x$r<-=q<0(B
$B=g=x$K8BDj$7$?$H$-$NMWAG?t$K$D$$Fb2r@O9k!%(B B5iK!$$3$l$i$N7k2L$N:G>.HqMQN.LdBj$X$N1~MQ$r9M$($k!%6aG/!$@0?t7W2hLdBj$K(B
$B$^$?!$0lHL$N9=g=x$KBP$9$k4{Ls(B Groebner $B4pDl$N $B@O$9$k!%:G8e$K!$$3N%0%i%UN:GC;O)LdBjXNE,MQKD$$$F9M;!$9$k!%(B ### $BL5JDO)M-8~%0%i%U$N%H!<%j%C%/%$%G%"%k$KBP$9$k%0%l%V%J4pDl$NJ#;(EY(B/ 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.

$B6aG/!$%H!<%j%C%/%$%G%"%k$NN%;6@-$rMQ$$FAH9g;O@K*1k7W;;:FqJLd(B BBjK(B Groebner B4pDlrE,MQ9k8&5f,9TolF$$$k!%5U$K!$%0%i%U$N@- $BMQ$$F(B Groebner B4pDlK4X9kLLGr$$CN8+$,F@$i$l$k2DG=@-$b$"$k!%K\O@J8(B $B$G$O!$:G$b4pK\E*$JM-8~%0%i%U$G$"$k!$L5JDO)%H!<%J%a%s%H%0%i%U$N%H!<%j(B
$B%C%/%$%G%"%k$r2r@O$9$k!%FC$K!$HoLs(B Groebner $B4pDl$N?t$KCmL\$9$k!%$^$:!$(B Groebner $B4pDl$r%5!<%-%C%H$GFCD'$E$1$k$3$H$K$h$j!$HoLs(B Groebner $B4pDl$N(B $BMWAG?t$,B?9<0%*!<%@$K$J$k9=g=x$,B8:_$9$k$3$H$r<($9!% $B=g=x$KBP$9$kHoLs(B Groebner $B4pDl$NMWAG?t$r2r@O$9$k!%:G8e$K!$:G>.HqMQN.(B
$BLdBj$X$N1~MQ$r5DO@$9$k!%(B

### $BL5JDO)%H!<%J%a%s%H%0%i%U$N%0%l%V%J4pDl$H%Y%-C19TNs$N72>e$ND64v2?7O(B/ 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 $B$O%Y%-C19TNs$N72>e$ND64v2?7O$N@~7AFHN)$J(B $B2r$N?t$r7W;;$7$?!%$3$ND64v2?7O$OL5JDO)%H!<%J%a%s%H%0%i%U$NE@;^@\B39T(B
$BNs$K4X78$7$F$$k!%K\O@J8GO!L5JDO)%H!<%J%a%s%H%0%i%UN%H!<%j%C%/%(B B%G%"%kN(B Groebner B4pDlr2r@O9k3HKhj!(BGelfand, Graev and Postnikov BN7k2L,F@ilk3Hr<(9!%5iK!(BGelfand, Graev and Postnikov BKh(B BkL2r7hLdBjKD$$$F$b9M;!$r9T$&!%(B

### $BL5JDO)M-8~%0%i%U$N%0%l%V%J4pDl$H(B Conti-Traverso $B%"%k%4%j%:%$K$*$1$k4JLs(B / 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.

$B6aG/!$%0%i%U>e$N:GE,2=LdBj$KBP$7$F!$M-8B%0%i%U$N(B Groebner $B4pDl$K(B Conti
-Traverso $B$N%"%k%4%j%:%$rE,MQ$9$k$3$H$K$h$kBe?tE*$J%"%W%m!<%A$,8&5f$5(B $B$l$F$$k!%0lJ}G!(BConti-Traverso B%"%k%4%j%:%K*1k(B normal form B%"%k(B B%4%j%:%N7W;;NLO2r@O5lF$$$J$$!%K\O@J8GO!(BConti-Traverso B%"%k%4(B B%j%:%K*1k4JLsN2s?tKD$$$FD4$Y$k!%FC$K!$L5JDO)M-8~%0%i%U>e$G$N:G(B
$B>.HqMQN.LdBj$HM"AwLdBj$KCeL\$7!$(BConti-Traverso $B%"%k%4%j%:%$N4JLs$N2s(B
$B?t$r

### $BL5JDO)M-8~%0%i%U$N%H!<%j%C%/%$%G%"%k$N%0%l%V%J4pDl$H:G>.HqMQN.LdBj$X$N1~MQ(B / 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. $B6aG/!$AH9g$;O@$K$*$1$k7W;;:$Fq$JLdBj$KBP$7$F!$%H!<%j%C%/%$%G%"%k$NN%;6(B
$B@-$rMQ$$F(B Groebner B4pDlrE,MQ9k8&5f,9TolF$$$k!%0lJ}$G!$%0%i%U$N(B
$B@- $B$G$O!$:G$b4pK\E*$JM-8~%0%i%U$G$"$k!$L5JDO)M-8~%0%i%U$N%H!<%j%C%/%$%G%"(B $B%k$r2r@O$9$k!%FC$K!$HoLs(B Groebner $B4pDl$NMWAG?t$KCeL\$9$k!%$^$:!$(BGroebner $B4pDl$r%0%i%U$N%5!<%-%C%H$GFCD'$E$1$k$3$H$K$h$j!$MWAG?t$,B?9<0%*!<%@$K(B