For a given schedule of a round-robin tournament and a matrix of distances between homes of teams, an optimal home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance. We propose a technique to transform the problem to MIN RES CUT. We apply Goemans and Williamson’s 0.878-approximation algorithm for MAX … Read more
We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix *-representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending … Read more
Swarm Intelligence (SI) is the property of a system whereby the collective behaviors of (unsophisticated) entities interacting locally with their environment cause coherent functional global patterns to emerge. SI provides a basis with wich it is possible to explore collective (or distributed) problem solving without centralized control or the provision of a global model. In … Read more
Primal–dual interior point methods and the HKM method in particular have been implemented in a number of software packages for semidefinite programming. These methods have performed well in practice on small to medium sized SDP’s. However, primal–dual codes have had some trouble in solving larger problems because of the method’s storage requirements. In this paper … Read more
The semidefinite programming formulation of the Lovasz theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number and the clique number of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either number by adding … Read more
Swarm Intelligence (SI) is the property of a system whereby the collective behaviors of (unsophisticated) entities interacting locally with their environment cause coherent functional global patterns to emerge. SI provides a basis with wich it is possible to explore collective (or distributed) problem solving without centralized control or the provision of a global model. To … Read more
We present a practical approach to Anstreicher and Lee’s masked spectral bound for maximum-entropy sampling, and we describe favorable results that we have obtained with a Branch-&-Bound algorithm based on our approach. By representing masks in factored form, we are able to easily satisfy a semidefiniteness constraint. Moreover, this representation allows us to restrict the … Read more
When solving large-scale semidefinite programming problems by second-order methods, the storage and factorization of the Newton matrix are the limiting factors. For a particular algorithm based on the modified barrier method, we propose to use iterative solvers instead of the routinely used direct factorization techniques. The preconditioned conjugate gradient method proves to be a viable … Read more
The DIRECT algorithm was motivated by a modification to Lipschitzian optimization. The algorithm begins its search by sampling the objective function at the midpoint of an interval, where this function attains its lowest value, and then divides this interval by trisecting it. One of its weakness is that if a global minimum lies at the … Read more
This note, attempts to further Pan’s second-order quasi-Newton methods(\cite{panqn}). To complement the numerical implementation, the linear convergence of a rank-one second-order update and the least change property are presented. Citation 1,Department of Mathematics, Southeast University, Nanjing, 210096, P.R.China.