universality

A sharp local threshold for integer feasibility in three-way transportation polytopes

Categories Integer Programming, Polyhedra Tags , , , , , ,

Abstract: A three-way transportation polytope consists of nonnegative three-way arrays with prescribed sums along every coordinate line. We show that its geometry and the difficulty of finding its integer points are both controlled by one local quantity: the number of cells on a line that can be positive. The change happens between two and three. … Read more

Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis

Categories Global Optimization Tags , ,

Average-case analysis computes the complexity of an algorithm averaged over all possible inputs. Compared to worst-case analysis, it is more representative of the typical behavior of an algorithm, but remains largely unexplored in optimization. One difficulty is that the analysis can depend on the probability distribution of the inputs to the model. However, we show … Read more