Given $\cA := \{a^1,\ldots,a^m\} \subset \R^n$ and $\eps > 0$, we propose and analyze two algorithms for the problem of computing a $(1 + \eps)$-approximation to the radius of the minimum enclosing ball of $\cA$. The first algorithm is closely related to the Frank-Wolfe algorithm with a proper initialization applied to the dual formulation of … Read more
Given a weighted undirected graph $G=(V,E)$, a tree (respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree (resp. tour) cover problem is of finding a minimum weight tree (resp. tour) cover of $G$. Arkin, Halld\’orsson … Read more
We consider the computational complexity of optimizing various classes of continuous functions over a simplex, hypercube or sphere. These relatively simple optimization problems have many applications. We review known approximation results as well as negative (inapproximability) results from the recent literature. Citation CentER Discussion paper 2006-85 Tilburg University THe Netherlands Article Download View The complexity … Read more
A $k$-bit Hamming prefix code is a binary code with the following property: for any codeword $x$ and any prefix $y$ of another codeword, both $x$ and $y$ having the same length, the Hamming distance between $x$ and $y$ is at least $k$. Given an alphabet $A = [a_1,\ldots,a_n]$ with corresponding probabilities $[p_1,\ldots,p_n]$, the $k$-bit … Read more
Given a set of points $\cS = \{x^1,\ldots,x^m\} \subset \R^n$ and $\eps > 0$, we propose and analyze an algorithm for the problem of computing a $(1 + \eps)$-approximation to the the minimum volume axis-aligned ellipsoid enclosing $\cS$. We establish that our algorithm is polynomial for fixed $\eps$. In addition, the algorithm returns a small … Read more
A notorious open problem in the field of rendezvous search is to decide the rendezvous value of the symmetric rendezvous search problem on the line, when the initial distance apart between the two players is 2. We show that the symmetric rendezvous value is within the interval (4.1520, 4.2574), which considerably improves the previous best … Read more
Given $\cA := \{a^1,\ldots,a^m\} \subset \R^d$ whose affine hull is $\R^d$, we study the problems of computing an approximate rounding of the convex hull of $\cA$ and an approximation to the minimum volume enclosing ellipsoid of $\cA$. In the case of centrally symmetric sets, we first establish that Khachiyan’s barycentric coordinate descent (BCD) method is … Read more
Semidefinite optimization, commonly referred to as semidefinite programming, has been a remarkably active area of research in optimization during the last decade. For combinatorial problems in particular, semidefinite programming has had a truly significant impact. This paper surveys some of the results obtained in the application of semidefinite programming to satisfiability and maximum-satisfiability problems. The … Read more
We consider the problem of computing the minimum value $p_{\min}$ taken by a polynomial $p(x)$ of degree $d$ over the standard simplex $\Delta$. This is an NP-hard problem already for degree $d=2$. For any integer $k\ge 1$, by minimizing $p(x)$ over the set of rational points in $\Delta$ with denominator $k$, one obtains a hierarchy … Read more
We study the problem of computing a $(1+\eps)$-approximation to the minimum volume covering ellipsoid of a given set $\cS$ of the convex hull of $m$ full-dimensional ellipsoids in $\R^n$. We extend the first-order algorithm of Kumar and \Yildirim~that computes an approximation to the minimum volume covering ellipsoid of a finite set of points in $\R^n$, … Read more