Abstract For $${\textbf {b}}=(b_1,\dots ,b_n)\in \mathbb {Z}_{>0}^n$$ b = ( b 1 , ⋯ , b n ) ∈ Z > 0 n , a $${\textbf {b}}$$ b -parking function is defined to be a sequence $$(\beta _1,\dots ,\beta _n)$$ ( β 1 , ⋯ , β n ) of positive integers whose nondecreasing rearrangement $$\beta '_1\le \beta '_2\le \cdots \le \beta '_n$$ β 1 ′ ≤ β 2 ′ ≤ ⋯ ≤ β n ′ satisfies $$\beta '_i\le b_1+\cdots + b_i$$ β i ′ ≤ b 1 + ⋯ + b i . The $${\textbf {b}}$$ b -parking-function polytope $$\mathfrak {X}_{n}({\textbf {b}})$$ X n ( b ) is the convex hull of all $${\textbf {b}}$$ b -parking functions of length n in $$\mathbb {R}^n$$ R n . Geometric properties of $$\mathfrak {X}_{n}({\textbf {b}})$$ X n ( b ) were previously explored in the specific case where $${\textbf {b}}=(a,b,b,\dots ,b)$$ b = (

Abstract. The investigation of combinatorial diameters of polyhedra is a classical topic in linear programming due to its connection with the possibility of an efficient pivot rule for the simplex method. We are interested in the diameters of polyhedra formed from the so-called parallel or series connection of oriented matroids. Oriented matroids are the natural way to connect representable matroid theory with the combinatorics of linear programming, and these connections are fundamental operations for the construction of more complicated matroids from elementary matroid blocks. We prove that, for polyhedra whose combinatorial diameter satisfies the Hirsch-conjecture bound regardless of the right-hand sides in a standard-form description, the diameters of their parallel or series connections remain small in the Hirsch-conjecture bound. These results are a substantial step toward devising a diameter bound for all polyhedra defined through totally unimodular matrices based on Seymour’s famous decomposition theorem. Our proof techniques and results exhibit a number of interesting features. While the parallel connection leads to a bound that adds just a constant, for the series connection one has to linearly take into account the maximal value in a specific coordinate of any vertex. Our proofs also require a careful treatment of non-revisiting edge walks in degenerate polyhedra as well as the construction of edge walks that may take a “detour" to facets that satisfy the non-revisiting conjecture when the underlying polyhedron may not.

Clustering is one of the fundamental tasks in data analytics and machine learning. In many situations, different clusterings of the same data set become relevant. For example, different algorithms for the same clustering task may return dramatically different solutions. We are interested in applications in which one clustering has to be transformed into another, e.g., when a gradual transition from an old solution to a new one is required. In this paper, we devise methods for constructing such a transition based on linear programming and network theory. We use a so-called clustering-difference graph to model the desired transformation and provide methods for decomposing the graph into a sequence of elementary moves that accomplishes the transformation. These moves are equivalent to the edge directions, or circuits, of the underlying partition polytopes. Therefore, in addition to a conceptually new metric for measuring the distance between clusterings, we provide new bounds on the circuit diameter of these partition polytopes.

Automatic finding of bugs in multithreaded programs is an important but inherently difficult task, even in the finite-state interleaving-semantics case. The complexity of this task has only been partially explored so far. We measure quantities such as the diameter, which is the longest finite distance realizable in the transition graph of the program, the local diameter, which is the maximum distance from any program state to any thread-local state, and the computational complexity of bugfinding. For the subclass of so-called binary multithreaded programs, we prove new bounds: all these quantities are majorized by a polynomial and, in certain cases, by a linear, logarithmic, or even constant function. Our bounds present a preparation step towards the corresponding polynomial-bound claims for general programs. These claims contrast sharply with the common belief that the main obstacle to analyzing concurrent programs is the exponential state explosion in the number of threads.

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 [Math. Oper. Res., 9 (1984), pp. 629--633]. 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.