We consider the (block-angular) min–max resource sharing problem, which is defined as follows. Given finite sets of resources and of customers, a convex set c, called block, and a convex function gc:cR+ for every c, the task is to find bcc (c) approximately attaining :=infmaxrc(gc(bc))rbcc (c) . As usual we assume that g c can be computed efficiently and we have a constant ? ? 1 and oracle functions fc:R+c, called block solvers, which for c and yR+ return an element bcc with ygc(bc)infbcygc(b). We describe a simple algorithm which solves this problem with an approximation guarantee ?(1 + ?) for any ? > 0, and whose running time is O((+)log(loglog+?2)) for any fixed ? ? 1, where ? is the time for an oracle call. This generalizes and improves various previous results. We also prove other bounds and describe several speed-up techniques. In particular, we show how to parallelize the algorithm efficiently. In addition we review another algorithm, variants of which were studied before. We show that this algorithm is almost as fast in theory, but it was not competitive in our experiments. Our work was motivated mainly by global routing in chip design. Here the blocks are mixed-integer sets (whose elements are associated with Steiner trees), and we combine our algorithm with randomized rounding. We present experimental results on instances resulting from recent industrial chips, with millions of customers and resources. Our algorithm solves these instances nearly optimally in less than two hours.

Copositive optimization problems are particular conic programs: optimize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone from within, we propose a method which approximates this cone from outside. This is achieved by passing to the dual problem, where the feasible set is an affine subspace intersected with the cone of completely positive matrices, and this cone is approximated from within. We consider feasible descent directions in the completely positive cone, and regularized strictly convex subproblems. In essence, we replace the intractable completely positive cone with a nonnegative cone, at the cost of a series of nonconvex quadratic subproblems. Proper adjustment of the regularization parameter results in short steps for the nonconvex quadratic programs. This suggests to approximate their solution by standard linearization techniques. Preliminary numerical results on three different classes of test problems are quite promising.

We consider the following natural heuristic for the Symmetric Traveling Salesman Problem: solve the subtour relaxation, yielding a solution x?, and then find the best tour ¯ x that is compatible with x?, where compatible means that every subtour elimination constraint that is satisfied at equality at x? is also satisfied at equality at ¯ x. We prove that finding the best compatible tour is NP-hard and show that the tour can have a cost approaching 5/3 that of the optimal tour. We then describe a branch-and-cut algorithm for computing the best compatible tour, and present extensive computational results for TSPLIB instances. It turns out that, in practice, the tour is usually of very good quality. Moreover, the computational effort for computing the compatible tour is considerably smaller than that of solving the full problem with the best available software, i.e., Concorde.