In the cut-improvement problem, we are asked, given a starting cut (T,V\T) in a graph G, to find a cut with low conductance around(T, V\T) or produce a certificate that there is none. More precisely, for a notion of correlation between cuts, cut-improvement algorithms seek to produce approximation guarantees of the following form: for any … Read more
In this paper we define semidefinite packing programs and describe an algorithm to approximately solve these problems. Semidefinite packing programs arise in many applications such as semidefinite programming relaxations for combinatorial optimization problems, sparse principal component analysis, and sparse variance unfolding technique for dimension reduction. Our algorithm exploits the structural similarity between semidefinite packing programs … Read more
The p-median problem consists in locating p medians in a given graph, such that the total cost of assigning each demand to the closest median is minimized. In this work, a Lagrangean heuristic is proposed and it uses two dual information to build primal solutions. It outperforms a classic heuristic based on the same Lagrangean … Read more
This paper explores generalizations of the Goemans-Williamson randomization technique. It establishes a simple equivalence of binary linear feasibility problems and max-cut problems and presents an analysis of the semidefinite max-cut relaxation for the case of a single linear equation. Numerical examples for feasible random binary problems indicate that the randomization technique is efficient when the … Read more
Inspired by a question of Lov\’asz, we introduce a hierarchy of nested semidefinite relaxations of the convex hull of real solutions to an arbitrary polynomial ideal, called theta bodies of the ideal. For the stable set problem in a graph, the first theta body in this hierarchy is exactly Lov{\’a}sz’s theta body of the graph. … Read more
We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal-dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than … Read more
Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any … Read more
The number partitioning problem (NPP) is to divide n numbers a_1,…,a_n into two disjoint subsets such that the difference between the two subset sums – the discrepancy, D, is minimized. In the balanced version of NPP (BalNPP), the subsets must have the same cardinality. With $a_j$s chosen uniformly from $[1,R]$, R > 2^n gives the … Read more
This work addresses the computation of free-energy di fferences between protein conformations by using morphing (i.e., transformation) of a source conformation into a target conformation. To enhance the morph- ing procedure, we employ permutations of atoms; we transform atom n in the source conformation into atom \sigma(n) in the target conformation rather than directly transforming atom … Read more
We consider a quadratic programming (QP) problem ($\Pi$) of the form $\min x^T C x$ subject to $Ax \ge b$ where $C\in {\mathbb R}^{n\mbox{\tiny\texttimes} n}_+, rank(C)=1$ and $A\in {\mathbb R}^{m\mbox{\tiny\texttimes} n}, b\in {\mathbb R}^m$. We present an FPTAS for this problem by reformulating the QP ($\Pi$) as a parametrized LP and “rounding” the optimal solution. … Read more