Author name cluster

Robert Hildebrand

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

SODA Conference 2017 Conference Paper

Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations

Robert Hildebrand
Robert Weismantel
Rico Zenklusen

We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on n vertices, with a polynomial number of constraints, requires many integer variables. By known reductions, this result extends to the traveling salesman polytope. This lower bound has various implications regarding the existence of small mixed-integer mathematical formulations of common problems in operations research. In particular, it shows that for many classic vehicle routing problems and problems involving matchings, any compact mixed-integer linear description of such a problem requires a large number of integer variables. This provides a first nontrivial lower bound on the number of integer variables needed in such settings.

Details

SODA Conference 2016 Conference Paper

An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra

Robert Hildebrand
Robert Weismantel
Kevin Zemmer

We present a generic approach that allows us to develop a fully polynomial-time approximation scheme (FTPAS) for minimizing nonlinear functions over the integer points in a rational polyhedron in fixed dimension. The approach combines the subdivision strategy of Papadimitriou and Yannakakis [22] with ideas similar to those commonly used to derive real algebraic certificates of positivity for polynomials. Our general approach is widely applicable. We apply it, for instance, to the Motzkin polynomial and to indefinite quadratic forms x T Q x in a fixed number of variables, where Q has at most one positive, or at most one negative eigenvalue. In dimension three, this leads to an FPTAS for general Q.

Details