This survey covers the state of the art of techniques for solving general purpose constrained global optimization problems and continuous constraint satisfaction problems, with emphasis on complete techniques that provably find all solutions (if there are finitely many). The core of the material is presented in sufficient detail that the survey may serve as a … Read more
We present a multi-exchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between $3+2\sqrt{2}-\epsilon$ and $3+2\sqrt{2}+\epsilon$ for any given constant … Read more
Let $f$ be a continuous function on $\Rl^n$, and suppose $f$ is continuously differentiable on an open dense subset. Such functions arise in many applications, and very often minimizers are points at which $f$ is not differentiable. Of particular interest is the case where $f$ is not convex, and perhaps not even locally Lipschitz, but … Read more
The variational approach for electronic structure based on the two-body reduced density matrix is studied, incorporating two representability conditions beyond the previously used $P$, $Q$ and $G$ conditions. The additional conditions (called $T1$ and $T2$ here) are implicit in work of R.~M.~Erdahl [Int.\ J.\ Quantum Chem.\ {\bf13}, 697–718 (1978)] and extend the well-known three-index diagonal … Read more
We generalize new criss-cross type algorithms for linear complementarity problems (LCPs) given with sufficient matrices. Most LCP solvers require apriori information about the input matrix. The sufficiency of a matrix is hard to be checked (no polynomial time method is known). Our algorithm is similar to Zhang’s linear programming, and Akkeleº-Balogh-Illés’s criss-cross type algorithm for … Read more
We show that a simple genralization of the Deferred Acceptance Procedure with men proposing due to Gale and Shapley(1962), yeilds outcomes for a generalized marriage problem, which are necessarily stable. We also show, that any outcome of this prcedure is Weakly Pareto Optimal for Men, i.e., there is no other outcome which all men prefer … Read more
This work introduces a distributed branch-and-bound algorithm to be run on computational Grids. Grids are often organized in a hierarchical fashion: clusters of processors connected via high-speed links, while the clusters themselves are geographically distant and connected through slower links. Our algorithm does not employ the usual master-worker paradigm and it considers the hierarchical structure … Read more
We study the maximum stable set problem. For a given graph, we establish several transformations among feasible solutions of different formulations of Lov{\’a}sz’s theta function. We propose reductions from feasible solutions corresponding to a graph to those corresponding to its subgraphs. We develop an efficient, polynomial-time algorithm to extract a maximum stable set in a … Read more
This document contains references related to GRASP (greedy randomized adaptive search procedure) that have either appeared in the literature or as technical reports. If you are aware of any uncited reference, incorrectly cited reference, or update to a cited reference, please contact Mauricio G. C. Resende at the address given at the end of this … Read more
We propose a new method for non-bijective graph matching for model-based pattern recognition. We formulate the search for the best correspondence between a model and an over-segmented image as a new combinatorial optimization problem, defined by the relational attributed graphs representing the model and the image where recognition has to be performed, together with the … Read more