Some new results on the Littlewood-Offord problem

We consider the 2ⁿ sums of the form Σ?_ia_i with the a_i's vectors, | a_i | ? 1, and ?_i = 0, 1 for each i. We raise a number of questions about their distribution.We show that if the a_i lie in two dimensions, then at most $\text{n}\text{(}\text{n}\text{2}\text{)}$) sums can lie within a circle of diameter √3, and if n is even at most the sum of the three largest binomial coefficients can lie in a circle of diameter √5. These are best results under the indicated conditions.If two a's are more than 60° but less than 120° apart in direction, then the bound ($\text{n}\text{[}\text{n}\text{2}\text{]}$) on sums lying within a unit diameter sphere is improved to ($\text{n+1}\text{[}\text{n}\text{2}\text{]}\text{) ? 2(}\text{n?1}\text{[(n?}\text{1}\text{2}\text{)])}$.The method of Katona and Kleitman is shown to lead to a significant improvement on their two dimensional result.Finally, Lubell-type relations for sums lying in a unit diameter sphere are examined.     

The Littlewood-Offord problem and invertibility of random matrices

We prove two basic conjectures on the distribution of the smallest singular value of random n×n matrices with independent entries. Under minimal moment assumptions, we show that the smallest singular value is of order n−1/2, which is optimal for Gaussian matrices. Moreover, we give a optimal estimate on the tail probability. This comes as a consequence of a new and essentially sharp estimate in the Littlewood-Offord problem: for i.i.d. random variables Xk and real numbers ak, determine the probability p that the sum k_∑akXk lies near some number v. For arbitrary coefficients ak of the same order of magnitude, we show that they essentially lie in an arithmetic progression of length 1/p.     

Bilinear flocks of quadratic cones

A construction is given which provides infinitely many examples of bilinear flocks of quadratic cones in PG(3,K) whereK is an infinite field. The corresponding translation planes admit SL(2,K) as a collineation group.This article was written while the second author was visiting the University of Lecce during May and June of 1995. The authors gratefully acknowledge the support of the University of Lecce and the C.N.R. The authors would like to thanks for referees for helpful suggestions with the writing of this article.     

The Dirichlet problem on quadratic surfaces

We give a fast, exact algorithm for solving Dirichlet problems with polynomial boundary functions on quadratic surfaces in such as ellipsoids, elliptic cylinders, and paraboloids. To produce this algorithm, first we show that every polynomial in can be uniquely written as the sum of a harmonic function and a polynomial multiple of a quadratic function, thus extending a theorem of Ernst Fischer. We then use this decomposition to reduce the Dirichlet problem to a manageable system of linear equations. The algorithm requires differentiation of the boundary function, but no integration. We also show that the polynomial solution produced by our algorithm is the unique polynomial solution, even on unbounded domains such as elliptic cylinders and paraboloids.

     

A new bound for the quadratic assignment problem based on convex quadratic programming

We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and computational effort. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

The quadratic Waring-Goldbach problem

It is conjectured that Lagrange's theorem of four squares is true for prime variables, i.e. all positive integers n with are the sum of four squares of primes. In this paper, the size for the exceptional set in the above conjecture is reduced to .     

On the continuous quadratic knapsack problem

We introduce a new algorithm for the continuous bounded quadratic knapsack problem. This algorithm is motivated by the geometry of the problem, is based on the iterative solution of a series of simple projection problems, and is easy to understand and implement. In practice, the method compares favorably to other well-known algorithms (some of which have superior worst-case complexity) on problem sizes up ton = 4000.     

Contributions to the quadratic assignment problem

Tree search procedures for solving the Koopmans Beckmann quadratic assignment problem (QAP) are unable to solve any reasonable size QAP's mainly because good quality lower bounds for this problem cannot be computed.The purpose of this paper is to propose a bounding technique based on the extraction from the QAP formulation, of a large linear assignment problem (which can then be solved optimally), leaving as a residual problem as ‘small’ a QAP as possible. The solution of this residual QAP can then be bounded by a separate procedure. This 2-step method produces improved bounds as compared with those produced by the direct application of the bounding algorithms to the original QAP. In addition, a procedure is described for the a priori fixing of variables in the QAP formulation, thus reducing the number of variables in the problem.     

New bounds on the unconstrained quadratic integer programming problem

We consider the maximization for a given symmetric . It was shown recently, using properties of zonotopes and hyperplane arrangements, that in the special case that A has a small rank, so that A = VV ^T where with m < n, then there exists a polynomial time algorithm (polynomial in n for a given m) to solve the problem . In this paper, we use this result, as well as a spectral decomposition of A to obtain a sequence of non-increasing upper bounds on γ with no constraints on the rank of A. We also give easily computable necessary and sufficient conditions for the absence of a gap between the solution and its upper bound. Finally, we incorporate the semidefinite relaxation upper bound into our scheme and give an illustrative example.     

Network-based formulations of the quadratic assignment problem

We present two formulations of the Quadratic Assignment Problem (QAP) that result in network flow problems with integer variables and side constraints. A linearization of the QAP is obtained in both cases by considering each facility to consist of two parts—a source for all outgoing flows from that facility, and a sink for all incoming flows to the facility. Preliminary computational experience with both approaches is presented.     

Unconstrained quadratic bivalent programming problem

A branching and pruning algorithm is proposed to minimize an unconstrained quadratic function of 0–1 variables. A local minimizing point is defined; and a necessary and sufficient condition for such a point is identified. The algorithm generates all such local minimizing points. The computational experience with the algorithm, which is encouraging, is also given.     

Lower bounds for the quadratic assignment problem

We investigate the classical Gilmore-Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore-Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem.     

Ant colonies for the quadratic assignment problem

This paper presents HAS–QAP, a hybrid ant colony system coupled with a local search, applied to the quadratic assignment problem. HAS–QAP uses pheromone trail information to perform modifications on QAP solutions, unlike more traditional ant systems that use pheromone trail information to construct complete solutions. HAS–QAP is analysed and compared with some of the best heuristics available for the QAP: two versions of tabu search, namely, robust and reactive tabu search, hybrid genetic algorithm, and a simulated annealing method. Experimental results show that HAS–QAP and the hybrid genetic algorithm perform best on real world, irregular and structured problems due to their ability to find the structure of good solutions, while HAS–QAP performance is less competitive on random, regular and unstructured problems.     

Autocorrelation measures for the quadratic assignment problem

In this article we provide an exact expression for computing the autocorrelation coefficient ξ and the autocorrelation length ? of any arbitrary instance of the Quadratic Assignment Problem (QAP) in polynomial time using its elementary landscape decomposition. We also provide empirical evidence of the autocorrelation length conjecture in QAP and compute the parameters ξ and ? for the 137 instances of the QAPLIB. Our goal is to better characterize the difficulty of this important class of problems to ease the future definition of new optimization methods. Also, the advance that this represents helps to consolidate QAP as an interesting and now better understood problem.     

An analytic center quadratic cut method for the convex quadratic feasibility problem

 We consider a quadratic cut method based on analytic centers for two cases of convex quadratic feasibility problems. In the first case, the convex set is defined by a finite yet large number, N, of convex quadratic inequalities. We extend quadratic cut algorithm of Luo and Sun [3] for solving such problems by placing or translating the quadratic cuts directly through the current approximate center. We show that, in terms of total number of addition and translation of cuts, our algorithm has the same polynomial worst case complexity as theirs [3]. However, the total number of steps, where steps consist of (damped) Newton steps, function evaluations and arithmetic operations, required to update from one approximate center to another is , where ε is the radius of the largest ball contained in the feasible set. In the second case, the convex set is defined by an infinite number of certain strongly convex quadratic inequalities. We adapt the same quadratic cut method for the first case to the second one. We show that in this case the quadratic cut algorithm is a fully polynomial approximation scheme. Furthermore, we show that, at each iteration, k, the total number steps (as described above) required to update from one approximate center to another is at most , with ε as defined above. Received: April 2000 / Accepted: June 2002 Published online: September 5, 2002 Key words. convex quadratic feasibility problem – interior-point methods – analytic center – quadratic cuts – potential function     

A survey for the quadratic assignment problem

The quadratic assignment problem (QAP), one of the most difficult problems in the NP-hard class, models many real-life problems in several areas such as facilities location, parallel and distributed computing, and combinatorial data analysis. Combinatorial optimization problems, such as the traveling salesman problem, maximal clique and graph partitioning can be formulated as a QAP. In this paper, we present some of the most important QAP formulations and classify them according to their mathematical sources. We also present a discussion on the theoretical resources used to define lower bounds for exact and heuristic algorithms. We then give a detailed discussion of the progress made in both exact and heuristic solution methods, including those formulated according to metaheuristic strategies. Finally, we analyze the contributions brought about by the study of different approaches.     

The indefinite zero-one quadratic problem

A method is described for transforming an indefinite 0–1 quadratic programming problem into an equivalent positive definite problem of precisely the same size. Several variations of the basic transformation are incorporated in a branch and bound algorithm. This technique is combined with a system of analytical bounds on the variables. Computational results on several hundred random test problems with up to 30 variables demonstrate that the (polynomial bounded) transformation together with the bounds are sufficient to solve many large indefinite problems.     

The general quadratic optimization problem

A principal pivoting algorithm is given for finding local minimizing points for general quadratic minimization problems. The method is a generalization of algorithms of Dantzig, and Van de Panne and Whinston for convex quadratic minimization problems.This paper is based on part of the author's doctoral dissertation written under Dr. Robert M. Thrall at the University of Michigan. The author was partially supported by funds from contract number DA-ARO-D-31-124-0767 with the U.S. Army Research Office, Durham.