Dualistic computational algebraic analyses of primal and dual minimum cost flow problems on acyclic tournament graphs

Details Dualistic computational algebraic analyses of primal and dual minimum cost flow problems on acyclic tournament graphs Dualistic computational algebraic analyses of primal and dual minimum cost flow problems on acyclic tournament graphs

2002-06-17

arxiv.org/abs/math/0206159v5

Mathematics

Combinatorics

20 pages, 6 figures

Scientific paper

To integer programming problems, computational algebraic approaches using Grobner bases or standard pairs via the discreteness of toric ideals have been studied in recent years. Although these approaches have not given improved time complexity bound compared with existing methods for solving integer programming problems, these give algebraic analysis of their structures. In this paper, we focus on the case that the coefficient matrix is unimodular, especially on the primal and dual minimum cost flow problems, whose structure is rather well-known, but new structures can be revealed by our approach. We study the Grobner bases and standard pairs for unimodular programming, and give the maximum number of dual feasible bases in terms of the volume of polytopes. And for the minimum cost flow problems, we characterize reduced Grobner bases in terms of graphs, and give bounds for the number of dual (resp. primal) feasible bases of the primal (resp. dual) problems: for the primal problems the minimum and the maximum are shown to be 1 and the Catalan number $\frac{1}{d}\tbinom{2(d-1)}{d-1}$, while for the dual problems the lower bound is shown to be $\Omega(2^{\lfloor d/6\rfloor})$. To analyze arithmetic degrees, we use two approaches: one is the relation between reduced Gr{\"o}bner bases and standard pairs, where the corresponding relation on the minimum cost flow -- between a subset of circuits and dual feasible bases -- has not been so clear, the other is the results in combinatorics related with toric ideals.

Affiliated with

Also associated with

No associations

Rating

Dualistic computational algebraic analyses of primal and dual minimum cost flow problems on acyclic tournament graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dualistic computational algebraic analyses of primal and dual minimum cost flow problems on acyclic tournament graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dualistic computational algebraic analyses of primal and dual minimum cost flow problems on acyclic tournament graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-603318