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

Raymond Hemmecke

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

ResearcherUnclaimed source record
math.OCmath.COmath.ACData Structures and AlgorithmsDiscrete MathematicsInformation Theorymath.ITmath.STQuantitative MethodsStatistics Theory

Catalog footprint

What is connected

20works
10topics
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

20 published item(s)

preprint2015arXiv

On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds-Karp to Bland and Beyond

Motivated by Bland's linear-programming generalization of the renowned Edmonds-Karp efficient refinement of the Ford-Fulkerson maximum-flow algorithm, we discuss three closely-related natural augmentation rules for linear and integer-linear optimization. In several nice situations, we show that polynomially-many augmentation steps suffice to reach an optimum. In particular, when using "discrete steepest-descent augmentations" (i.e., directions with the best ratio of cost improvement per unit 1-norm length), we show that the number of augmentation steps is bounded by the number of elements in the Graver basis of the problem matrix, giving the first ever strongly polynomial-time algorithm for $N$-fold integer-linear optimization. Our results also improve on what is known for such algorithms in the context of linear optimization (e.g., generalizing the bounds of Kitahara and Mizuno for the number of steps in the simplex method) and are closely related to research on the diameters of polytopes and the search for a strongly polynomial-time simplex or augmentation algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Connectivity of Fiber Graphs

We consider the connectivity of fiber graphs with respect to Gröbner basis and Graver basis moves. First, we present a sequence of fiber graphs using moves from a Gröbner basis and prove that their edge-connectivity is lowest possible and can have an arbitrarily large distance from the minimal degree. We then show that graph-theoretic properties of fiber graphs do not depend on the size of the right-hand side. This provides a counterexample to a conjecture of Engström on the node-connectivity of fiber graphs. Our main result shows that the edge-connectivity in all fiber graphs of this counterexample is best possible if we use moves from Graver basis instead.

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
preprint2012arXiv

Graver basis and proximity techniques for block-structured separable convex integer minimization problems

We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R. Weismantel, A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer Science, vol. 6080, Springer, 2010, pp. 219--229], it was proved that for fixed blocks but variable N, these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result [D.S. Hochbaum and J.G. Shanthikumar, Convex separable optimization is not much harder than linear optimization, J. ACM 37 (1990), 843--862], which allows us to use convex continuous optimization as a subroutine.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

N-fold integer programming in cubic time

N-fold integer programming is a fundamental problem with a variety of natural applications in operations research and statistics. Moreover, it is universal and provides a new, variable-dimension, parametrization of all of integer programming. The fastest algorithm for $n$-fold integer programming predating the present article runs in time $O(n^{g(A)}L)$ with $L$ the binary length of the numerical part of the input and $g(A)$ the so-called Graver complexity of the bimatrix $A$ defining the system. In this article we provide a drastic improvement and establish an algorithm which runs in time $O(n^3 L)$ having cubic dependency on $n$ regardless of the bimatrix $A$. Our algorithm can be extended to separable convex piecewise affine objectives as well, and also to systems defined by bimatrices with variable entries. Moreover, it can be used to define a hierarchy of approximations for any integer programming problem.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Reconstructing biochemical cluster networks

Motivated by fundamental problems in chemistry and biology we study cluster graphs arising from a set of initial states $S\subseteq\Z^n_+$ and a set of transitions/reactions $M\subseteq\Z^n_+\times\Z^n_+$. The clusters are formed out of states that can be mutually transformed into each other by a sequence of reversible transitions. We provide a solution method from computational commutative algebra that allows for deciding whether two given states belong to the same cluster as well as for the reconstruction of the full cluster graph. Using the cluster graph approach we provide solutions to two fundamental questions: 1) Deciding whether two states are connected, e.g., if the initial state can be turned into the final state by a sequence of transition and 2) listing concisely all reactions processes that can accomplish that. As a computational example, we apply the framework to the permanganate/oxalic acid reaction.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Challenging computations of Hilbert bases of cones associated with algebraic statistics

In this paper we present two independent computational proofs that the monoid derived from $5\times 5\times 3$ contingency tables is normal, completing the classification by Hibi and Ohsugi. We show that Vlach's vector disproving normality for the monoid derived from $6\times 4\times 3$ contingency tables is the unique minimal such vector up to symmetry. Finally, we compute the full Hilbert basis of the cone associated with the non-normal monoid of the semi-graphoid for $|N|=5$. The computations are based on extensions of the packages LattE-4ti2 and Normaliz.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Equality of Graver bases and universal Gröbner bases of colored partition identities

Associated to any vector configuration A is a toric ideal encoded by vectors in the kernel of A. Each toric ideal has two special generating sets: the universal Gröbner basis and the Graver basis. While the former is generally a proper subset of the latter, there are cases for which the two sets coincide. The most prominent examples among them are toric ideals of unimodular matrices. Equality of universal Gröbner basis and Graver basis is a combinatorial property of the toric ideal (or, of the defining matrix), providing interesting information about ideals of higher Lawrence liftings of a matrix. Nonetheless, a general classification of all matrices for which both sets agree is far from known. We contribute to this task by identifying all cases with equality within two families of matrices; namely, those defining rational normal scrolls and those encoding homogeneous primitive colored partition identities.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Learning restricted Bayesian network structures

Bayesian networks are basic graphical models, used widely both in statistics and artificial intelligence. These statistical models of conditional independence structure are described by acyclic directed graphs whose nodes correspond to (random) variables in consideration. A quite important topic is the learning of Bayesian network structures, which is determining the best fitting statistical model on the basis of given data. Although there are learning methods based on statistical conditional independence tests, contemporary methods are mainly based on maximization of a suitable quality criterion that evaluates how good the graph explains the occurrence of the observed data. This leads to a nonlinear combinatorial optimization problem that is in general NP-hard to solve. In this paper we deal with the complexity of learning restricted Bayesian network structures, that is, we wish to find network structures of highest score within a given subset of all possible network structures. For this, we introduce a new unique algebraic representative for these structures, called the characteristic imset. We show that these imsets are always 0-1-vectors and that they have many nice properties that allow us to simplify long proofs for some known results and to easily establish new complexity results for learning restricted Bayes network structures.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs

In this paper we generalize N-fold integer programs and two-stage integer programs with N scenarios to N-fold 4-block decomposable integer programs. We show that for fixed blocks but variable N, these integer programs are polynomial-time solvable for any linear objective. Moreover, we present a polynomial-time computable optimality certificate for the case of fixed blocks, variable N and any convex separable objective function. We conclude with two sample applications, stochastic integer programs with second-order dominance constraints and stochastic integer multi-commodity flows, which (for fixed blocks) can be solved in polynomial time in the number of scenarios and commodities and in the binary encoding length of the input data. In the proof of our main theorem we combine several non-trivial constructions from the theory of Graver bases. We are confident that our approach paves the way for further extensions.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Nonlinear Integer Programming

Research efforts of the past fifty years have led to a development of linear integer programming as a mature discipline of mathematical optimization. Such a level of maturity has not been reached when one considers nonlinear systems subject to integrality requirements for the variables. This chapter is dedicated to this topic. The primary goal is a study of a simple version of general nonlinear integer problems, where all constraints are still linear. Our focus is on the computational complexity of the problem, which varies significantly with the type of nonlinear objective function in combination with the underlying combinatorial structure. Numerous boundary cases of complexity emerge, which sometimes surprisingly lead even to polynomial time algorithms. We also cover recent successful approaches for more general classes of problems. Though no positive theoretical efficiency results are available, nor are they likely to ever be available, these seem to be the currently most successful and interesting approaches for solving practical problems. It is our belief that the study of algorithms motivated by theoretical considerations and those motivated by our desire to solve practical instances should and do inform one another. So it is with this viewpoint that we present the subject, and it is in this direction that we hope to spark further research.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

A polynomial oracle-time algorithm for convex integer minimization

In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex $N$-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex $N$-fold integer minimization problems for which our approach provides polynomial time solution algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Computation of Atomic Fibers of Z-Linear Maps

For given matrix $A\in\Z^{d\times n}$, the set $P_{b}=\{z:Az=b,z\in\Z^n_+\}$ describes the preimage or fiber of $b\in\Z^d$ under the $\Z$-linear map $f_A:\Z^n_+\to\Z^d$, $x\mapsto Ax$. The fiber $P_{b}$ is called atomic, if $P_{b}=P_{b_1}+P_{b_2}$ implies $b=b_1$ or $b=b_2$. In this paper we present a novel algorithm to compute such atomic fibers. An algorithmic solution to appearing subproblems, computational examples and applications are included as well.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension

We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. Moreover, using a weaker notion of approximation, we show the existence of a fully polynomial-time approximation scheme for the problem of maximizing or minimizing an arbitrary polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Pareto Optima of Multicriteria Integer Linear Programs

We settle the computational complexity of fundamental questions related to multicriteria integer linear programs, when the dimensions of the strategy space and of the outcome space are considered fixed constants. In particular we construct: 1. polynomial-time algorithms to exactly determine the number of Pareto optima and Pareto strategies; 2. a polynomial-space polynomial-delay prescribed-order enumeration algorithm for arbitrary projections of the Pareto set; 3. an algorithm to minimize the distance of a Pareto optimum from a prescribed comparison point with respect to arbitrary polyhedral norms; 4. a fully polynomial-time approximation scheme for the problem of minimizing the distance of a Pareto optimum from a prescribed comparison point with respect to the Euclidean norm.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Integer Polynomial Optimization in Fixed Dimension

We classify, according to their computational complexity, integer optimization problems whose constraints and objective functions are polynomials with integer coefficients and the number of variables is fixed. For the optimization of an integer polynomial over the lattice points of a convex polytope, we show an algorithm to compute lower and upper bounds for the optimal value. For polynomials that are non-negative over the polytope, these sequences of bounds lead to a fully polynomial-time approximation scheme for the optimization problem.

0 citations0 reviewsNo code linkedOpen access