Probabilistic asymptotic properties of some combinatorial optimization problems

A class of combinatorial optimization problems with sum- and bottleneck objective function is described, having the following probabilistic asymptotic behaviour: With probability tending to one the ratio between worst and optimal objective function value approaches one as the size of the problem tends to infinity.Problems belonging to this class are among others quadratic assignment problems, as well as certain combinatorial and graph theoretical optimization problems.The obtained results suggest that even very simple heuristic algorithms incline to yield good solutions for high dimensional problems of this class.     

Probabilistic analysis of geometric location problems

We analyze the behaviour of thek center and median problems forn points randomly distributed in an arbitrary regionA ofR ^d . Under a mild assumption on the regionA, we show that fork≦k(n)=o(n/logn), the objective function values of the discrete and continuous versions of these problems are equal to each otheralmost surely. For the two-dimensional case, both these problems can be solved by placing the centers or medians in an especially simple regular hexagonal pattern (the ‘honeycomb heuristic’ of Papadimitriou). This yields the exact asymptotic values for thek center and median problem, namely, α(|A|/k)^1/2 and β(|A|/k)^1/2, where |A| denotes the volume ofA, α and β are known constants, and the objective of the median problem is given in terms of the average, rather than the usual total, distance. For the 3- and 4-dimensional case, similar results can be obtained for the center problem to within an accuracy of roughly one percent. As a by-product, we also get asymptotically optimal algorithms for the 2-dimensionalp-normk median problem and for the twin problems of minimizing the maximum number of vertices served by any center and similarly for maximizing the minimum.     

Special embeddings of some disconnected graphs into euclidean space

Embeddings of graphs into ℝ³ such that each line contains minimal possible number of points of the image are considered. It is proved that for every embedding into ℝ³ of a graph containing the disjoint union of two Kuratowski-Pontryagin graphs there exists a line containing four points of the image or more. Therefore, disjoint unions of Kuratowski-Pontryagin graphs are minimal 3-nonembeddable graphs.     

Probabilistic clustering via Pareto solutions and significance tests

The present paper proposes a new strategy for probabilistic (often called model-based) clustering. It is well known that local maxima of mixture likelihoods can be used to partition an underlying data set. However, local maxima are rarely unique. Therefore, it remains to select the reasonable solutions, and in particular the desired one. Credible partitions are usually recognized by separation (and cohesion) of their clusters. We use here the p values provided by the classical tests of Wilks, Hotelling, and Behrens–Fisher to single out those solutions that are well separated by location. It has been shown that reasonable solutions to a clustering problem are related to Pareto points in a plot of scale balance vs. model fit of all local maxima. We briefly review this theory and propose as solutions all well-fitting Pareto points in the set of local maxima separated by location in the above sense. We also design a new iterative, parameter-free cutting plane algorithm for the multivariate Behrens–Fisher problem.     

Solving capacitated clustering problems

This paper presents two effective algorithms for clustering n entities into p mutually exclusive and exhaustive groups where the ‘size’ of each group is restricted. As its objective, the clustering model minimizes the sum of distance between each entity and a designated group median. Empirical results using both a primal heuristic and a hybrid heuristic-subgradient method for problems having n ? 100 (i.e. 10 100 binary variables) show that the algorithms locate close to optimal solutions without resorting to tree enumeration. The capacitated clustering model is applied to the problem of sales force territorial design.     

On the complexity of some data analysis problems

NP-completeness of certain discrete optimization problems is proved. These are the problems to which one can reduce some important problems arising in data analysis when certain subsets of vectors are sought.     

On the complexity of some cluster analysis problems

NP-completeness of certain important clusterization problems for a finite set of vectors is proved.     

Probabilistic aspects of finite-fuel,reflected follower problems

The issue is that of following the path of a Brownian particle by a process of bounded total variation and subject to a reflecting barrier at the origin, in such a way as to minimize expected total cost over a finite horizon. We establish the existence of optimal processes and the dynamic programming equations for this question, and show (by purely probabilistic arguments) its relation to an appropriatefamily of optimal stopping problems with absorption at the origin.Work carried out during a visit by the second author at the University Pierre et Marie Curie (Paris VI), and at INRIA (Institut National de Recherche en Informatique et en Automatique). The hospitality of these institutions is gratefully acknowledged.Research supported in part by the U.S. Air Force Office of Scientific Research, under grant AFOSR-86-0203.     

Approximation algorithms for Hamming clustering problems

We study Hamming versions of two classical clustering problems. The Hamming radius p-clustering problem (HRC) for a set S of k binary strings, each of length n, is to find p binary strings of length n that minimize the maximum Hamming distance between a string in S and the closest of the p strings; this minimum value is termed the p-radius of S and is denoted by . The related Hamming diameter p-clustering problem (HDC) is to split S into p groups so that the maximum of the Hamming group diameters is minimized; this latter value is called the p-diameter of S.We provide an integer programming formulation of HRC which yields exact solutions in polynomial time whenever k is constant. We also observe that HDC admits straightforward polynomial-time solutions when k=O(logn) and p=O(1), or when p=2. Next, by reduction from the corresponding geometric p-clustering problems in the plane under the L₁ metric, we show that neither HRC nor HDC can be approximated within any constant factor smaller than two unless P=NP. We also prove that for any >0 it is NP-hard to split S into at most pk^1/7− clusters whose Hamming diameter does not exceed the p-diameter, and that solving HDC exactly is an NP-complete problem already for p=3. Furthermore, we note that by adapting Gonzalez' farthest-point clustering algorithm [T. Gonzalez, Theoret. Comput. Sci. 38 (1985) 293–306], HRC and HDC can be approximated within a factor of two in time O(pkn). Next, we describe a 2^O(p/)k^O(p/)n²-time (1+)-approximation algorithm for HRC. In particular, it runs in polynomial time when p=O(1) and =O(log(k+n)). Finally, we show how to find in

Full-size image

time a set L of O(plogk) strings of length n such that for each string in S there is at least one string in L within distance (1+), for any constant 0<<1.     

Partitional clustering via successive transportation problems

We propose to extend the spherical separation approach, amply used in supervised classification, to clustering problems by assigning each datum to a suitable sphere. Our idea consists in designing a heuristic approach based on solving successive transportation problems aimed at providing the radii of the clustering spheres, whose centers are fixed in advance as the barycenters of each current cluster, similarly to the well known K-Means algorithm. Numerical results show the effectiveness of our proposal.     

An alternating extragradient method with non euclidean projections for saddle point problems

In this work we analyze a first order method especially tailored for smooth saddle point problems, based on an alternating extragradient scheme. The proposed method is based on three successive projection steps, which can be computed also with respect to non Euclidean metrics. The stepsize parameter can be adaptively computed, so that the method can be considered as a black-box algorithm for general smooth saddle point problems. We develop the global convergence analysis in the framework of non Euclidean proximal distance functions, under mild local Lipschitz conditions, proving also the \(\mathcal {O}(\frac{1}{k})\) rate of convergence on the primal–dual gap. Finally, we analyze the practical behavior of the method and its effectiveness on some applications arising from different fields.     

Properly efficient and efficient solutions for vector maximization problems in euclidean space

Recently Benson proposed a definition for extending Geoffrion's concept of proper efficiency to the vector maximization problem in which the domination cone K is any nontrivial, closed convex cone. We give an equivalent definition of his notion of proper efficiency. Our definition, by means of perturbation of the cone K, seems to offer another justification of Benson's choice above Borwein's extension of Geoffrion's concept. Our result enables one to prove some other theorems concerning properly efficient and efficient points. Among these is a connectedness result.     

On some distribution problems in Manova and discriminant analysis

Asymptotic expansions, valid for large error degrees of freedom, are given for the multivariate noncentral F distribution and for the distribution of latent roots in MANOVA and discriminant analysis. The asymptotic results are expressed in terms of elementary functions which are easy to compute and the results of some numerical work are included. The Bartlett test of the null hypothesis that some of the noncentrality parameters in discriminant analysis are zero is also briefly discussed.     

Identifiability of factor analysis: some results and open problems

Identifiability of the factor analysis model is discussed, and some recent results and their relation to previous work are surveyed. Sufficient conditions for local identifiability are presented. A counterexample shows that these conditions are not necessary in general. A simple counting rule for local identifiability of the factor analysis model is given generically. Finally some open problems are formulated.     

Probabilistic analysis of combat models

This paper reviews recent developments in the field of stochastic combat models. A simple heterogeneous model with attrition rates dependent on the number of surviving forces is considered as a Markov process. Various characteristics of system dynamics are evaluated and expressed in explicit form. Numerical results to illustrate the difference between deterministic and stochastic models are presented. Some areas for further work are pointed out.