BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Elisabeth Finhold

Elisabeth Finhold appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.OC

Catalog footprint

What is connected

5works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2015arXiv

The Hierarchy of Circuit Diameters and Transportation Polytopes

The study of the diameter of the graph of polyhedra is a classical problem in the theory of linear programming. While transportation polytopes are at the core of operations research and statistics it is still open whether the Hirsch conjecture is true for general $m{\times}n$--transportation polytopes. In earlier work the first three authors introduced a hierarchy of variations to the notion of graph diameter in polyhedra. The key reason was that this hierarchy provides some interesting lower bounds for the usual graph diameter. This paper has three contributions: First, we compare the hierarchy of diameters for the $m{\times}n$--transportation polytopes. We show that the Hirsch conjecture bound of $m+n-1$ is actually valid in most of these diameter notions. Second, we prove that for $3{\times}n$--transportation polytopes the Hirsch conjecture holds in the classical graph diameter. Third, we show for $2{\times}n$--transportation polytopes that the stronger monotone Hirsch conjecture holds and improve earlier bounds on the graph diameter.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Edges vs Circuits: a Hierarchy of Diameters in Polyhedra

The study of the graph diameter of polytopes is a classical open problem in polyhedral geometry and the theory of linear optimization. In this paper we continue the investigation initiated in [4] by introducing a vast hierarchy of generalizations to the notion of graph diameter. This hierarchy provides some interesting lower bounds for the usual graph diameter. After explaining the structure of the hierarchy and discussing these bounds, we focus on clearly explaining the differences and similarities among the many diameter notions of our hierarchy. Finally, we fully characterize the hierarchy in dimension two. It collapses into fewer categories, for which we exhibit the ranges of values that can be realized as diameters.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the circuit diameter of dual transportation polyhedra

In this paper we introduce the circuit diameter of polyhedra, which is always bounded from above by the combinatorial diameter. We consider dual transportation polyhedra defined on general bipartite graphs. For complete $M{\times}N$ bipartite graphs the Hirsch bound $(M{-}1)(N{-}1)$ on the combinatorial diameter is a known tight bound (Balinski, 1984). For the circuit diameter we show the much stronger bound $M{+}N{-}2$ for all dual transportation polyhedra defined on arbitrary bipartite graphs with $M{+}N$ nodes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Quadratic diameter bounds for dual network flow polyhedra

Both the combinatorial and the circuit diameters of polyhedra are of interest to the theory of linear programming for their intimate connection to a best-case performance of linear programming algorithms. We study the diameters of dual network flow polyhedra associated to $b$-flows on directed graphs $G=(V,E)$ and prove quadratic upper bounds for both of them: the minimum of $(|V|-1)\cdot |E|$ and $\frac{1}{6}|V|^3$ for the combinatorial diameter, and $\frac{|V|\cdot (|V|-1)}{2}$ for the circuit diameter. The latter strengthens the cubic bound implied by a result in [De Loera, Hemmecke, Lee; 2014]. Previously, bounds on these diameters have only been known for bipartite graphs. The situation is much more involved for general graphs. In particular, we construct a family of dual network flow polyhedra with members that violate the circuit diameter bound for bipartite graphs by an arbitrary additive constant. Further, it provides examples of circuit diameter $\frac{4}{3}|V| - 4$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Lower bounds on the Graver complexity of $M$-fold matrices

In this paper, we present a construction that turns certain relations on Graver basis elements of an $M$-fold matrix $A^{(M)}$ into relations on Graver basis elements of an $(M+1)$-fold matrix $A^{(M+1)}$. In doing so, we strengthen the bound on the Graver complexity of the $M$-fold matrix $A_{3\times M}$ from $g(A_{3\times M})\geq 17\cdot 2^{M-3}-7$ (Berstein and Onn) to $g(A_{3\times M})\geq 24\cdot 2^{M-3}-21$, for $M\geq 4$. Moreover, we give a lower bound on the Graver complexity $g(A^{(M)})$ of general $M$-fold matrices $A^{(M)}$ and we prove that the bound for $g(A_{3\times M})$ is not tight.

0 citations0 reviewsNo code linkedOpen access