The only general class of MAX-rCSP problems for which Polynomial Time Approximation Schemes (PTAS) are known are the dense problems. In this paper, we give PTAS's for a much larger class of weighted MAX-rCSP problems which includes as special cases the dense problems and, for r = 2, all metric instances (where the weights satisfy the triangle inequality) and quasimetric instances; for r > 2, our class includes a generalization of metrics. Our algorithms are based on low-rank approximations with two novel features: (1) a method of approximating a tensor by the sum of a small number of "rank-1" tensors, akin to the traditional Singular Value Decomposition (this might be of independent interest) and (2) a simple way of scaling the weights. Besides MAX-rCSP problems, we also give PTAS's for problems with a constant number of global constraints such as maximum weighted graph bisection and some generalizations.

Let k be a fixed integer. We consider the problem of partitioning an input set of points endowed with a distance function into k clusters. We give polynomial time approximation schemes for the following three clustering problems: Metric k-Clustering, l 22k-Clustering, and l22k-Median. In the k-Clustering problem, the objective is to minimize the sum of all intra-cluster distances. In the k-Median problem, the goal is to minimize the sum of distances from points in a cluster to the (best choice of) cluster center. In metric instances, the input distance function is a metric. In l 22 instances, the points are in R d and the distance between two points x,y is measured by x−y22 (notice that (R d, ⋅ 22 is not a metric space). For the first two problems, our results are the first polynomial time approximation schemes. For the third problem, the running time of our algorithms is a vast improvement over previous work.

We present a new efficient sampling method for approximating r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on n variables up to an additive error εnr. We prove a newgeneral paradigm in that it suffices, for a given set of constraints, to pick a small uniformly random subset of its variables, and the optimum value of the subsystem induced on these variables gives (after a direct normalization and with high probability) an approximation to the optimum of the whole system up to an additive error of εnr. Our method gives for the first time a polynomial in ε—1 bound on the sample size necessary to carry out the above approximation. Moreover, this bound is independent in the exponent on the dimension r. The above method gives a completely uniform sampling technique for all the MAX-rCSP problems, and improves the best known sample bounds for the low dimensional problems, like MAX-CUT. The method of solution depends on a new result on t he cut norm of random subarrays, and a new sampling technique for high dimensional linear programs. This method could be also of independent interest.

Metric MAX-CUT is the problem of dividing a set of points in metric space into two parts so as to maximize the sum of the distances between points belonging to distinct parts. We show that metric MAX-CUT has a polynomial time randomized approximation scheme.

Abstract In a given network with n vertices, a routing is defined as a set of n(n − 1) routes, one route connecting each ordered pair of vertices. The load of a vertex is the number of routes going through it. The forwarding index of the network is the minimum of the largest load taken over all routings. We show that the problem of determining the value of the forwarding index (respectively, the forwarding index of shortest routings) is an instance of the multicommodity flow problem (respectively, flow with multipliers). Since many very good heuristics or approximation algorithms are known for these flow problems, it follows from our results that all of these methods can be used for calculating the forwarding index. © 1994 by John Wiley & Sons, Inc.

This paper contains two probabilistic results about merging two sorted lists of sizes n and m with $m < n$. This paper designs a probabilistic algorithm, which in the worst case is significantly faster than any deterministic one in the range $1.618 < {n / m} \leqslant 3$. This paper extends it into a simple general algorithm that performs well for any ratio ${n / m}$. In particular, for ${n / m} > 1.618$ it is significantly faster than binary merge. This paper also proves an average case lower bound for a widely studied class of merging algorithms, when $1 < {n / {m < \sqrt 2 }} + 1$.