Consultar ensayos de calidad
Approximation schemes for densi instances of nphard problems  Applicable Optimization ProblemsPolynomial Time Approximation Schemes for Dense
Instances of N PHard Problems 1 Introduction Approximation algorithms, whenever they can be found, are a way to deal with the 1 have a fully polynomial time approximation scheme. These are known to exist for a few problems [GJ79, DFK91, KLM89].) Unfortunately, recent results ([ALM+ 92]) show that if P = N P, then PTASs do not exist for many N Phard problems. In particular, this is is true for every MAXSN Phard problem. (The class of MAXSN Phard problems includes VERTEX COVER, MAX3SAT, MAXCUT, METRIC TSP, MULTIWAY CUTS, and many others [PY91].) Note that the inapproximability results mentioned above, like all N Phardness results, rule out approximation only on worst case instances of the problem. They do not rule out the existence of algorithms (heuristics) that do well on most instances. This observation is the starting pointof our research. This paper gives PTASs for a large class of N Phard problems when the problem instance is dense. The deﬁnition of denseness depends on the problem; for example, dense graphs are graphs with Ω(n2 ) edges while dense 3SAT formulas are those with Ω(n3 ) clauses. Note that almost all graphs (asymptotically speaking) are dense, as are almost all 3SAT instances. The design of many (but not all) of our PTASs relies on the observation that many optimization problems can be phrased as nonlinear integer programs in which the objective function is a low degree polynomial. For dense problems, the optimum value of the objective function is quite large. Thus, to achieve a multiplicative approximation for dense instances it suﬃces to achieve an additive approximation for the nonlinear integer programming problem. We design such an additive approximation algorithm (see Sections 1.2 and 1.3). In the remainder of this introduction, we describe the problems we solve and sketch our solution techniques. 1.1 Applicable Optimization Problems We now describe the problems to which we apply our techniques. The reader will note that the problems span a broad spectrum. Some, like maximum cut and maximum ksatisﬁability, are MAXSN Pcomplete. Thus they do not have PTASs on general (that is, nondense) instances [ALM+ 92], but they can all be approximatedwithin some constant factor in polynomial time [PY91]. Others, like graph bisection and separation, do not currently have any algorithms with approximation ratios better than O(log n) on general instances. It is an open problem whether they are hard to approximate. MAXCUT: Partition the vertices of an undirected graph into two groups so as to maximize the number of edges with exactly one endpoint in each group. An algorithm in [GW94] achieves an approximation ratio of 1.13 for the problem. MAXDICUT: The directed version of the MAXCUT problem. An algorithm in [FG95] (improving [GW94]) achieves an approximation ratio of 1.15. MAXHYPERCUT(d): A generalization of MAXCUT to hypergraphs of dimension d; an edge is considered cut if it has at least one endpoint on each side. SEPARATOR: Partition the vertices of a graph into two groups, each with at least 1/3 of the vertices, so as to minimize the number of edges with exactly one endpoint in each group. An algorithm in [LR88] achieves approximation ratio O(log n) (though it may produce a 1/4 : 3/4 separator instead of a 1/3 : 2/3 separator). BISECTION: Partition the vertices of an undirected graph into two equal halves so as to minimize the number of edges with exactly one endpoint in each half. Some algorithms, for example using eigenvalues [B87] or simulated annealing [JS93] do well on certain random graphs(see also [BCLS84]). For worstcase inputs, no true approximation algorithms are known. Some known bisection approximators (based upon techniques 2 of [LR88]) yield separators whose capacity is within a factor O(log n) of the capacity of the optimum bisection. Our algorithm gives an exact bisection. MAXkSAT: Given a conjunctive normal form formula with k variables per clause, ﬁnd a truefalse assignment to the variables making the maximum possible number of clauses true. An algorithm in [Yan92] achieves an approximation ratio of 1.33 for the problem. Improved algorithms have since been given for MAX3SAT; an approximation ratio of 8/7 + ǫ is achieved in [KZ97]. It also known that achieving an approximation ratio of 8/7 − ǫ is N Phard [H97]. MINkCUT: Given an nvertex graph, remove a minimum set of edges that partitions the graph into k connected components. Saran and Vazirani [SV91] gave a (2 − 2/k)approximation algorithm. The variant kterminal cut problem speciﬁes k vertices that must all be disconnected from each other by the removal of the edges. Dalhaus et al. [DJP+ 94] give an algorithm that achieves an approximation ratio of (2 − 2/k). DENSEkSUBGRAPH: Given a graph, ﬁnd a subset of k vertices that induces a graph with the most edges. This problem was studied in [KP93], where an approximation algorithm with ratio n7/18 was presented.3COLORING: Color the vertices of a graph with 3 colors such that no two adjacent vertices have the same color. Application of our techniques to this problem yields a result already shown in [Edw86]. MAXSN P: The class of constant factor approximable problems deﬁned in [PY91]. We now deﬁne a natural notion of dense instance for each problem. (The deﬁnition of dense instances for the class MAXSN P appears in Section 4.4, where we also describe a PTAS for them.) Exact optimization on dense instances is N Phard for all problems except MINkCUT and 3COLORING (see Section 7). Deﬁnition 1.1. A graph is δdense if it has δn2 /2 edges. It is everywhereδdense if the minimum degree is δn. We abbreviate Ω(1)dense as dense and everywhereΩ(1)dense as everywheredense. Thus everywheredense implies dense, but not vice versa. Similarly, a kSAT formula is dense if it has Ω(nk ) clauses, and a dimensiond hypergraph if it has Ω(nd ) edges. Theorem 1.2. There are PTASs for everywheredense instances of BISECTION and SEPARATOR. Theorem 1.3. There are PTASs for dense instances of the following problems: MAXCUT, MAXDICUT, MAXkSAT for any constant k, DENSEkSUBGRAPH for k = Ω(n), MAXHYPERCUT(d) for constant d, and any MAXSN Pproblem. Theorem 1.4. Exact algorithms exist on everywheredense graphs for MINkCUT when k = o(n) and for 3COLORING. Remark. The3COLORING result is not newsee [Edw86]but does follow from a direct application of our general technique 1.2 Our Methods Our heuristics are based upon two main ideas: exhaustive sampling and its use in approximation of polynomial integer programs. We discuss these ideas in the context of the maximum cut problem (MAXCUT), one of the problems to which our techniques apply. The goal in MAXCUT is to partition the vertices of a given graph into two groups called the left and right sidesso as to maximize the number of edges with an endpoint 3 on each side. Notice that in the optimum solution, every vertex has the majority of its neighbors on the opposite side of the partition (else, it would improve the cut to move the vertex to the other side). Thus, if we knew where the neighbors of each vertex lay, we would know where to put each vertex. This argument may seem circular, but the circularity can be broken (in dense graphs) by the following exhaustive sampling approach. Suppose we take a sample of O(log n) vertices. By exhaustively trying all possible (i.e., 2O(log n) ) placements of the vertices in the sample, we will eventually guess where each vertex of the sample belongs in the optimum cut. Since there are 2O(log n) = nO(1) possibilities, we can aﬀord to try every one of them in polynomial time. So assume we have partitioned the sampledvertices correctly according to the optimal cut. Now consider some unsampled vertex. If a majority of its neighbors belong on the right side of the optimum cut, then we expect that a majority of its sampled neighbors will be from the right side of the optimum cut. This suggests the following scheme: put each unsampled vertex on the side opposite the majority of its sampled neighbors. This scheme works well for vertices whose oppositeside neighbors signiﬁcantly outnumber their sameside neighbors. More problematic are vertices for which the neighbors split evenly between the two sides; sampling will not typically give us conﬁdence about the majority side. This brings us to the second major idea of our paper: approximately solving nonlinear integer programs. Deﬁne a variable xi for vertex i which is 1 if the vertex is on the right side of a cut and 0 otherwise. Then ﬁnding a maximum cut corresponds to ﬁnding a 01 assignment that maximizes the following function (where E is the edge set of the graph): i To see this, note that the formula counts, for every vertex i on the right side of the cut, the number of edges leading from it to neighbors j on the left side of the cut. Of course, solving even linear integer programs is N Pcomplete, and the above program involves a quadratic objective function. However, we show that exhaustive sampling can be used toapproximately maximize such functions, and more generally, to approximately solve integer programs in which the constraints and objective involve lowdegree polynomials instead of linear functions. We state our main approximation result in the next section. Most of our approximation algorithms are more properly viewed as algorithms that compute an additive approximation (see Section 1.3). For example, our algorithm for MAXCUT computes, for every graph, a cut of capacity at least OP T − ǫn2 , where ǫ is any desired constant. Such an approximation is also within a small multiplicative factor of the optimum in a dense graph (i.e., one with Ω(n2 ) edges) because OP T = Ω(n2 ) for such graphs (this follows from our earlier observation that in an optimum cut, every vertex is on the opposite side from a majority of its neighbors). However, our algorithms for BISECTION and SEPARATOR are not additive approximation algorithms. xi (i,j) E (1 − xj ) . 1.3 Smooth Integer Programs Many existing approximation algorithms for N Phard problems are based on representation of the problem as a linear integer program (LIP). All problems in N P have such formulations since solving LIPs is N Pcomplete. Many problems have natural formuations as LIPs that give insight into their structure and lead to approximation algorithms. But formulation as a LIP masks thetrue nature of many other problemsin particular, an approximately optimum solution to the LIP may correspond to a far from optimum solution to the original optimization problem. A more natural formulation involves nonlinear integer program in which the objective function is a low degree polynomial. Most of our PTASs for dense problems are derived from such a representation. We solve a general class of optimization problems in which the objective function and the constraints are polynomials. 4 Deﬁnition 1.5. A polynomial integer program (or PIP) is of the form maximize p0 (x1 , . . . , xn ) subject to li ≤ pi (x) ≤ ui xi (1) (2) (3) (i = 1, . . . , m) i ≤ n where p0 , . . . , pm are polynomials. (The PIP could involve minimization instead of maximization.) When all pi have degree at most d, we call this program a degree d PIP. Since they subsume integer programs, it is clear that solving PIPs is N Phard. One might hope to deﬁne a more tractable class by eliminating the integrality requirement, but this accomplishes nothing since the 01 integrality of xi can be enforced by the quadratic constraint xi (xi − 1) = 0. We now describe a class of PIPs that are easy to approximate. Deﬁnition 1.6. An nvariate, degreed polynomial has smoothness c if the absolute value of each coeﬃcient of each degree i monomial (term) is at most c nd−i .Remark. The reader should think of c and d as being ﬁxed constants, and n as being allowed to grow. We call the resulting family of polynomials a family of csmooth degree d polynomials. Deﬁnition 1.7. A csmooth degreed PIP is a PIP in which the objective function and constraints are csmooth polynomials with degree at most d. Smooth integer programs can represent many combinatorial problems in a natural way. We illustrate this using MAXCUT as an example. Example 1.8. A degree2 polynomial with smoothness c has the form aij xi xj + bi xi + d where each aij  ≤ c, bi  ≤ cn, d ≤ cn2 . We show how to formulate MAXCUT on the graph G = (V, E) using a 2smooth integer program. Deﬁne a variable xi for each vertex vi . Then, assign 0, 1 values to the xi (in other words, ﬁnd a cut) so as to maximize (xi (1 − xj ) + xj (1 − xi )). E (Notice that an edge contributes 1 to the sum when xi = xj and 0 otherwise. Thus the sum is equal to the cut value.) Expanding the sum shows that the coeﬃcients of the quadratic terms are 0 and −2 while the coeﬃcients of the linear terms are at most n. Now we can state our general theorem about approximation of smooth integer programs. Deﬁnition 1.9. A solution a is said to satisfy a constraint li ≤ pi (x) ≤ ui to within an additive error δ if li − δ ≤ pi (a) ≤ ui + δ. Theorem 1.10. There is a randomizedpolynomialtime algorithm that approximately solves smooth PIPs, in the following sense. Given a feasible csmooth degree d PIP with n variables, objective function p0 and K constraints, the algorithm ﬁnds a 0/1 solution z satisfying p0 (z1 , . . . , zn ) ≥ OP T − ǫnd , 5 where OPT is the optimum of the PIP. This solution z also satisﬁes each degree d′ constraint ′ to within an additive factor of ǫnd for d′ > 1, and satisﬁes each linear constraint to within √ an additive error of O(ǫ n log n). The running time of the algorithm is O((dKnd )t ), where t = 4c2 e2 d2 /ǫ2 = O(1/ǫ2 ). The algorithm can be derandomized (i.e., made deterministic), while increasing the running time by only a polynomial factor. Remark. The statement of the theorem can be stronger: the input PIP does not need to be feasible, but only approximately feasible (that is, there must be a point that satisﬁes each ′ degree d′ constraint to within an additive error ǫ′ nd for some ǫ′ < ǫ/2.) Theorem 1.10 underlies almost all of our PTASs. However, our PTASs for BISECTION and MINkCUT require some additional ideas since an additive approximation is not good enough. 1.4 Related Work There are known examples of problems that are seemingly easier to approximate in dense graphs than in general graphs. For instance, in graphs with degree exceeding n/2, one can ﬁnd Hamiltonian cycles [P`and approximate the number of perfect matchings [JS89]. In 76] everywheredense graphs it is easy to approximate the values of the Tutte polynomial and, as a special case, to estimate the reliability of a network [AFW94]. Independent of our work, Fernandez de la Vega [FdlV94] developed a PTAS for everywheredense MAXCUT using exhaustive sampling principles similar to ours. After sampling and guessing, Fernandez de la Vega replaces our linearprogramming solution with a greedy placement procedure. While this procedure is signiﬁcantly simpler than ours (at least conceptually; the running time is still dominated by the exhaustive sampling procedure and is similar to ours), it is not obvious (and is an interesting open question) whether the procedure can generalize to the other problems we have listed. Edwards [Edw86] shows how to 3color a 3colorable everywheredense graph in polynomial time. Our sampling approach gives an alternative algorithm. A randomsampling based approach related to ours also appears in [KP92]. In the last section of the paper (Section 8) we describe some results related to our work that have been discovered since the conference presentation of the current paper. 1.5 Paper Organization In Section 2 we give details of the main ideas of our approach, exhaustive sampling and transforming polynomial constraints into linearconstraints, already sketched in Sections 1.2 and 1.3. We continue to use MAXCUT as a motivating example. In Section 3 we generalize these techniques to derive our (additive error) approximation algorithm for any smooth polynomial integer program (PIP). In Section 4, we use these PIPs to approximate most of the problems listed in Section 1.1. Solving BISECTION and SEPARATOR requires some additional exhaustive sampling ideas that are explained in Section 5. In Section 6, we describe some problems that can be solved purely by exhaustive sampling, with no recourse to PIPs. Finally, in Section 7, we conﬁrm that all of the problems we are approximating are still N Pcomplete when restricted to dense instances, demonstrating that an exact solution is unlikely. 2 Our Techniques: An overview In this section we introduce our two major techniques, exhaustive sampling and reducing degree d constraints to linear constraints (in an approximate sense) to give a PTAS for dense MAXCUT. 6 First we express MAXCUT as a quadratic integer program as follows. Let the 0/1 vector x be the characteristic vector of a cut, i.e., xi = 1 iﬀ i is on the right side. Let N (i) be the set of neighbors of vertex i, and let ri (x) = j N (i) (1 − xj ) be the linear function denoting the number of number of neighbors of i that are on the left side of cut x. Then MAXCUT = max i xi ri (x) s.t. xi i The above formulation looks a lot like an integer linear program, for which numerous approximation techniques are known. Unfortunately, the coeﬃcients ri (x) in the objective function are not constantsthe program is actually a quadratic program. However, exhaustive sampling lets us estimate the value these coeﬃcients have in the optimum solution. We arrive at our approximation in three steps: 1. Using exhaustive sampling, we estimate the values of ri (a) at the optimum solution a = (a1 , . . . , an ). See Section 2.1. 2. We replace each function ri by the corresponding estimate of ri (a). This turns the quadratic program into a linear (integer) program. We show that optimum of this linear integer program is nearoptimum for the quadratic program. See Section 2.2. 3. We solve the fractional relaxation of the linear integer program, and use randomized rounding to convert the solution into an integer one. We show that this does not dramatically change the solution value. See Section 2.3. A comment on notation: Throughout the paper, we will use a b where a and b are real numbers, as a shorthand for the interval [a − b, a + b]. 2.1 Estimating Coeﬃcients We begin by using exhaustive sampling to estimate the values ri (a) at the optimum solution a. Let a be the optimum cut and let ρi = ri (a). Then a is the solutionto the following integer linear program: MAXCUT = max i xi ρi s.t. xi i i ri (x) = ρi Of course, the usefulness of this observation is unclear, since we dont know the values ρi . We show, however, that it is possible to compute an additive error estimate of the ρi in polynomial time, in other words, a set of numbers ei such that ρi − ǫn ≤ ei ≤ ρi + ǫn i. (4) This can be done using our exhaustive sampling approach. We take a random sample of O(log n) vertices. By exhaustively trying all possible (i.e., 2O(log n) = nO(1) ) placements of the vertices in the sample, we will eventually guess a placement wherein each vertex is placed as it would be in the optimum cut. So we can assume that we have guessed the values aj in the optimum cut for all the sampled vertices j. Now consider any unsampled vertex i. If it has N (i) = Ω(n) neighbors, then with high probability, Θ(log n) of its neighbors are part 7 of the random sample (high probability means probability 1 − n−Ω(1) ). A moments thought shows that these neighbors form a uniform random sample from N (i). Hence by examining the fraction of sampled neighbors on the left hand side of the cut (namely, neighbors for which aj = 0) we can obtain an estimate of ri (a)/ N (i) that is correct to within a small additive factor. This follows from the following sampling lemma. Lemma 2.1(Sampling Lemma). Let (ai ) be a sequence of n numbers, each with absolute value at most M . Let f > 0 be any number. If we choose a multiset of s = g log n of the ai at random (with replacement), then their sum q satisﬁes qn s with probability at least 1 − n−f . Proof. Let s = g log n. For j = 1, . . . , s let Xj be the random variable denoting the number picked in the j th draw. Since the numbers are drawn with replacement, the values Xj are identically distributed, and n 1 aj . E[Xj ] = n j=1 Since Xj  ≤ M by hypothesis, the lemma now follows from the standard Hﬀding bound o [H64]. For MAXCUT, our goal is to estimate the values ρi of the form j N (i) (1 − aj ). First, if any N (i) ≤ ǫn/10, we use the estimate 0 for ρi . To estimate ρi for the remaining i, we randomly choose (with replacement) g log n indices with g = O(1/ǫ3 ), and guess their values by exhaustively trying all possibilities. Since each aj = 0 or 1, we can take M = 1 in the Sampling Lemma. The Sampling Lemma shows that for each i, the probability is at least 1 − 1/n2 that the following happen (i) Ω(log n/ǫ2 ) of the sampled vertices lie in N (i) (note that the conditional distribution of these vertices is uniform) and (ii) the estimate for ρi produced using this sample is accurate to within ǫn. ai nM f g i 2.2 Linearizing the Quadratic Integer Program Now we use thecoeﬃcient estimates to deﬁne an integer linear program whose solutions are nearoptima for MAXCUT. Given the estimates ei just derived for the values ρi , we write the following linear integer program. Note that it is feasible, since a satisﬁes it (assuming our sampling step in the previous section worked). NEWOPT = max i xi ei s.t. xi i ei − ǫn ≤ ri (x) ≤ ei − ǫn i (5) (Recall that each ri (x) is a linear function of x, so the given constraints are linear constraints.) We claim that the optimum solution z to this integer linear program is nearoptimum for MAXCUT. This can be seen as follows: 8 zi ri (z) ≥ ≥ ≥ ≥ ≥ zi (ei − ǫn) zi ei − ǫn2 ai ei − ǫn2 ai (ρi − ǫn) − ǫn2 ai ρi − 2ǫn2 By the constraints (5) Since z is integer optimum from (4) = MAXCUT − 2ǫn2 In other words, the optimum of the integer program is a nearoptimum solution to MAXCUT. 2.3 Approximating the Linear Integer Program Of course, we cannot exactly solve the integer linear program just derived. But we can compute an approximate solution to it as follows. We relax the integrality constraints, allowing 0 ≤ xi ≤ 1. We use linear programming to obtain the fractional optimum, say y [0, 1]n , and then use randomized rounding to convert the fractional solution to an integral one of roughly the same value. The key lemma is the following: Lemma 2.2(Randomized Rounding). If c and f are positive integers and 0 < ǫ < 1, then the following is true for any integers n ≥ 0. Let y = (yi ) be a vector of n variables, 0 ≤ yi ≤ 1, that satisﬁes a certain linear constraint aT y = b, where each ai  ≤ c. Construct a vector z = (zi ) randomly by setting zi = 1 with probability yi and 0 with probability 1 − yi . Then with probability at least 1 − n−f , we have aT z b c f n ln n We can apply this lemma to our problem as follows. Give our fractional solution y, let us apply randomized rounding as in the lemma to yield an integral solution z. We claim that with high probability, √ (6) ri (z) ri (y) O( n ln n) zi ri (y) yi ri (y) O(n3/2 ln n) (7) Speciﬁcally, to derive Equations (6) and (7) from Lemma 2.2, note that each ri (x) is a linear function with 01 coeﬃcients and that each ri (y) is at most n. We use these equations as follows. The analysis of the previous section showed that the integral optimum of our derived linear program was near the maximum cut value, so the fractional optimum y can only be better. That is, yi ri (y) ≥ MAXCUT − 2ǫn2 . We now use our randomized rounding lemma. We have that √ zi ri (z) ≥ zi (ri (y) − O( n ln n)) ≥ ≥ zi ri (y) − O(n3/2 ln n) yi ri (y) − O(n3/2 ln n) From (7) 2 From (6) ≥ MAXCUT − (2ǫ + o(1))n This ﬁnishes the overview of our algorithm for MAXCUT. 9 3 Approximating Smooth Integer Programs We now generalize the results of the previous section to handle arbitrary polynomial integer programs (PIPs). We describe an algorithm that computes approximate solutions to smooth PIPs of low degree, thus proving Theorem 1.10. We use the fact that smooth PIPs can be recursively decomposed into smooth lowerdegree PIPs. This lets us apply ideas similar to those described in Section 2 for MAXCUT. In a PIP the objective function and constraints are low degree polynomials (degree 2 in the case of MAXCUT). We use exhaustive sampling to convert such polynomial integer programs into linear integer programs. Then we use the RaghavanThompson technique to approximately solve the linear integer program. We will see shortly that we can assume without loss of generality that we are dealing with the feasibility version of a PIPthat is, we are given a feasible PIP and out goal is to ﬁnd an approximately feasible integer solution. Our general algorithm has the same three elements as the one for MAXCUT: 1. We show in Section 3.2 that we can relax the integrality conditions, since we can use randomized rounding to convert every feasible fractional solution of a PIP into a feasible integral solution. 2. In Section 3.3, we generalize the sampling theorem, which applies only to sums, to let us estimate the values ofpolynomials. 3. We show in Section 3.4 that we can use our estimates to convert degree d constraints into linear constraints without aﬀecting feasibility. We begin in Section 3.1 with some basic observations. 3.1 Basic Observations We begin with a few basic observations that we will use at various times in the proof. 3.1.1 A Polynomial Decomposition Our PIP algorithms are basically recursive generalizations of the approach for MAXCUT. They rely on the following key observation that lets us decompose any polynomial into simpler polynomials: Lemma 3.1. A csmooth polynomial p of degree d can be written as p(x) = t + xi pi (x) where t is a constant and each pi is a csmooth polynomial of degree d − 1. Proof. From each monomial term in the expansion of p, pull out one variable xi . Group all monomials from which xi was extracted into pi . Every degree d′ term in pi corresponds to ′ ′ a degree d′ + 1 term in p, and thus has coeﬃcient at most cnd−(d +1) = cn(d−1)−d . Thus, since pi has degree (at most) d − 1, it is a csmooth degree d − 1 polynomial. Remark. The above analysis also shows that we can express p uniquely as a sum p(x) = t + xi pi (xi , . . . , xn ), that is, where each pi depends only on variables with index i or greater. 10 The decomposition of a degree d polynomial into degree d − 1 polynomials gives us a natural recursionthrough which we can generalize our quadratic programming techniques. By computing an estimate ρi of the value of pi (x) at the optimum solution, we replace the degreed constraint p with a single constraint on xi ρi together with a family of constraints on the values pi (x). We then recursively expand these degree d − 1 constraints, continuing until all of our constraints are linear. To estimate the values pi (x), we again rely on the expansion above: we expand pi in xj pij (x), recursively estimate the pij terms of degree d − 2 polynomials, writing pi (x) = values, and then use exhaustive sampling to estimate p based on the values of the pij . After constructing the required linear integer program, we solve its fractional relaxation and use randomized rounding as before to transform the solution into an integral solution. To prove that randomized rounding works, we again use the decompositionwe show that xi pi (x) is also preserved. each pi (x) is roughly preserved by rounding, and deduce that 3.1.2 Reducing Optimization to Feasibility We can reduce PIP optimization to the corresponding feasibility problem (Is there a feasible solution such that the objective exceeds a given value?) using binary search in the usual way. This uses the fact that the optimum value of a PIP is not too large, as shown in the following lemma (which will also be useful later).Lemma 3.2. If n > d, then the absolute value of a csmooth polynomial at any point in [0, 1]n is at most 2cend (where ln e = 1). Proof. For 0 ≤ i ≤ d the polynomial has at most n+i terms of degree i, and each has a i coeﬃcient in [−cnd−i , cnd−i ]. Thus an upper bound on the absolute value at any point in [0, 1]n is d i=0 cnd−i n+i i d ≤ i=0 cnd−i d n+d i ≤ cnd ( ≤ cn e which is at most cend (1 + 2d/n) < 2cend for n > 5d. i=0 d 1+d/n n+d i 1 ) n i! 3.2 Rounding Fractional PIPs We begin with the ﬁnal step of our algorithm, rounding a fractional solution to an integral one. We present this section ﬁrst since it is more straightforward than the following ones but conveys the same ideas. As we saw in Section 2.3, Raghavan and Thompson [RT87] show that given a fractional solution to a linear program, we can round it into an integer solution that is almost as good. We rephrased their result in Lemma 2.2. We now modify the RaghavanThompson technique to show in Lemma 3.3 that a similar result is true for low degree polynomials. In other words, we show that the value of a csmooth polynomial at a point in [0, 1]n is not too diﬀerent from its value at a nearby integral point obtained by randomized rounding. Lemma 3.3 (Randomized Rounding for degree d polynomials). Let p be a csmooth degreed polynomial. Givenfractional values (yi ) such that p(y1 , . . . , yn ) = b, suppose randomized rounding is performed on the yi as in Lemma 2.2 to yield a 0, 1 vector (zi ). Then with probability at least 1 − nd−f , we have 1√ p(z1 , . . . , zn ) b gdnd− 2 ln n , 11 √ where g = 2ce f . Proof. We use induction on the degree. The case d = 1 follows from Lemma 2.2. Now assume we have proved the Lemma for all integers less than d, and p is a degree d polynomial. As argued in Section 3.1, we can express p as n p(x1 , . . . , xn ) = i=1 xi pi (x1 , . . . , xn ) + t, (8) where t is a constant and pi is a csmooth polynomial of degree at most d − 1. Let ρi denote the value pi (y1 , . . . , yn ). Then b = p(y1 , . . . , yn ) n = t+ i=1 ρi yi . Let (z1 , . . . , zn ) n be obtained by randomized rounding on (y1 , . . . , yn ). Our proof consists of noticing that with high probability, (zi ) satisﬁes both b ≈ i ρi zi (by Lemma 2.2) and i ≤ n : ρi ≈ pi (z1 , . . . , zn ) (by induction for degree d − 1). Then we realize that any such (zi ) also satisﬁes b ≈ p(z1 , . . . , zn ). Let us formalize this idea. Note that ρi  ≤ 2cend−1 by Lemma 3.2. So we can apply Lemma 2.2 (replacing c by 2cend−1 ). We ﬁnd that with probability at least 1−n−f (recalling that the notation a b is shorthand for the interval [a − b, a + b]), n i=1 √ ρi zi b gnd−1 n ln n. (9) Furthermore, the inductive hypothesis implies that for each i ≤ n, the probability is at least 1 − nd−f −1 that 1√ (10) pi (zi , . . . , zn ) ρi g(d − 1)nd−1− 2 ln n Hence we conclude that with probability at least 1 − nd−f − n−f ≈ 1 − nd−f , the event mentioned in Condition (10) happens for each i ≤ n, and so does the event mentioned in Condition (9). Of course, when all these events happen, we have: n p(z1 , . . . , zn ) = t + i=1 zi pi (z1 , . . . , zn ) by (10) t+ √ zi (ρi g(d − 1)nd−1−1/2 ln n) √ t+ zi ρi g(d − 1)nd−1/2 ln n √ √ = b gnd−1 n ln n g(d − 1)nd−1/2 ln n 1√ = [b gdnd− 2 ln n] 1 by (9) Hence we have shown that p(z1 , . . . , zn ) [b gdnd− 2 1 − nd−f . √ ln n] with probability at least 3.3 Estimating the Value of a Polynomial Having shown how to round a fractional solution to an integral one, we now show how to ﬁnd an approximately optimal fractional solution by solving a linear program. As discussed above, our procedure for replacing the constraint on p(x) by linear constraints requires 12 estimating the values at the optimum a of the coeﬃcients pi (a) in the expansion p(a) = ai pi (a). In this section, we show how this estimation can be accomplished by exhaustive sampling. We describe a procedure Eval in Figure 3.3 that can approximate the value of acsmooth degree d polynomial p(x1 , . . . , xn ) on any unknown 0/1 vector (a1 , . . . , an ), given only partial information about (a1 , . . . , an ). The algorithm is given the values ai for O(log n) randomlychosen indices i, and outputs an estimate that, with high probability, lies in p(a1 , . . . , an ) ǫnd . To simplify our exposition later we describe the procedure more generally as using a (multi)set of indices S . Algorithm Eval(p, S, ) polynomial p of degree at most d, set of variables indices S, ai for i S. Output: estimate for p(a1 , . . . , an ). if deg(p) = 0 (i.e., p is a constant) then return p else write p(x1 , . . . , xn ) = t + xi pi (x1 , . . . , xn ) where t is a constant and each pi has degree at most d − 1 for each i S ei ←Eval(pi , S, ) return n ai ei t+ S i S Input: Figure 1: The approximate evaluation algorithm Note that if S = then the procedure returns p(a1 , . . . , an ). We will show that in order to get an additive approximation of the type we are interested in, it suﬃces to choose S randomly and of size O(log n). We use the Sampling Lemma (2.1) as the base case in our inductive proof of the correctness of Eval. Lemma 3.4. Let p be a csmooth polynomial of degree d in n variables xi , and let a1 , . . . , an . Let S be a set of O(g log n) indices chosenrandomly (with replacement). Then with probability at least 1 − nd−f , set S is such that Eval(p, S, ) returns a value in p(a1 , . . . , an ) ǫnd , where ǫ = 4ce f . g Proof. The proof is by induction on d. The case d = 0 is clear. For the inductive step let ρi = pi (ai , . . . , an ), so we have n p(a1 , . . . , an ) = t + i=1 ai ρi (11) The intuition for why Evals output should approximate p(a1 , . . . , an ) is as follows. Each pi has degree at most d−1, so the inductive hypothesis implies that ei ≈ ρi . Thus the output 13 of eval is t+ n S ai ei ≈ t + ≈t+ n S i i S i S ai ρi (by the inductive hypothesis) (by the Sampling Lemma) ai ρi It remains to ﬁll in the details, and to deal with the complication that the errors in our recursive estimates of the ρi accumulate into the error for our estimate of p(a1 , . . . , an ). Our sample has size g log n. By Lemma 3.2, each ρi  ≤ 2cend−1 . Hence the Sampling Lemma implies that with probability 1 − n−f the set S is such that n S ai ρi ai ρi 2ce f g nd (12) i S i Of course, we do not have the values ρi . However, we do have the values ei =Eval(pi , S, ). To see the impact of using them instead, let ǫd denote the smallest number such that for every csmooth degree d polynomial p and point a n Pr[Evalcomputes an estimate within p(a) ǫd nd ] ≥ 1 − nd−f We get an recurrence for ǫd as follows. By deﬁnition, Eval estimates any particular ρi to within ǫd−1 nd−1 with probability 1 − n(d−1)−f . Thus all n values ρi are estimated to within this bound with probability 1 − n n(d−1)−f = 1 − nd−f . Combining with (12), we conclude that with probability at least 1 − nd−f − n−f ≈ 1 − nd−f , set S is such that the returned value n n ai ei t + ai ρi ǫd−1 nd−1 t+ S S i S i S t+ t+ t+ n S i S ai ρi ǫd−1 nd−1 f d n g n S ǫd−1 d n S nd nd . by (12) i ai ρi 2ce 2ce i ai ρi ǫd−1 f + g S f ǫd−1 + g S = p(a1 , . . . , an ) It follows that ǫd ≤ 2ce ≤ 2ce ≤ 4ce for S > 1. f ǫd−1 + g S 2ce f (1 + S−1 + + S−d ) g f g 14 Corollary 3.5. With probability 1−nd−f over the choice of S, the Eval procedure accurately estimates the values of all the polynomials arising from the decomposition of polynomial p ′ (that is, estimates every degreed′ polynomial to within ǫd′ nd ). Proof. This is implicit in the previous proof. Note that the decomposition of p is determined solely by p, independent of the value of the optimum solution a that we are estimating. 3.4 Transforming Degree d Constraints to Linear Constraints Using the estimates produced by Procedure Eval of Section 3.3 we cantransform any polynomial constraint into a family of linear constraints, so that any feasible solution to the linear constraints will approximately satisfy the polynomial constraint as well. We use algorithm Linearize in Figure 3.4. Just like Eval, the inputs to this procedure contain partial information about some feasible solution vector (a1 , . . . , an ) n to the input constraint. Algorithm Linearize(L ≤ p(x1 , . . . , xn ) ≤ U , S, , ǫ) constraint involving polynomial p of degree d, lower bound L and upper bound U multiset of variable indices S ai for each i S. Error parameter ǫ > 0. Output: A set of linear constraints if p is linear then output the input constraint L ≤ p(x) ≤ U else write p(x1 , . . . , xn ) = t + xi pi (x1 , . . . , xn ) where t is a constant and each pi has degree at most d − 1 for i = 1 to n ei ← Eval(pi , S, ) li ← ei − ǫnd−1 ui ← ei + ǫnd−1 Linearize(li ≤ pi (x1 , . . . , xn ) ≤ ui , S, , ǫ) output the constraint L − ǫnd ≤ t + xi ei ≤ U + ǫnd Figure 2: Linearizing a Polynomial Constraint A simple induction shows that the Procedure in Figure 3.4, when given a degree d constraint, outputs a set of at most 1 + n + + nd−1 = O(nd−1 ) linear constraints. The next two lemmas prove the correctness of this (probabilistic) reduction. The ﬁrst shows that with highprobability, the replacement equations are jointly feasible. The second shows any feasible solution will be almost feasible for the original constraint. Lemma 3.6. Let f, g, c > 0 be any constants. Let Linearize be given an error parameter ǫ = 4ce f /g and a constraint involving a csmooth polynomial of degree d. Let (a1 , . . . , an ) n be a feasible solution to the constraint. If S is a random sample of g log n variables (picked with replacement), then with probability at least 1 − dnd−f Procedure Linearize outputs a set of linear constraints that are satisﬁed by (a1 , . . . , an ). Proof. Calling linearize with polynomial p results in numerous recursive call, each of which (besides making other recursive calls) outputs a constraint on some degree d′ polynomial 15 Input: p′ . The boundaries li and ui for this constraint are determined by a call to Eval involving polynomial p′ . Vector a satisﬁes this constraint so long as li and ui satisfy li ≤ p(a) ≤ u, ′ and this happens so long as ei p′ (a) ǫnd . So Linearize does the right thing so long as every polynomial p′ arising in the recursions is estimated accurately. But these polynomials are just the polynomials arising in the recursive decomposition of the original polynomial p, and are all encountered during a call to Eval(p). Corollary 3.5 says that all of these polynomials are estimated towithin the desired bounds with probability 1 − nd−f . Now we show that in the linear system output by Linearize, every feasible solution is an approximate solution to the input constraint (note that this statement involves no probabilities). The next lemma uses [x, y] a, where x < y and a ≥ 0, as a shorthand for the interval [x − a, y + a]. Lemma 3.7. Every feasible solution (yi ) [0, 1]n to the set of linear constraints output by Linearize satisﬁes the following (irrespective of what the set S is) p(y) [L, U ] 2dǫnd Proof. By induction on d. The case d = 1 is clear, so consider the inductive step. Since by assumption y is feasible for the entire set of output constraints, it is feasible for the constraints output by each recursive call involving a polynomial pi . It follows by the inductive hypothesis that for each i, pi (yi , . . . , yn ) [li , ui ] 2(d − 1)ǫnd−1 . Substituting the values of li and ui we get pi (y) ei (2d − 1)ǫnd−1 Therefore, p(y) = t+ t+ yi pi (yi , . . . , yn ) yi (ei (2d − 1)ǫnd−1 ) yi ei (2d − 1)ǫnd (13) t+ [L, U ] ǫnd (2d − 1)ǫnd [L, U ] 2dǫnd where Equation (13) follows from the fact that y is feasible for the constraint that was output before recursion, namely t+ Thus the inductive step is complete. xi ei [L, U ] ǫnd . 3.5 Proof of the main theorem The proof of Theorem 1.10 nowfollows easily. We have a feasible degree d PIP with K constraints, where K = poly(n). Suppose (a1 , . . . , an ) is some (unknown) feasible 0/1 solution and ǫ > 0 is some tolerance parameter. We describe a probabilistic procedure that produces a 0/1 solution z that is approximately feasible. That is, if L ≤ p(x) ≤ U was a degree d′ constraint in the input, then with high probability z satisﬁes it within an additive 16 error ǫnd , that is, L − ǫnd ≤ p(z) ≤ U + ǫnd . (We indicate below how to derandomize the procedure.) Let f > 0 be such that nf ≈ 2dKnd . We let ǫ′ = ǫ/2d, and g = 16c2 e2 f d2 /ǫ2 = O(/ǫ2 ). We pick a random multiset S of O(g log n) variables and guess (by exhaustive enumeration in 2g log n time) the values of ai for each i S. Then we use Procedure Linearize with ′ error parameter ǫ′ to replace each degree d′ constraint with O(nd −1 ) linear constraints, thus obtaining a linear system with O(Knd−1 ) constraints. Since (a1 , . . . , an ) is a feasible solution to the PIP, Lemma 3.6 implies that the probability that the new system is feasible is at least 1−dnd−f K > 1/2 . We solve the linear system using a polynomialtime algorithm for linear programming in O((Knd−1 )3 ) time [K84]. Lemma 3.7 implies that the (fractional) solution thus obtained is also a feasible solution for the original PIP, except for an additive error 2dǫ′ nd .Then we randomly round this fractional solution to a 0/1 solution; Lemma 3.3 implies that this increases the additive error by at most O(nd−1/2 ln n) = o(nd ). Hence we have described a probabilistic procedure that, with probability at least 1/2, produces a 0/1 solution that is feasible for the PIP except for an additive error of 2ǫ′ dnd = ǫnd . The procedure explores 2g log n exhaustive sampling possibilities and for each spends at most O((Knd )3 ) time in generating the linear constraints and solving them for each guess. The randomized rounding can be done in nearly linear time. Noting that 2g log n = ng = (nf )4c 2 2 2 ′ ′ ′ e d /ǫ2 ≈ (2Knd )4c 2 2 2 e d /ǫ2 , we conclude that this term dominates the running time. 3.6 Derandomization Derandomizing the algorithm in Theorem 1.10 involves derandomizing its components, Procedures Eval and Linearize. Those depend upon two randomized procedures: Randomized Rounding (used in Lemma 3.3) and the Sampling Lemma. Raghavan [Rag88] derandomized the former through the method of conditional probabilities. Derandomizations of the Sampling Lemma appear in [BR94] and [BGG93]. For example, instead of picking s = O(log n/ǫ2 ) variables independently, it suﬃces to pick the variables whose indices are encountered on a random walk of length O(log n/ǫ2 ) on a constant degree expander [Gil93].For any ﬁxed sampling experiment, the probably that such a walk works is 1/nO(1) . Hence our algorithm can deterministically go through all such walks (the number of such walks 2 is nO(1/ǫ ) since the expander has O(1) degree). One of the walks is guaranteed to work correctly for all of the poly(n) sampling experiments that our algorithms is interested in. 4 Applications In this section we use our theorem on approximating constantdegree smooth integer programs to construct PTASs for (dense instances of) many problems. Most applications require approximating quadratic programs. Approximating dense MAXkSAT requires approximating degreek integer programs. In later sections we will obtain PTASs for graph bisection and minimum kway cut. These will require some additional ideas, speciﬁcally, a diﬀerent application of exhaustive sampling. 4.1 MAXCUT, MAXDICUT, MAXHYPERCUT Note that a δdense graph has at least δn2 edges. Thus the capacity k of the maximum cut exceeds δn2 /2, since this is the expected size of a cut obtained by randomly assigning each vertex to one side of the graph or the other with equal probability. We already saw in 17 Example 1.8 how to represent MAXCUT using csmooth quadratic integer programs with c = O(1). Using the approximation scheme for quadratic programs in Theorem 1.10, we 2 2 can in time nO(1/ǫ δ )ﬁnd a cut of value at least c − ǫδn2 /2 ≥ (1 − ǫ)k, in other words a (1 − ǫ) approximation to the maximum cut. MAXDICUT has a similar PTAS. Again, an expectation argument shows that the maximum cut in a δdense graph exceeds δn2 /4. The representation by a quadratic program is also similar; in the quadratic program for MAXCUT in Example 1.8 just replace (xi (1 − xj ) + xj (1 − xi )) in the objective function by (1 − xi )xj . The PTAS for dense MAXHYPERCUT(d) is similarly obtained by modeling the problems as a smooth degreed PIP. For a given edge (set of vertices) S, we use the term 1 − i S xi − i S (1 − xi ). This term is 1 if S is cut and zero otherwise. 4.2 DENSEkSUBGRAPH Let k ≥ αn. If a graph is δdense, then a graph induced by a random subset of k vertices contains α2 δn2 /2 edges on average. Hence the densest subgraph contains at least α2 δn2 /2 edges. We can express the DENSESTkSUBGRAPH as the optimum of the following quadratic program. maximize subject to xi xj E xi n i=1 xi = k Clearly this PIP is 1smooth. From Theorem 1.10 we know how to ﬁnd an approximately √ √ n optimal 0, 1 vector x satisfying i=1 xi [k g n ln n]. Now we move at most g n ln n vertices in or out to get √ subset of size k; this aﬀects the number of edges included in the a subgraph by at most gn n ln n = o(n2 ). The reader may wonder ifour algorithm for DENSESTSUBGRAPH has any application to the CLIQUE problem. We do not see any connection. In fact, approximating CLIQUE in dense graphs is N Phard (this follows from the fact that approximating INDEPENDENT SET in degree5 graphs is N Phard [ALM+ 92]). 4.3 MAXkSAT A standard arithmetization method can be used to represent MAXkSAT as a degreek smooth IP. Let y1 , . . . , yn be the variables and m be the number of clauses. Introduce 01 valued variables x1 , . . . , xn . For each i, 1 ≤ i ≤ n, replace each unnegated occurrence of variable yi by 1 − xi , each negated occurrence by xi , eachlogical by multiplication (over integers), and for each clause subtract the resulting term from 1. This changes each clause into a degreek polynomial. To give an example, the clause y1 y2 y3 is replaced by the term 1 − (1 − x1 )x2 (1 − x3 ). Now associate, in the obvious way, 0, 1 assignments to the variables xi with truth assignments to the boolean variables yi . Clearly, an assignment of values to the xi makes the term 1 if the corresponding assignment to the yi makes the clause true, and 0 otherwise. Let tj be the term obtained in this way from the jth clause. The following degreek program represents the MAXkSAT instance, and is smooth. maximize subject to j≤m tj (x1 , . . . , xn ) i xi 18 Now suppose thenumber of clauses is m ≥ δnk . Let OPT be the maximum number of clauses that any assignment can satisfy. Since the number of clauses of size k is m−O(nk−1 ), and a random assignment satisﬁes each of them with probability 1 − 2−k , we have OPT ≥ (1 − 2−k )(m − O(nk−1 )). By approximating our PIP we can in time O(n2 OPT − 2ǫk nk ≥ (1 − ǫ)OPT clauses. 4k /ǫ2 ) ﬁnd an assignment that satisﬁes 4.4 As pointed out in [PY91], problems such as MAXCUT, MAXkSAT and MAXHYPERCUT(d) lie in a class called MAXSN P, and actually in a subclass called MAXSN P 0 in [Pap94]. MAXSN P 0 was deﬁned using model theory, and it is unclear how to deﬁne denseness for MAXSN P 0 problems. In fact, problems such as vertex cover are in MAXSN P only if the degree of the graph is bounded. In this section we give a plausible deﬁnition of denseness and show that under this deﬁnition, all dense MAXSN P 0 problems have a PTAS. Let MAXkFUNCTIONSAT be the problem in which the input consists of m boolean functions f1 , f2 , . . . , fm in n variables, and each fi depends only upon k variables. The objective is to assign values to the variables so as to satisfy as many fi as possible. As is wellknown (see [Pap94], Theorem 13.8), a MAXSN P 0 problem can be viewed as a MAXkFUNCTIONSAT problem for some ﬁxed integer k. (An alternative name for MAXkFUNCTIONSAT isconstraint satisfaction problems [KSW97].) We call an instance of a MAXSN P 0 problem dense if the instance of MAXkFUNCTIONSAT produced using it has Ω(nk ) functions. It is easily checked that our earlier deﬁnitions of denseness were subcases of this deﬁnition. Also, not all MAXSN P problems have a dense version under this deﬁnition; for example vertex cover is excluded. A slight modiﬁcation of the kSAT technique of Section 4.3 shows that MAXkFUNCTIONSAT can be represented by a smooth degreek integer program, so it follows that dense MAXkFUNCTIONSAT has a PTAS. Dense MAXSN P 5 BISECTION and SEPARATOR In this section we describe a PTAS for BISECTION. Small modiﬁcations described at the end give a PTAS for SEPARATOR. Consider a graph with minimum degree δn for some δ > 0 and let k denote the capacity of the minimum bisection. The PTAS consists of two diﬀerent algorithms, one of which is a PTAS when k ≥ αn2 , and the other when k < αn2 , where α is a certain small constant. For k ≥ αn2 , we use our PIP approximation algorithm to achieve an additive error at most ǫαn2 , so that the capacity of the ﬁnal bisection is at most (1 + ǫ)k. When k ≤ αn2 , such additive approximations do not suﬃce, and we give a diﬀerent algorithm. The algorithm uses exhaustive sampling to identify vertices that have many neighbors on one side of the bisection, andplaces them on that side. We show that this leaves only a small number of unplaced neighbors, whose placement can be done greedily without signiﬁcantly disturbing the value of our solution. 5.1 Large Bisections The algorithm for k ≥ αn2 is essentially our algorithm for approximating smooth quadratic integer programs. We formulate graph bisection using the same quadratic program as for MAXCUT (see Example 1.8), except we change maximize to minimize, and add the constraint xi = n/2. Applying our main theorem gives us an assignment to the xi that makes the objective function less than k + ǫn2 ≤ k(1 + ǫ/α). 19 There is one small problem: this 0, 1 assignment might not induce a bisection, since it xi = n/2. However, randomized rounding only approximately satisﬁes the constraint √ does guarantee there will√ n/2 ( n log n) vertices on each side of the solution. Hence be we need to move only O( n log n) vertices from one side to another in order to balance the cut. This aﬀects the bisection value by at most O(n1.5 log n) = o(n2 ). 5.2 Small Bisections The case k ≤ αn2 is more diﬃcult. We need the following lemma. Lemma 5.1. In a minimum bisection, there is one side whose every degreed vertex has at most d/2 + 1 of its neighbors on the other side. Proof. If not, then we can reduce the bisection value by picking from each side a vertex thathas more than the allowed neighbors on the other side, and switching them. Let Lopt and Ropt denote the sets of vertices on the two sides of a particular minimum bisection. Without loss of generality, we will assume that Lopt is the side referred to in Lemma 5.1. We now give a bisection algorithm in Figure 5.2. For simplicity, we describe it as a randomized algorithm, although we can easily derandomize it using the techniques mentioned earlier. Recall that δ is the denseness of the problem. 1. Pick a set S of O((log n)/δ) vertices at random. 2. For each possible partition of S into two sets (SL , SR ), construct a partition (L, R) as follows. (a) Let T be the set of vertices that have more than 5/8 of their sampled neighbors in SR . (b) Put T in R. (c) For each vertex v T , deﬁne bias(v) as #(neighbors of v not in T ) − #(neighbors of v in T ). (d) Put the n/2 − T  vertices with the smallest bias into R. 3. Of all bisections found in the previous step, output the one with the smallest value. Figure 3: The Bisection Algorithm Now we prove the correctness of the algorithm. Since it exhaustively tries all possible partitions of the vertices in the sample S, it also tries the correct partition, which labels each of the vertices of S according to a minimum bisection (Lopt , Ropt ) of the entire graph. From now on we call this partition (SL , SR ) of Sspecial. We will show that with high probability (over the choice of S) the special partition leads the algorithm to a nearoptimum graph bisection. Let T be the set constructed by the ﬁrst step of the algorithm using the special partition. The next lemma describes some useful properties of T . Call a vertex radicalright if at least 3/4 of its neighbors are in Ropt . Note (from Lemma 5.1) that every radicalright vertex must be in Ropt . Lemma 5.2. With high probability (over the choice of S), T is a subset of Ropt and contains every radical right vertex. 20 Proof. Let v be any vertex. Since its degree exceeds δn, the Sampling Lemma implies that with high probability a random sample of size O((log n)/δ) contains Θ(log n) neighbors of v. Conditioning on the number of neighbors in the sample, these neighbors form an unbiased sample of that many neighbors of v. Suppose v Lopt , and so has fewer than 1/2 of its neighbors in Ropt . Then an application of the Sampling Lemma shows that in a random sample of Θ(log n) neighbors of v, the probability that more than 5/8 of them are in Ropt is n−Ω(1) . Hence the probability that v T is n−Ω(1) . Now suppose v Ropt has more than 3/4 of its neighbors in Ropt . An application of the Sampling Lemma shows that in a random sample of O(log n) neighbors of v, the probability that less than 5/8 of them are in Ropt isn−Ω(1) . Hence the probability that v T is 1 − n−Ω(1) . The next lemma says that with high probability, T has size close to n/2 and thus contains almost all of Ropt . Lemma 5.3. If T satisﬁes the two conditions in Lemma 5.2 then T  ≥ n 2 − 4k δn . Proof. Every vertex in Ropt −T must have 1/4 of its neighbors in Lopt . Let s = Ropt − T  = n/2 − T . Then the value of the minimum bisection is at least sδn/4, which by assumption is at most k. Hence s ≤ 4k/(δn). We can now show that with high probability the algorithm produces a bisection close to optimum. Theorem 5.4. Assuming k < αn2 , with high probability (over the choice of S) the bisection produced by the special partition has value at most k(1 + ǫ), where ǫ = 16α2 /δ 2 . Proof. We measure the cost of extending T to a particular set of half the vertices. For any set U T , let din (U ) be twice the number of edges with both endpoints in U , and let dout (T ) be the number of edges with exactly one endpoint in T . Further, let bias(U ) be the sum of the biases of vertices in U . We claim that the capacity of the bisection whose one side is T U is dout (T ) + bias(U ) − din (U ). (14) To see this, note that the expression starts by counting all edges leaving T . The bias term then subtracts the edges crossing from U to T while adding the edges crossing from U to the other side of thecut. The bias term also incorrectly adds (twice, once for each endpoint) the number of edges with both endpoints in U , which do not cross the cut; however, this quantity is subtracted by the din (U ) term, resulting in the correct quantity. With high probability, the set T produced in the ﬁrst phase satisﬁes the conditions in Lemma 5.2. Hence T Ropt , and s = n/2 − T  ≤ 4k/(δn). Let Uopt = Ropt − T be the optimum set of s vertices extending T to Ropt and let Uactual be the set of s vertices that the algorithm actually picks to extend R. Since Uopt minimizes Equation (14), we know k = dout (T ) + bias(Uopt ) − din (Uopt ). On the other hand, Uactual (since it includes the s vertices with the smallest bias) minimizes bias(U ), and thus also the expression dout (T ) + bias(U ). Thus the capacity of the bisection whose one side is T Uactual is at most k + din (Uopt ) − din (Uactual ), which is at most k + s2 ≤ k + (4k/(δn))2 . Since k < αn2 the capacity is at most k(1 + 16α2 /δ 2 ). Corollary 5.5. If a dense graph has bisection value O(n), the optimum bisection can be found in polynomial time. Proof. From Lemma 5.3, there are O(1) vertices in Ropt − T . These can be found by exhaustive search. 21 Corollary 5.6. There is a PTAS for the optimum separator of a dense graph. Proof. Guess the number k of vertices on the left side of the separator (bytrying all n/3 possibilities) and replace n/2 by k in the previous discussion of bisection. If the minimum degree is not constrained, but the average degree is Ω(n), our PIP approach still works for large bisection values, but our other algorithm for small bisection values fails. In fact, as shown in Section 7, approximating the minimum bisection for ǫdense graphs is no easier than approximating it on general graphs. 6 Algorithms without PIPs Occasionally, exhaustive sampling is suﬃcient to solve or approximately solve a dense problem without recourse to PIPs. This was shown for MAXCUT by Fernandez de la Vega [FdlV94]. We have also seen this for the case of (small) bisections. Here we describe two other problems, multiway cuts and 3coloring. (The latter was already solved by Edwards [Edw86].) 6.1 MINkCUT First we consider the kterminal cut problem. Let δn denote the minimum degree. Let OP T be the capacity of the optimum cut. Note that OP T ≤ kn, since kn is an upperbound on the capacity of a cut in which k − 1 of the terminals form singleton groups, while all other vertices form the remaining group. The algorithm relies on the following lemma. Lemma 6.1. When k = o(n), there is a kcut of capacity (1 + o(1))OP T that has a special form: at most 2/δ groups of size Ω(n), and all other groups of size 1 (containing only the terminals).Proof. Suppose S1 , S2 , . . . , Sk (sorted in decreasing order by size) are the k groups in the optimum cut. Let an ordinary vertex be one that in the optimum cut has at most 1/4 of its ≥ δn neighbors in groups diﬀerent from its own. Note that there are at most 4k/δ vertices that are not ordinary. Let t be the number of groups with at least δn/2 vertices; note that t ≤ 2/δ. Consider the modiﬁed cut in which all nonterminals from St+1 , . . . , Sk are moved to one of S1 , S2 , . . . , St . We show that the capacity of this cut is at most (1 + o(1)) times the original capacity; this will prove the lemma. Since each of St+1 , . . . , Sk has size less than δn/2, they can only contain vertices that are not ordinary. Thus they together contain at most 4k/δ vertices. Furthermore, the capacity of the cut is at least k Si  δn − ). (Si  2 2 i=t+1 Since Si  = O(k) = o(n), the second term is o() of the ﬁrst term. Now consider moving all nonterminals from St+1 , . . . , Sk to S1 , . . . , St ; this increases the capacity of the cut by at most k Si  , 2 i=t+1 which as already noted is o() of k i=t+1 (Si  δn/2). Now we describe the algorithm. Imagine ﬁxing a kcut of the type described in Lemma 6.1 Let an ordinary vertex be one that has at most 1/4 of its ≥ δn neighbors in groups diﬀerent 22 from its own. Let s be the number of nodes that are notordinary. Clearly, OP T (1 + o(1)) ≥ sδn/4, thus implying s ≤ 4k(1 + o(1))/δ = o(n). First we exhaustively try all k 2/δ ways of picking terminals that will go into nonsingleton groups. One of these ways will be correct. For each of the placements, we try placing the nonterminals using exhaustive sampling. We pick a random sample of O(log n) vertices and by exhaustively trying all partitions of it (just as in the other algorithms), we can identify for each vertex the group (if one exists) that contains more than 2/3 of its sampled neighbors, and assign it to that group. The Sampling Lemma shows that this fails to place or misplaces only vertices that are not ordinary, i.e., at most s vertices. Now place each of the remaining vertices in the group that contains a plurality of its neighbors. This gives almost the desired cut, except it may misplace s vertices. Furthermore, if a misplaced vertex contributed x to the correct cut (i.e., x of its neighbors were in another group) then it contributes at most x + s − 1 to our cut. Thus the cost of our cut is at most OP T (1 + o(1)) + s . 2 Since OP T (1 + o(1)) ≥ sδn/4, and s = o(n), the cut has capacity OP T (1 + o(1)). A similar PTAS can be designed for the problem without terminals, where the goal is simply to ﬁnd the best partition into k nonempty groups of vertices. 6.2 3COLORING Random samplingalso gives a scheme for 3coloring dense 3colorable graphs. Since this result replicates that of Edwards [Edw86], details are omitted. Let the colors be 0, 1, 2. Initially, make all vertices uncolored. As before, we pick a random sample of O((log n))/ǫ2 ) vertices and guess their colors. Let us focus on the correct guess. With high probability, at least one neighbor of every vertex is sampled and colored. Now observe that if a vertex has colored neighbors of two diﬀerent colors, its color is determined. So long as such a vertex exists, color it. When we ﬁnish, each remaining uncolored vertex vi has a neighbor with color ci and no neighbors of other colors. Now set up an instance of 2SAT as follows. Assign a variable xi to vertex vi that is true if vi has color ci + 1 (mod 3) in the optimal coloring, and false otherwise (i.e., vi has color ci − 1 (mod 3)). For each edge (vi , vj ), add constraints on the variables xi and xj that prevent vi and vj from having the same color. Solve the 2SAT instance in polynomial time, and extract an assignment of colors from the assignment to the variable xi . Note that the algorithm can be derandomized easily. 7 N Pcompleteness results Thus far, we have described PTASs for dense instances of many N Phard problems. Now we show that computing optimal solutions in all these cases remains N Phard, justifying thesearch for approximation schemes. For MAXSN P type problems, it is usually easy to reduce nondense instances to ǫdense instances. MAXCUT provides a good example. Suppose OPT is the optimum value of the MAXCUT problem on a graph G = (V, E). We add a (disjoint) complete graph on n vertices to G. The new graph has E + n edges, and is 1/2dense. Furthermore, the new 2 optimum of MAXCUT is OP T + n /2. Thus exact optimization on the new instance is no 2 easier than exact optimization on the old instance. A similar idea works for MAXkSAT, MAXDICUT, etc. 23 Everywheredense BISECTION is also N Phard. In fact, the standard reduction that shows the N Pcompleteness of BISECTION produces such instances. It starts from instances of MAX5050CUT that have constant degree this is a known N Phard restriction of MAX5050CUT and complements the graph to turn it into an instance of BISECTION. The resulting instance is everywhereǫdense. Now we indicate two problems for which denseness does not seem to help in designing PTASs: dense instances of BISECTION and everywheredense instances of MINVERTEXCOVER. We show that if the ﬁrst problem has a PTAS that then there is a PTAS for general instances of BISECTION (designing such a PTAS is a famous open problem). This follows from the following reduction: Given any instance of BISECTION with n vertices, addto it two disjoint cliques of size 2n each. The resulting instance is 2/5dense, but the capacity of the minimum bisection is unchanged. Now we show that if there is a PTAS on everywhere1/2dense instances of MINVERTEXCOVER, then P = N P. We rely on the result of [PY91, ALM+ 92] that P = N P if there is a PTAS for MINVERTEXCOVER on the following simple family of graphs: each of the n vertices has degree at most 5, and the smallest vertex cover has size at least n/2. Notice that given such a simple graph we can add a clique on n vertices to the graph and put a complete bipartite graph between the original vertices and the new vertices. This raises the degree of every vertex to n (so the graph becomes everywhere1/2dense) and raises the size of the minimum vertex cover by exactly n. Thus a PTAS on the resulting instance is a PTAS on the original instance. 8 Conclusion We suspect that our technique of approximately reducing quadratic programs to linear programs might be useful in nondense instances of problems. Of course, the exhaustive random sampling that underlies our work no longer suﬃces, since an additive approximation is not good enough in that case. But some other approximation method could plausibly replace it. If such an approximation method can be found, it would probably also improve performance on dense instances, by removing theerror due to the sampling lemma. Note that the error introduced by the RaghavanThompson technique in our approximation algorithm is much smaller than that introduced by the sampling step (the former error is an additive term of O(n1.5 log n) in the case of quadratic programs; the latter error is Ω(n2 )). Does a good approximation algorithm exist for general BISECTION? What about an inapproximability result? Our results suggest how not to try to prove inapproximability results. Recall that the standard way to prove the N Pcompleteness of BISECTION uses the fact that 5050 MAXCUT is just BISECTION on the complementary graph. Since 5050 MAXCUT on degree 5 graphs is MAXSN P hard (and therefore has no PTAS), one is tempted to try to use this connection to prove the MAXSN Phardness of BISECTION. This naive idea does not work, since the complementary graph of a degree 5 graph is a dense graph in which the minimum bisection has capacity Ω(n2 ). This capacity swamps the gap (in the capacity of the optimum cut) of Θ(n) present in the instance of 5050 MAXCUT, so the the MAXSN Phardness of BISECTION does not follow. Of course, now we know an inherent reason why such approaches are unlikely to succeed: BISECTION has a PTAS on dense graphs. To conclude, we mention some recent research that extends or improves our work. Arora, Frieze, and Kaplan [AFK96] extendour exhaustive sampling idea to design additive approximation schemes for problems in which feasible solutions are permutations (such as the 01 Quadratic Assignment problem). Frieze and Kannan [FK96] and independently, Goldreich, Goldwasser, and Ron [GGR96] showed that our techniques apply because of certain regularity properties in dense graphs, and used this observation to design linear time additive approximation schemes for most of the problems we have considered here. Frieze 24 and Kannan also point out connections to constructive versions of Szemeredis Regularity Lemma. acknowledgedments We thank the anonymous referee for detailed comments that signiﬁcantly improved the presentation. References [AFK96] S. Arora, A. Frieze, and H. Kaplan. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. In 37th Annual Symposium on Foundations of Computer Science, pages 2130, IEEE Computer Society Press, 1996. N. Alon, A. Frieze, and D. Welsh. Polynomial time randomized approximation schemes for the tutte polynomial of dense graphs. In Proceedings of the 35th Annual Symposium on the Foundations of Computer Science [IEE94], pages 24 35. [AFW94] [ALM+ 92] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof veriﬁcation and hardness of approximation problems. In Proceedings of the33rd Annual Symposium on the Foundations of Computer Science [IEE92], pages 1423. [AS92] S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. JACM 45(1):70122, 1998. Prelim. version in Proceedings of the 33rd Annual Symposium on the Foundations of Computer Science [IEE92], pages 2 13. [BCLS84] T. Bui, S. Chaudhuri, T. Leighton, and M. Sipser. Graph bisection algorithms with good average case behavior. In Proceedings of the 25th Annual Symposium on the Foundations of Computer Science, pages 181192. IEEE, IEEE Computer Society Press, 1984. [BGG93] [B87] M. Bellare, O. Goldreich, and S. Goldwasser. Randomness in interactive proofs. Computational Complexity, 3:319354, 1993. Abstract in IEEE FOCS 1990. R. B. Boppana. Eigenvalues and graph bisection: an averagecase analysis Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, pages 280285, IEEE Computer Society Press, 1987. M. Bellare and J. Rompel. Randomnesseﬃcient oblivious sampling. In Proceedings of the 35th Annual Symposium on the Foundations of Computer Science [IEE94], pages 276287. M. E. Dyer, A. Frieze, and R. Kannan. A random polynomial time algorithm for approximating the volume of convex bodies. Journal of the ACM, 38:117, 1991. [BR94] [DFK91] [DJP+ 94] E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, andM. Yannakakis. The complexity of multiterminal cuts. [FG95] U. Feige and M. X. Goemans. Approximating the value of 2prover proof systems, with applications to max2sat and maxdicut. In Proceedings of theIsraeli Symposium on Theoretical Computer Science, pages 182189, 1995. [FGL+ 91] U. Feige, S. Goldwasser, L. Lovsz, S. Safra, and M. Szegedy. Approximating a clique is almost NPcomplete. In Proceedings of the 32nd Annual Symposium on the Foundations of Computer Science, pages 212. IEEE, IEEE Computer Society Press, October 1991. [FdlV94] W. Fernandez de la Vega. MAXCUT has a randomized approximation scheme in dense graphs. Random Structures & Algorithms, vol. 8(3):187198, 1996. Prelim. manuscript, October 1994. W. Fernandez de la Vega and G. S. Lueker. Bin packing can be solved within 1+ǫ in linear time. Combinatorica:1(4), 349355, 1981. A. Frieze and R. Kannan. The regularity lemma and approximation schemes for dense problems. In Proceedings of the 37th Annual Symposium on the Foundations of Computer Science, pages 1220. IEEE, IEEE Computer Society Press, October 1996. O. Goldreich, S. Goldwasser, and D. Ron. Propertytesting and its connection to learning and approximation. In 37th Annual Symposium on Foundations of Computer Science, pages 339348, IEEE Computer Society Press, 1996. D. Gillman. A Chernoﬀ bound for random walks on expanders. In Proceedings of the 34th Annual Symposium on the Foundations of Computer Science [IEE93], pages 680691. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman and Company, [FL81] [FK96] [GGR96] [Gil93] [GJ79] [GW94] [H96] [H97] [H64] [IEE92] [IEE93] [IEE94] 26 [IK75] [JS89] [JS93] O. H. Ibarra and C. E. Kim. Fast approximation algorithms for the knapsack and sum of subsets problems. Journal of the ACM, 22(4):463468, 1975. M. Jerrum and A. Sinclair. Approximating the permanent. [KZ97] [K84] [KK82] [KLM89] [KSW97] [KP92] [KP93] [LR88] [LY93] 76] [P` [Pap94] [PY91] [Rag88] 27 [RT87] P. Raghavan and C. D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365374, 1987. S. Sahni. Approximate algorithms for the 0/1 knapsack problem. Journal of the ACM, 22(1):115124, 1975. H. Saran and V. V. Vazirani. Finding kcuts within twice the optimal. In IEEE, editor, Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, pages 743751, San Juan, Porto Rico, October 1991. IEEE Computer Society Press. D. Shmoys. Computing nearoptimal solutions to combinatorial optimization problems. In Combinatorial Optimization, DIMACS Series in Discrete Math and Theoretical Computer Science, (W. Cook, L. Lovasz, and P.D. Seymour, eds.) AMS, 1995, pages 355397. M. Yannakakis. On the approximation of maximum satisﬁability. In Proceedings of the 3rd Annual ACMSIAM Symposium on Discrete Algorithms, pages 19. ACMSIAM, January 1992. [S75] [SV91] [Shm94] [Yan92] 28 Poltica de privacidad 
