Robust integer programming

We provide a complexity classification of four variants of robust integer programming when the underlying Graver basis is given. We discuss applications to robust multicommodity flows and multiway statistical table problems, and describe an effective parametrization of robust integer programming.     

Finding the Homology of Submanifolds with High Confidence from Random Samples

Recently there has been a lot of interest in geometrically motivated approaches to data analysis in high-dimensional spaces. We consider the case where data are drawn from sampling a probability distribution that has support on or near a submanifold of Euclidean space. We show how to “learn” the homology of the submanifold with high confidence. We discuss an algorithm to do this and provide learning-theoretic complexity bounds. Our bounds are obtained in terms of a condition number that limits the curvature and nearness to self-intersection of the submanifold. We are also able to treat the situation where the data are “noisy” and lie near rather than on the submanifold in question. The main results of this paper were first presented at a conference in honor of John Franks and Clark Robinson at Northwestern University in April 2003. These results were formally written as Technical Report No. TR-2004-08, Department of Computer Science, University of Chicago.     

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.     

A few remarks on sampling of signals with small spectrum

Given a bounded set S of small measure, we discuss the existence of sampling sequences for the Paley-Wiener space PW _S , which have both densities and sampling bounds close to the optimal ones.     

Tiebout and sympathy

In its simplest form the Tiebout hypothesis suggests that redistribution by local government is not sustainable because individuals, when confronted by negative net fiscal benefits, will vote with their feet, changing their residential locations to jurisdictions which offer a more favorable fiscal balance. It is usually thought, moreover, that they will move (e.g. from central city to suburbs) in descending order of income.Recognition of extended preference modifies this simple characterization of the tiebout process, in which the process of relocation is like ‘peeling an onion’. Any relocation sequence is possible, with either sympathy or antipathy. Even for sympathetic individuals with identical tastes, restrictive and unrealistic assumptions are required to predict, with certainty, that individuals with higher incomes would be the first to move. In particular the marginal tax rate must exceed unity. With antipathy, individuals with lower incomes may move before those with higher incomes, even if net fiscal benefits decrease with income, if they become more willing to begrudge transfers to others as their incomes increase.     

Generalizations of the odd degree theorem and applications

LetV ⊂ ℙℝ ⁿ be an algebraic variety, such that its complexificationV _ℂ ⊂ ℙ ⁿ is irreducible of codimensionm ≥ 1. We use a sufficient condition on a linear spaceL ⊂ ℙℝ ⁿ of dimensionm + 2r to have a nonempty intersection withV, to show that any six dimensional subspace of 5 × 5 real symmetric matrices contains a nonzero matrix of rank at most 3.     

Remarks on a principle of localization

We prove that the Brauer class of a crossed product is a sum of symbols iff its “local” components are. Analogously we show that a solution of the “Goldie rank conjecture” would follow from the “local” statements; an extension of a result of Cliff-Sehgal is an easy corollary.     

An Adaptive Algorithm for Vector Partitioning

The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L)v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output.     

Graphs of transportation polytopes

This paper discusses properties of the graphs of 2-way and 3-way transportation polytopes, in particular, their possible numbers of vertices and their diameters. Our main results include a quadratic bound on the diameter of axial 3-way transportation polytopes and a catalogue of non-degenerate transportation polytopes of small sizes. The catalogue disproves five conjectures about these polyhedra stated in the monograph by Yemelichev et al. (1984). It also allowed us to discover some new results. For example, we prove that the number of vertices of an m×n transportation polytope is a multiple of the greatest common divisor of m and n.