Search

The standard quadratic optimization problem (StQP) refers to the problem of minimizing a quadratic form over the standard simplex. Such a problem arises from numerous applications and is known to be NP-hard. In a recent paper [Chen X, Peng J, Zhang S (2013) Sparse solutions to random standard quadratic optimization problems. Math. Programming 141(1–2):273–293], Chen, et al. showed that with a high probability close to 1, StQPs with random data have sparse optimal solutions when the associated data matrix is randomly generated from a certain distribution such as uniform and exponential distributions. In this paper, we present a new analysis for random StQPs combining probability inequalities derived from the first-order and second-order optimality conditions. The new analysis allows us to significantly improve the probability bounds. More important, it allows us to handle normal distributions, which is left open in Chen et al. (2013). The existence of sparse approximate solutions to convex StQPs and extensions to other classes of QPs are discussed as well.

In this paper, we establish hardness and approximation results for various Lp-ball constrained homogeneous polynomial optimization problems, where p ∈ [2, ∞]. Specifically, we prove that for any given d ≥ 3 and p ∈ [2, ∞], both the problem of optimizing a degree-d homogeneous polynomial over the Lp-ball and the problem of optimizing a degree-d multilinear form (regardless of its super-symmetry) over Lp-balls are NP-hard. On the other hand, we show that these problems can be approximated to within a factor of Ω((log n)(d−2)/p / nd/2−1) in deterministic polynomial time, where n is the number of variables. We further show that with the help of randomization, the approximation guarantee can be improved to Ω((log n/n)d/2−1), which is independent of p and is currently the best for the aforementioned problems. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where p ∈ {2, ∞}. We believe that the wide array of tools used in this paper will have further applications in the study of polynomial optimization problems.

Random sampling is a simple but powerful method in statistics and in the design of randomized algorithms. In a typical application, random sampling can be applied to estimate an extreme value, say maximum, of a function f over a set S ⊆ ℝn. To do so, one may select a simpler (even finite) subset S0 ⊆ S, randomly take some samples over S0 for a number of times, and pick the best sample. The hope is to find a good approximate solution with reasonable chance. This paper sets out to present a number of scenarios for f, S and S0 where certain probability bounds can be established, leading to a quality assurance of the procedure. In our setting, f is a multivariate polynomial function. We prove that if f is a d-th order homogeneous polynomial in n variables and F is its corresponding super-symmetric tensor, and ξi (i = 1, 2, …, n) are i.i.d. Bernoulli random variables taking 1 or −1 with equal probability, then Prob{f(ξ1, ξ2, …, ξn) ≥ τn−d/2 ‖F‖1} ≥ θ, where τ, θ > 0 are two universal constants and ‖·‖1 denotes the summation of the absolute values of all its entries. Several new inequalities concerning probabilities of the above nature are presented in this paper. Moreover, we show that the bounds are tight in most cases. Applications of our results in optimization are discussed as well.

We consider the single-machine scheduling problem to minimize the weighted sum of completion times under precedence constraints. In a series of recent papers, it was established that this scheduling problem is a special case of minimum weighted vertex cover. In this paper, we show that the vertex cover graph associated with the scheduling problem is exactly the graph of incomparable pairs defined in the dimension theory of partial orders. Exploiting this relationship allows us to present a framework for obtaining (2-2/f)-approximation algorithms, provided that the set of precedence constraints has fractional dimension of at most f. Our approach yields the best-known approximation ratios for all previously considered special classes of precedence constraints, and it provides the first results for bounded degree and orders of interval dimension 2. On the negative side, we show that the addressed problem remains NP-hard even when restricted to the special case of interval orders. Furthermore, we prove that the general problem, if a fixed cost present in all feasible schedules is ignored, becomes as hard to approximate as vertex cover. We conclude by giving the first inapproximability result for this problem, showing under a widely believed assumption that it does not admit a polynomial-time approximation scheme.

In a recent paper on semidefinite linear complementarity problems, Gowda and Song (2000) introduced and studied the P-property, P2-property, GUS-property, and strong monotonicity property for linear transformation L: Sn → Sn, where Sn is the space of all symmetric and real n × n matrices. In an attempt to characterize the P2-property, they raised the following two questions: (i) Does the strong monotonicity imply the P2-property? (ii) Does the GUS-property imply the P2-property? In this paper, we show that the strong monotonicity property implies the P2-property for any linear transformation and describe an equivalence between these two properties for Lyapunov and other transformations. We show by means of an example that the GUS-property need not imply the P2-property, even for Lyapunov transformations.

This paper investigates algebraic and combinatorial properties of the set of linear orders on the algebra of subsets of a finite set that are representable by positive measures. It is motivated by topics in decision theory and the theory of measurement, where an understanding of such properties can facilitate the design of strategies to elicit comparisons between subsets that, for example, determine an individual's preference order over subsets of objects or an individual's qualitative probability order over subsets of states of the world. We introduce a notion of critical pairs of binary comparisons for such orders and prove that (i) each order is uniquely characterized by its set of critical pairs and (ii) the smallest set of binary comparisons that determines an order is a subset of its set of critical pairs. The paper then focuses on the minimum number of on-line binary-comparison queries between subsets that suffice to determine any representable order for a set of given cardinality n. It is observed that, for small n, the minimum is attained by first determining the ordering of singleton subsets. We also consider query procedures with fixed numbers of stages, in each stage of which a number of queries for the next stage are formulated.

In this paper we present a tour of the symmetric traveling salesman polytope, focusing on inequalities that can be defined on sets of nodes. Most widely known inequalities are of this type. Many papers have appeared that give increasingly complex valid inequalities for this polytope, but little intuition on why these inequalities are valid has been given. To help in understanding these inequalities, we develop an intuition into their validity by giving a unifying way of defining them through a sequential lifting procedure. This procedure is based on lifting the slack variables associated with subtour elimination inequalities defined on sets of nodes (called teeth). We apply this procedure to some known classes of valid inequalities for the traveling salesman polytope (TSP) respectively comb, brush, star, path, and bipartition inequalities, where the lifting coefficients are sequence independent. For comb, star, and bipartition inequalities, we provide new and noninductive proofs of validity directly inspired by this lifting procedure. We also give an example where a facet-defining inequality is derived from the lifting procedure, but where the lifting coefficients are sequence dependent. We finally study the ladder inequalities and show that they can be generated by an extension of the general procedure, where the lifted variables are different from the slack variables of subtour elimination inequalities.

This paper studies two properties of the set of Markov chains induced by the deterministic policies in a Markov decision chain. These properties are called μ-uniform geometric ergodicity and μ-uniform geometric recurrence. μ-uniform ergodicity generalises a quasi-compactness condition. It can be interpreted as a strong version of stability, as it implies that the Markov chains generated by the deterministic stationary policies are uniformly stable. μ-uniform geometric recurrence can be shown to be equivalent to the simultaneous Doeblin condition, If μ is bounded. Both properties imply the existence of deterministic average and sensitive optimal policies. The second Key theorem in this paper shows the equivalence of μ-uniform geometric ergodicity and weak μ-uniform geometric recurrence under appropriate continuity conditions. In the literature numerous recurrence conditions have been used. The first Key theorem derives the relation between several of these conditions, which interestingly turn out to be equivalent in most cases.

In this paper we consider the temporal stochastic convexity and concavity properties of Markov processes {X(t), t ∈ S} in discrete time (then S = N+ ≡ {0, 1, 2, …}) or in continuous time (then S = [0, ∞)). That is, we obtain conditions on the process {X(t), t ∈ S} which imply that the expectation Ef(X(t)) is a monotone convex (concave) function of t whenever f is a monotone convex (concave) function. The theory is illustrated through some examples. After giving some background we define ℱ-monotonicity and then obtain some general results concerning stochastic convexity and concavity of Markov processes by using the notion of ℱ-monotone operators. We then introduce a method for identifying ℱ-monotone operators, and we discuss the relationship between our results concerning temporal convexity and other results in the literature. In particular, we center our attention on a notion of stochastic concavity. In this respect we show that a result of Shaked and Shanthikumar is incorrect and we prove two alternative versions of it. The approach that we use here is an operator-analytic approach. This approach is quite powerful, but not as intuitive as sample path approaches used in other papers. However, using it, we can obtain results that we could not obtain otherwise.

Let E be a finite set of elements, and let L be a clutter over ground set E. We say distinct elements e, f are opposite if every member and every minimal cover of L contains at most one of e, f. In this paper, we investigate opposite elements and reveal a rich theory underlying such a seemingly simple restriction. The clutter C obtained from L after identifying some opposite elements is called an identification of L; inversely, L is called a split of C. We will show that splitting preserves three clutter properties, i.e., idealness, the max-flow min-cut property, and the packing property. We will also display several natural examples in which a clutter does not have these properties but a split of them does. We will develop tools for recognizing when splitting is not a useful operation, and as well, we will characterize when identification preserves the three mentioned properties. We will also make connections to spanning arborescences, Steiner trees, comparability graphs, degenerate projective planes, binary clutters, matroids, as well as the results of Menger, Ford and Fulkerson, the Replication Conjecture, and a conjecture on ideal, minimally nonpacking clutters.

In this paper we study width of semialgebraic proof systems and various cut-based procedures in integer programming. We focus on two important systems: Gomory-Chvátal cutting planes and Lovász-Schrijver lift-and-project procedures. We develop general methods for proving width lower bounds and apply them to random k-CNFs and several popular combinatorial principles, like the perfect matching principle and Tseitin tautologies. We also show how to apply our methods to various combinatorial optimization problems. We establish a “supercritical” trade-off between width and rank, that is we give an example in which small width proofs are possible but require exponentially many rounds to perform them.

Recently, in He et al. [He BS, Tao M, Yuan XM (2012) Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22(2):313–340], we have showed the first possibility of combining the Douglas-Rachford alternating direction method of multipliers (ADMM) with a Gaussian back substitution procedure for solving a convex minimization model with a general separable structure. This paper is a further study on this theme. We first derive a general algorithmic framework to combine ADMM with either a forward or backward substitution procedure. Then, we show that convergence of this framework can be easily proved from the contraction perspective, and its local linear convergence rate is provable if certain error bound condition is assumed. Without such an error bound assumption, we can estimate its worst-case convergence rate measured by the iteration complexity.

Classified stable matching, proposed by Huang, describes a matching model between academic institutes and applicants, in which each institute has upper and lower quotas on classes, i.e., subsets of applicants. Huang showed that the problem to decide whether there exists a stable matching or not is NP-hard in general. On the other hand, he showed that the problem is solvable if classes form a laminar family. For this case, Fleiner and Kamiyama gave a concise interpretation in terms of matroids and showed the lattice structure of stable matchings. In this paper we introduce stable matchings on generalized matroids, extending the model of Fleiner and Kamiyama. We design a polynomial-time algorithm which finds a stable matching or reports the nonexistence. We also show that the set of stable matchings, if nonempty, forms a lattice with several significant properties. Furthermore, we extend this structural result to the polyhedral framework, which we call stable allocations on generalized polymatroids.

For an integer linear program, Gomory’s corner relaxation is obtained by ignoring the nonnegativity of the basic variables in a tableau formulation. In this paper, we do not relax these nonnegativity constraints. We generalize a classical result of Gomory and Johnson characterizing minimal cut-generating functions in terms of subadditivity, symmetry, and periodicity. Our result is based on the notion of generalized symmetry condition. We also prove a 2-slope theorem for extreme cut-generating functions in our setting, in the spirit of the 2-slope theorem of Gomory and Johnson.

Let G be a digraph and let π(G) be the linear system consisting of nonnegativity, stability, and domination inequalities. We call G kernel ideal if π(H) defines an integral polytope for each induced subgraph H of G, and we call G kernel Mengerian if π(H) is totally dual integral (TDI) for each induced subgraph H of G. In this paper we show that a digraph is kernel ideal iff it is kernel Mengerian iff it contains none of three forbidden structures; our characterization yields a polynomial-time algorithm for the minimum weighted kernel problem on kernel ideal digraphs. We also prove that it is NP-hard to find a kernel of minimum size even in a planar bipartite digraph with maximum degree at most three.

In 2010, Huang introduced the laminar classified stable matching problem (lcsm for short) that is motivated by academic hiring. This problem is an extension of the well-known hospitals/residents problem in which a hospital has laminar classes of residents and it sets lower and upper bounds on the number of residents that it can hire in each class. Against the intuition that variations of the stable matching problem with lower quotas are difficult in general, Huang proved that lcsm can be solved in polynomial time. In this paper, we present a matroid-based approach to lcsm and we obtain the following results. (i) We solve a generalization of lcsm in which both sides have quotas. (ii) Huang raised a question about a polyhedral description of the set of stable assignments in lcsm. We give a positive answer for this question by exhibiting a polyhedral description of the set of stable assignments in a generalization of lcsm. (iii) We prove that the set of stable assignments in a generalization of lcsm has a lattice structure that is similar to the (ordinary) stable matching problem.

In this paper two interpretations of the variable dimension algorithm to compute a fixed point of a continuous function from the product space S of simplices into itself, introduced in an earlier paper, are given. The first interpretation yields a subdivision, whereas the second one yields a triangulation of the convex hull of the set S on the natural level and some set on the artificial level. After labelling the vertices of the latter set in such a way that this set is completely labelled, a path of adjacent polyhedra (or simplices) can be generated with common completely labelled facets starting with the set on the artificial level and terminating with a completely labelled simplex on the natural level yielding an approximate fixed point. The intersection of the path with this level is the sequence of the simplices of variable dimension of the algorithm. So, the algorithm can be viewed as tracing zeroes of a piecewise linear homotopy function.

In two previous papers Prékopa (Prékopa, A. 1986a. Boole-Bonferroni inequalities and linear programming. Oper. Res. 36 145–162; Prékopa, A. 1986b. Sharp bounds on probabilities using linear programming. To appear in Oper. Res.) gave algorithms to approximate probabilities that at least r and exactly r out of n events occur (1 ≤ r ≤ n). Primal and dual linear programming problems were formulated and solved by dual type algorithms. The purpose of the present paper is to give closed forms for the basis inverse and the corresponding dual vector in case of an arbitrary basis, furthermore to give closed forms for the lower and upper bounds, approximating the probability in question, in case of a dual feasible basis. In the case when the probability that at least one out of n events occurs is approximated, it is shown that the absolute values of the components of any dual vector form a monotonically decreasing sequence. The paper improves the method of inclusion-exclusion, proves new probability inequalities and proves the sharpness of some known inequalities.

This paper considers a (multiplicative) process called branching Markov decision chains in which the output at the end of the Nth period equals the product of N nonnegative matrices chosen at the beginning of periods 1, …, N, respectively, times a positive (fixed) terminal reward vector. It is assumed that the above transition matrices are drawn out of a finite set of matrices given in product form (i.e., the rows of the matrices can be selected independently out of finite sets of nonnegative row vectors). For each coordinate s we define the geometric and algebraic growth rates, respectively, of the sth coordinate of the stream of output. These growth rates are defined so that the magnitude of the corresponding sequence is of the order αNNk where α is the geometric growth rate and k is the algebraic growth rate. The main result of this paper is the constructive establishment of the existence of a transition matrix whose repeated use will guarantee, for each coordinate, the achievement of the best geometric growth rate and the best algebraic growth rate subject to the geometric growth rate at maximum, among all potential sequences of transition matrices.

The Perron-Frobenius Theorem says that if A is a nonnegative square matrix some power of which is positive, then there exists an x0 such that Anx/‖Anx‖ converges to xn for all x > 0. There are many classical proofs of this theorem, all depending on a connection between positively of a matrix and properties of its eigenvalues. A more modern proof, due to Garrett Birkhoff, is based on the observation that every linear transformation with a positive matrix may be viewed as a contraction mapping on the nonnegative orthant. This observation turns the Perron-Frobenius theorem into a special ease of the Banach contraction mapping theorem. Furthermore, it applies equally to linear transformations which are positive in a much more general sense. The metric which Birkhoff used to show that positive linear transformations correspond to contraction mappings is known as Hilbert's projective metric. The definition of this metric is rather complicated. It is therefore natural to try to define another, less complicated metric, which would also turn positive matrices into contractions. The main result of this paper is that, essentially, this is impossible. The paper also gives some other results of possible interest in themselves, as well as enough background to make the presentation self-contained.

In this paper an algorithm based on the principle of simplicial approximation is introduced to compute fixed points of upper semicontinuous point to set mappings from the product space S of unit simplices into itself. The algorithm is a modification of an algorithm, introduced in an earlier paper. The main feature is that it starts with an arbitrary chosen point in S and that the triangulation of S depends on the starting point. Moreover, the algorithm can terminate with a non-full-dimensional subsimplex, yielding a good approximation. An application is given for non cooperative n person games, where S is the strategy space. Some computational experiences are given.

In this paper, we consider the sparse linear complementarity problem, denoted by k-LCP: the coefficient matrices are restricted to have at most k nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i.e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known complexity bound for the corresponding sparse linear feasibility problem. In addition, we show that an integer variant of the sign-balanced 2-LCP is weakly NP-hard and pseudo-polynomially solvable, and the generalized 1-LCP is strongly NP-hard.

In the classical k-median problem, we are given a metric space and want to open k centers so as to minimize the sum (over all the vertices) of the distance of each vertex to its nearest open center. In this paper we present the first constant-factor approximation algorithms for two natural generalizations of this problem that handle matroid or knapsack constraints. In the matroid median problem, there is an underlying matroid on the vertices and the set of open centers is constrained to be independent in this matroid. When the matroid is uniform, we recover the k-median problem. Another previously studied special case is the red-blue median problem where we have a partition matroid with two parts. Our algorithm for matroid median is based on rounding a natural linear programming relaxation in two stages, and it relies on a connection to matroid intersection. In the knapsack median problem, centers have weights and the total weight of open centers is constrained to be at most a given capacity. When all weights are uniform, this reduces to the k-median problem. The algorithm for knapsack median is based on a novel LP relaxation that constrains the set of centers that each vertex can get connected to. The rounding procedure uses a two-stage approach similar to that for matroid median.

It is well known that the permutahedron Πn has 2n − 2 facets. The Birkhoff polytope provides a symmetric extended formulation of Πn of size Θ(n2). Recently, Goemans described a non-symmetric extended formulation of Πn of size Θ(n log n). In this paper, we prove that Ω(n2) is a lower bound for the size of symmetric extended formulations of Πn. Moreover, we prove that the cardinality indicating polytope has the same tight lower bounds for the sizes of symmetric and nonsymmetric extended formulations as the permutahedron.

In this paper, we introduce a notion to be called k-wise uncorrelated random variables, which is similar but not identical to the so-called k-wise independent random variables in the literature. We show how to construct k-wise uncorrelated random variables by a simple procedure. The constructed random variables can be applied, e.g., to express the quartic polynomial (xTQx)2, where Q is an n × n positive semidefinite matrix, by a sum of fourth powered polynomial terms, known as Hilbert's identity. By virtue of the proposed construction, the number of required terms is no more than 2n4 + n. This implies that it is possible to find a (2n4 + n)-point distribution whose fourth moments tensor is exactly the symmetrization of Q ⊗ Q. Moreover, we prove that the number of required fourth powered polynomial terms to express (xTQx)2 is at least n(n + 1)/2. The result is applied to prove that computing the matrix 2 ↦ 4 norm is NP-hard. Extensions of the results to complex random variables are discussed as well.

Given a simple and undirected graph, nonnegative node weights, a nonnegative integer j, and a positive integer k, a k-matching in the graph is a subgraph with no isolated nodes and with maximum degree no more than k, a j-restricted k-matching is a k-matching with each connected component having at least j + 1 edges, and the total node weight of a j-restricted k-matching is the total weight of the nodes covered by the edges in the j-restricted k-matching. When j = 1 and k = 2, Kaneko [Kaneko A (2003) A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two. J. Combin. Theory, B 88:195–218] and Kano et al. [Kano M, Katona G, Király Z (2005) Packing paths of length at least two. Discrete Math. 283:129–135] studied the problem of maximizing the number of nodes covered by the edges in a 1-restricted 2-matching. In this paper, we consider the problem of finding a j-restricted k-matching with the maximum total node weight. We present a polynomial-time algorithm for the problem as well as a min-max theorem in the case of j < k. We also prove that, when j ≥ k ≥ 2, the problem of maximizing the number of nodes covered by the edges in a j-restricted k-matching is NP-hard.

Submodular maximization generalizes many fundamental problems in discrete optimization, including Max-Cut in directed/undirected graphs, maximum coverage, maximum facility location, and marketing over social networks. In this paper we consider the problem of maximizing any submodular function subject to d knapsack constraints, where d is a fixed constant. We establish a strong relation between the discrete problem and its continuous relaxation, obtained through extension by expectation of the submodular function. Formally, we show that, for any nonnegative submodular function, an α-approximation algorithm for the continuous relaxation implies a randomized (α − ε)-approximation algorithm for the discrete problem. We use this relation to obtain an (e−1 − ε)-approximation for the problem, and a nearly optimal (1 − e−1 − ε)-approximation ratio for the monotone case, for any ε > 0. We further show that the probabilistic domain defined by a continuous solution can be reduced to yield a polynomial-size domain, given an oracle for the extension by expectation. This leads to a deterministic version of our technique.

The question as to whether the Gomory-Chvátal closure of a nonrational polytope is a polytope has been a longstanding open problem in integer programming. In this paper, we answer this question in the affirmative by combining ideas from polyhedral theory and the geometry of numbers.

This paper provides a systematic solvability analysis for (generalized) variational inequalities on separable Hilbert lattices. By contrast to a large part of the existing literature, our approach is lattice-theoretic, and is not based on topological fixed point theory. This allows us to establish the solvability of certain types of (generalized) variational inequalities without requiring the involved (set-valued) maps be hemicontinuous or monotonic. Some of our results generalize those obtained in the context of nonlinear complementarity problems in earlier work, and appear to have scope for applications. This is illustrated by means of several applications to fixed point theory, optimization, and game theory.

Provan and Billera defined the notion of weak k-decomposability for pure simplicial complexes in the hopes of bounding the diameter of convex polytopes. They showed the diameter of a weakly k-decomposable simplicial complex Δ is bounded above by a polynomial function of the number of k-faces in Δ and its dimension. For weakly 0-decomposable complexes, this bound is linear in the number of vertices and the dimension. In this paper we exhibit the first examples of non-weakly 0-decomposable simplicial polytopes. Our examples are in fact polar to certain transportation polytopes.

This study is concerned with finding a level ideal (LI) of a partially ordered set (poset). Given a finite poset P, the level of each element p ∈ P is defined as the number of ideals that do not include p, then the problem is to find the ith LI–the ideal consisting of elements whose levels are less than a given integer i. The concept of a level ideal is naturally derived from the generalized median stable matchings, introduced by Teo and Sethuraman [Teo, C. P., J. Sethuraman. 1998. The geometry of fractional stable matchings and its applications. Math. Oper. Res. 23(4) 874–891] in the context of “fairness” of matchings in a stable marriage problem. Cheng [Cheng, C. T. 2010. Understanding the generalized median stable matchings. Algorithmica 58(1) 34–51] showed that finding the ith LI is #P-hard when i = Θ(N), where N is the total number of ideals of P. This paper shows that finding the ith LI is #P-hard even if i = Θ(N1/c), where c is an arbitrary constant at least one. Meanwhile, we present a polynomial time exact algorithm when i = O((log N)c′), where c′ is an arbitrary positive constant. We also devise two randomized approximation schemes for the ideals of a poset, by using an oracle of an almost-uniform sampler.

An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, the QAP and LAP objective function values are identical. Several sufficiency conditions are known that guarantee linearizability of a QAP. However, no polynomial time algorithm is known to test if a given instance of QAP is linearizable. In this paper, we give a necessary and sufficient condition for an instance of a QAP to be linearizable and develop an O(n4) algorithm to solve the corresponding linearization problem, where n is the size of the QAP.

A convex set with nonempty interior is maximal lattice-free if it is inclusion maximal with respect to the property of not containing integer points in its interior. Maximal lattice-free convex sets are known to be polyhedra. The precision of a rational polyhedron P in ℝd is the smallest natural number s such that sP is an integral polyhedron. In this paper we show that, up to affine mappings preserving ℤd, the number of maximal lattice-free rational polyhedra of a given precision s is finite. Furthermore, we present the complete list of all maximal lattice-free integral polyhedra in dimension three. Our results are motivated by recent research on cutting plane theory in mixed-integer linear optimization.

One of the most important variants of the standard linear assignment problem is the bottleneck assignment problem. In this paper we give a method by which one can find all of the asymptotic moments of a random bottleneck assignment problem in which costs (independent and identically distributed) are chosen from a wide variety of continuous distributions. Our method is obtained by determining the asymptotic moments of the time to first complete matching in a random bipartite graph process and then transforming those, via a Maclaurin series expansion for the inverse cumulative distribution function, into the desired moments for the bottleneck assignment problem. Our results improve on the previous best-known expression for the expected value of a random bottleneck assignment problem, yield the first results on moments other than the expected value, and produce the first results on the moments for the time to first complete matching in a random bipartite graph process.

We investigate in this paper the Lagrangian duality properties of linear equality constrained binary quadratic programming. We derive an underestimation of the duality gap between the primal problem and its Lagrangian dual or SDP relaxation, using the distance from the set of binary integer points to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyperplane arrangement. Alternative Lagrangian dual schemes via the exact penalty and the squared norm constraint reformulations are also discussed.

A hypergraph is called box-Mengerian if the linear system Ax ≥ 1, x ≥ 0 is box-totally dual integral (box-TDI), where A is the edge-vertex incidence matrix of the hypergraph. Because it is NP-hard in general to recognize box-Mengerian hypergraphs, a basic theme in combinatorial optimization is to identify such objects associated with various problems. In this paper, we show that the so-called equitably subpartitionable (ESP) property, first introduced by Ding and Zang (Ding, G., W. Zang. 2002. Packing cycles in graphs. J. Combin. Theory Ser. B 86 381–407) in their characterization of all graphs with the min-max relation on packing and covering cycles, turns out to be even sufficient for box-Mengerian hypergraphs. We also establish several new classes of box-Mengerian hypergraphs based on ESP property. This approach is of transparent combinatorial nature and is hence fairly easy to work with.

Quadratic assignment is a basic problem in combinatorial optimization that generalizes several other problems such as traveling salesman, linear arrangement, dense k subgraph, and clustering with given sizes. The input to the quadratic assignment problem consists of two n × n symmetric nonnegative matrices $W=(w_{i, j})$ and $D=(d_{i, j})$ . Given matrices W, D, and a permutation $\pi: [n] \rightarrow [n]$ , the objective function is $Q(\pi):= \sum_{i, j \in [n], i \ne j} w_{i, j} \cdot d_{\pi(i), \pi(j)}$ . In this paper, we study the maximum quadratic assignment problem, where the goal is to find a permutation π that maximizes $Q(\pi)$ . We give an $\tilde{O}(\sqrt{n})$ -approximation algorithm, which is the first nontrivial approximation guarantee for this problem. The above guarantee also holds when the matrices W, D are asymmetric. An indication of the hardness of maximum quadratic assignment is that it contains as a special case the dense k subgraph problem, for which the best-known approximation ratio is $\approx n^{1/3}$ (Feige et al. [Feige, U., G. Kortsarz, D. Peleg. 2001. The dense k-subgraph problem. Algorithmica29(3) 410--421]). When one of the matrices W, D satisfies triangle inequality, we obtain a $2e/(e-1) \approx 3.16$ -approximation algorithm. This improves over the previously best-known approximation guarantee of four (Arkin et al. [Arkin, E. M., R. Hassin, M. Sviridenko. 2001. Approximating the maximum quadratic assignment problem. Inform. Processing Lett.77 13--16]) for this special case of maximum quadratic assignment. The performance guarantee for maximum quadratic assignment with triangle inequality can be proved relative to an optimal solution of a natural linear programming relaxation that has been used earlier in branch-and-bound approaches (see, eg., Adams and Johnson [Adams, W. P., T. A. Johnson. 1994. Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Ser. Discrete Math. Theoret. Comput. Sci.16 43--77]). It can also be shown that this linear program (LP) has an integrality gap of $\tilde{\Omega}(\sqrt{n})$ for general maximum quadratic assignment.

We consider ranking and clustering problems related to the aggregation of inconsistent information, in particular, rank aggregation, (weighted) feedback arc set in tournaments, consensus and correlation clustering, and hierarchical clustering. Ailon et al. [Ailon, N., M. Charikar, A. Newman. 2005. Aggregating inconsistent information: Ranking and clustering. Proc. 37th Annual ACM Sympos. Theory Comput. (STOC '05), 684–693], Ailon and Charikar [Ailon, N., M. Charikar. 2005. Fitting tree metrics: Hierarchical clustering and phylogeny. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS '05), 73–82], and Ailon [Ailon, N. 2007. Aggregation of partial rankings, p-ratings and top-m lists. Proc. 18th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA '07), 415–424] proposed randomized constant factor approximation algorithms for these problems, which recursively generate a solution by choosing a random vertex as “pivot” and dividing the remaining vertices into two groups based on the pivot vertex. In this paper, we answer an open question in these works by giving deterministic approximation algorithms for these problems. The analysis of our algorithms is simpler than the analysis of the randomized algorithms. In addition, we consider the problem of finding minimum-cost rankings and clusterings that must obey certain constraints (e.g., an input partial order in the case of ranking problems), which were introduced by Hegde and Jain [Hegde, R., K. Jain. 2006. Personal communication]. We show that the first type of algorithms we propose can also handle these constrained problems. In addition, we show that in the case of a rank aggregation or consensus clustering problem, if the input rankings or clusterings obey the constraints, then we can always ensure that the output of any algorithm obeys the constraints without increasing the objective value of the solution.

In flow shop scheduling there are m machines and n jobs, such that every job has to be processed on the machines in the fixed order 1,…,m. In the permutation flow shop problem, it is also required that each machine process the set of all jobs in the same order. Formally, given n jobs along with their processing times on each machine, the goal is to compute a single permutation of the jobs σ: [n] → [n] that minimizes the maximum job completion time (makespan) of the schedule resulting from σ. The previously best known approximation guarantee for this problem was O((m log m)1/2) [Sviridenko, M. 2004. A note on permutation flow shop problem. Ann. Oper. Res. 129 247–252]. In this paper, we obtain an improved O(min{m1/2,n1/2}) approximation algorithm for the permutation flow shop scheduling problem, by finding a connection between the scheduling problem and the longest increasing subsequence problem. Our approximation ratio is relative to the lower bounds of maximum job length and maximum machine load, and is the best possible such result. This also resolves an open question from Potts et al. [Potts, C., D. Shmoys, D. Williamson. 1991. Permutation vs. nonpermutation flow shop schedules. Oper. Res. Lett. 10 281–284], by algorithmically matching the gap between permutation and nonpermutation schedules. We also consider the weighted completion time objective for the permutation flow shop scheduling problem. Using a natural linear programming relaxation and our algorithm for the makespan objective, we obtain an O(min{m1/2,n1/2}) approximation algorithm for minimizing the total weighted completion time, improving on the previously best known guarantee of εm for any constant ε > 0 [Smutnicki, C. 1998. Some results of the worst-case analysis for flow shop scheduling. Eur. J. Oper. Res. 109 66–87]. We give a matching lower bound on the integrality gap of our linear programming relaxation.

International audience; This paper deals with, direct proofs and combinatorial proofs of the famous necklace theorem of Alon, Goldberg, and West. The new results are a direct proof for the case of two thieves and three types of beads, and an efficient constructive proof for the general case with two thieves. This last proof uses a theorem of Ky Fan which is a version of Tucker's lemma concerning cubical complexes instead of Simplicial complexes. © 2008 INFORMS.

Rothblum showed that the convex hull of the stable matchings of a bipartite preference system can be described by an elegant system of linear inequalities. In this paper we prove that the description given by Rothblum is totally dual integral. We give a constructive proof based on the results of Gusfield and Irving on rotations, which gives rise to a strongly polynomial algorithm for finding an integer optimal dual solution.

Let M be a matroid on E∪{l}, where l ∉ E is a distinguished element of M. The l-port of M is the set 𝒫= {P: P ⊆ E with P∪{l} a circuit of M}. Let A be the 𝒫-E incidence matrix. Let U2, 4 be the uniform matroid on four elements of rank two, let F7 be the Fano matroid, let F7* be the dual of F7, and let F7+ be the unique series extension of F7. In this paper, we prove that the system Ax≥1, x≥0 is box-totally dual integral (box-TDI) if and only if M has no U2, 4-minor using l, no F7*-minor using l, and no F7+-minor using l as a series element. Our characterization yields a number of interesting results in combinatorial optimization.

In this paper, we lay the foundation for the study of the two-dimensional mixed integer infinite group problem (2DMIIGP). We introduce tools to determine if a given continuous and piecewise linear function over the two-dimensional infinite group is subadditive and to determine whether it defines a facet of 2DMIIGP. We then present two different constructions that yield the first known families of facet-defining inequalities for 2DMIIGP. The first construction uses valid inequalities of the one-dimensional integer infinite group problem (1DIIGP) as building blocks for creating inequalities for the two-dimensional integer infinite group problem (2DIIGP). We prove that this construction yields all continuous piecewise linear facets of the two-dimensional group problem that have exactly two gradients. The second construction we present has three gradients and yields facet-defining inequalities of 2DMIIGP whose continuous coefficients are not dominated by those of facets of the one-dimensional mixed integer infinite group problem (1DMIIGP).

In this paper, we explore properties of a family of probability density functions, called norm-induced densities, defined as [Formula: see text]where K is a n-dimensional convex set that contains the origin, parameters t > 0 and p > 0, and ‖·‖ is any norm. We also develop connections between these densities and geometric properties of K such as diameter, width of the recession cone, and others. Since ft is log-concave only if p ≥ 1, this framework also covers nonlog-concave densities. Moreover, we establish a new set inclusion characterization for convex sets. This leads to a new concentration of measure phenomena for unbounded convex sets. Finally, these properties are used to develop an efficient probabilistic algorithm to test whether a convex set, represented only by membership oracles (a membership oracle for K and a membership oracle for its recession cone), is bounded or not, where the algorithm reports an associated certificate of boundedness or unboundedness.

We consider a constrained homogeneous random walk in ℤ+d. Such random walks are used to model various stochastic processes, most importantly multiclass Markovian queueing networks operating under state-dependent scheduling policies. These applications motivate the need to compute various performance measures, including stationary probability distributions and large deviations rates. In this paper, we show that computing the stationary probability distributions exactly is an algorithmically undecidable problem. That is no algorithm can possibly exist to solve this task. The problem remains undecidable even if a linear Lyapunov function that verifies positive recurrence of the underlying random walk is available as a part of the input. We then prove that computing large deviation rates for this model is also an undecidable problem. Specifically, we show that it is an undecidable problem to determine finiteness of large deviations rates.