Approximation algorithms for the Maximum Induced Planar and Outerplanar Subgraph problems

,with an amount offlow equal to the requirement of job.We have two paths,carryingflow each,for each job with requirement;these serveto saturate the edge.The other two terminals on will have paths through and respectively,carrying units offlow;and the terminals and can then receive units offlow each on their unique paths from.Conversely,suppose there is a routing whose equilibrium allocation satisfies.The vector can only contain at most entries equal to,so these must be associated with all the terminals of the form.Also,can only contain at most entries equal to,so these must be associated with paths that pass through of the edges into.All the remaining terminals must get aflow value of at least—this therefore consists of of terminals of the form,as well as of the terminals at.Each terminal of the form must get at least aflow of ,so at most one path bound for can pass through each of and.Hence at least two of these paths must pass through the edge.We claim that in fact exactly two of these paths pass through each such edge(and hence exactly one passes through each of and).For suppose that at least three passed through.Then no terminal bound for could use,and so some edge would carry two paths bound for,each with aflow of;therefore,it would follow that no terminal from could make use of the edge,and this would force more than one path bound for to pass through one of or,a contradiction.Thus,of the terminals at get aflow value equal to ,so we observe that at least of the edges of the form must carry a single path only.We will call these pure edges,and the other edges of the form mixed.We have therefore established the following two proper-ties of our routing whose allocation is at least as fair as :There are mixed edges of the form;these are associated with indices for which has require-ment,and on each one,there is a single path bound for with aflow of.There are pure edges of the form;these are associated with indices for which has requirement,and on each one,there is a single path bound for with aflow of.Hence for each edge that carries positiveflow,we can assign job to machine;this will be a feasible as-signment of jobs to machines in the original load balancing problem.source sjob j of req 1/2job i of req 1four terminalsterm.term.machinesubgraphterminalsnode ,and edges for each pair such that machine belongs to the set .We also create a sin-gle node that will hold terminals ,and add edges for each .This defines the “core”of the construction,through which we encode the condition that job can only be as-signed to a machine in .Moreover,if we view this por-tion of the graph in isolation,we can observe the following:Since there are only edges entering ,and terminals at ,we know that the fairest allocation for these terminals would have entries equal to and entries equal to,and which get .This is what we accomplish in the remainder of the construction.For each jobwith a requirement offlow,and all terminals in receive either or units offlow.Now consider the problem offinding an approximate fair flow.Our algorithmfinds the fairest binaryflow.We claim here that thisflow satisfies our approximation guarantee.Theorem3.6The fairest binaryflow is in2-approximate equilibrium.Proof.We use Corollary3.5for the proof.Suppose a termi-nal receives units offlow.We need to prove that we cannot increase theflow to without decreasing theflow to some other terminal that receives at most units of flow.Consider the cut in the Corollary.The terminal is on the sink side of.The cut is saturated,so we cannot increase theflow to without decreasing some otherflow across the cut.However,all terminals on the sink side of receive at most units offlow.4The NP-Completeness of Fairest Allocation We formulate here a decision problem associated withcomputing a fairest routing,and show that it is NP-complete.The reduction is somewhat complicated for the following reason:We are dealing with a single-sourceflowproblem with unit capacities,and to obtain an NP-completeproblem here,one typically needs to introduce terminalswith different(unsplittable)demand cking a no-tion of demand in our problem,we must simulate such de-mands using the constraints imposed by the equlibrium con-dition(.Theorem4.1The following problem is NP-complete:given a single-source routing problem with a unit-capacity directed graph,source,terminals,and an allo-cation vector,is there a routing of the terminals whoseequilibrium allocation vector satisfies?(I.e.is at least as fair as.)Proof.The problem is in NP since we can exhibit thepaths in such a routing,and in polynomial time compute itsequilibrium allocation vector in order to compare it to.To show NP-hardness,we reduce from a special caseof the non-uniform load balancing problem considered by Lenstra,Shmoys,and Tardos[10].We have a set of jobs,and a set of machines;for each job,there is a set on which can be run.Each job has a requirement with the property that each is equal to either.Let denote the jobs of requirement,and let denote the jobs of requirementby.5without affecting the one unit offlow sent along those that belong to.This means that we get the desired maximum unsplittableflow,and a path decomposition of thisflow gives the paths claimed by the theorem.Our goal is thus to modify the paths forso as to satisfy the assumption above:If a path uses one of the edges in the pathsbackwards(i.e.,uses the residual edge),then the cor-responding terminal is an endpoint of a(possibly different)path.Once we have such paths we can use the argument above to obtain the theorem.We will modify the paths using a process that is similar to the Gale-Shapley stable marriage algorithm[4].(Indeed, we can carry out the remainder of the proof through a re-duction to the stable marriage problem;however,we feel it is simpler here to provide a direct argument.)We say that paths and meet if has the terminal as an end-point,or if a contiguous segment of consists of back-ward edges from.Note that there may be many such meetings,in this sense,between the same pair of paths and.Suppose a path meets a path,but is not an endpoint of any path.If there are many paths that meet ,then let be the path that meets at an edge closest to its terminal.We change so that it begins from this terminal,and continues along the backward edges of until the meeting point;it then continues as before.This re-routing of a path leads to an alternate set of paths that also satisfies the above properties,and hence can also be used for augmentation.We repeat this process until there are no pairs of paths and that satisfy the condition above.We now want to argue that this process terminates;for when it does,we have the set of augmenting paths needed tofind theflow .To show termination,note that each re-routing de-creases the number of distinct meetings between a path inand a path in:before the re-routing,path met some other path before meeting ,and this meeting is now eliminated.we have.This implies the theorem:The value,the sum of the smallest loads in the algorithm’s assignment,needs to be compared to the smallest values in loads,whereas here we compare it to a set of values that may not be the smallest.Consider the subset of the jobs that are assigned to ma-chine.We now show thatTo see this consider two cases.Let be the index of the job in with maximum load.If then the in-equality is true term by term due to Lemma2.8.Ifthen our assumption that is ordered last in implies that all jobs in participate in the sum.Now the state-ment follows from Lemma2.7as the sum of the loads in the fractional assignment is bounded bySumming over all machines we get the desired bound.an assignment,it is easy tofind the fairest allocation of load for the assignment.This again is based on the equilibrium condition(),and the following provides a characterization analogous to Lemma2.1.Lemma2.6In a(possibly fractional)assignment of jobs to machines let denote the set of jobs assigned(in part)to machine.The fairest allocation of loads has the following property.Each machine has an associated critical load ;and the load of any job is. For each machine,either the machine is fully loaded,orover all.Further,if some job does not achieve its upper bound,thenThat is,is the minimum load among jobs on that are not able to achieve their upper bounds.We will consider assigning each job to a unique ma-chine,and then construct the fairest allocation of load from this assignment.Notice thatfinding the fairest assignment is NP-hard,as deciding if there is an assignment in which all jobs can be assigned their maximum load is a standard NP-hard scheduling problem[10].Our goal will be to make the resulting loads closely ap-proximate the load sequence of the fractional assignment. Instead of a coordinate-wise approximation of loads,we will give a prefix-sum2-approximation.We observe that it might not be possible to approximate the vector of fairest fractional loads with a fair integer assignment. Consider,for example,a problem in which we have ma-chines.Assume that thefirst job can be as-signed to any machine,and has.In addition to this job,for each machine,there are jobs with that can only be assigned to.Now fraction-ally,we can assign each job its maximum load by spreading the load of job across all machines.However, in any integer assignment,the fair load for that assignment will have;i.e.,there is no way to approximate the optimal fractional fair load of job1in an integer assign-ment.We use Megiddo’s algorithm[12]to obtain a fairest frac-tionalflow.We say that a job is integrally assigned to machine is the entire allocation of job is to machine; otherwise,we say that it is partially assigned to those ma-chines on which it receives a strictly positive allocation.An assignment of jobs to machines is integral if all jobs are integrally assigned by.We use the rounding algorithm of Lenstra,Shmoys and Tardos[10]to create an integral as-signment from.Let be the set of jobs assigned to machine by,and let denote the fair load of this assignment.Theorem2.7([10])Assume is a fractional assignment of jobs to machines assigning load to job node.The approximation algorithm of[10]constructs an integral as-signment so that for each machine,consists of all the jobs that were integrally assigned to by, plus at most one additional job that was partially assigned to.Since did not assign more than unit of load to any machine,we consequently have.First we analyze the fair loads of the set of jobs for a single machine.Let denote the job with maximum load in,Lemma2.8The fair load of all jobs with the possible exception of job have.Proof.We say that is saturated by if some job that was integrally assigned to by has a load. Let denote the critical load(in the sense of Lemma2.6) of machine in the fairest fractional assignment.We define to be if is saturated by;otherwise,we define to be the maximum of over all jobs that were integrally assigned to by.We claim that the critical load of machine for the assignment is at least.To see this,we consider two cases,depending on whether or not is saturated by.If is saturated,then some job that was integrally assigned to is given load by;by setting the critical load for to,this job’s load decreases by relative to the loads in the fractional solution,and creates enough room for one extra job with load at most.If is not saturated,then by setting the critical load for to,we divide by at most two the load of all jobs that were integrally assigned to by.Ifis the unique job that was partially assigned to by, and its load decreases by more than a factor of two,then we must have,whence is the job of maximum load,and constitutes the exceptional job in the statement of the lemma.We will use more generally to denote a possibly par-tial assignment of jobs to machines;we write to de-note the number of jobs assigned by.We say that isa(partial)assignment of maximum degree if the maxi-mum number of jobs assigned to a machine is,and isa maximum assignment of degree at most if the number of unassigned jobs is the least possible among all assign-ments of degree at most.Given any assignment of jobsto machines of degree at most,we can use augmentingpaths tofind a maximum assignment of degree at most .We will refer to this process as A UGMENT().Our load balancing algorithm starts with,and defines =A UGMENT()iteratively for until all jobs get assigned.The assignment at termination is thenreturned;we denote this assignment.The assignment found by=A UGMENT()has the following properties.First,all jobs assigned in are also assigned in.Second,if and denotes the degree of machine in assignments and then. Both of these properties follow from the augmenting path algorithm:augmenting paths never use the backwards edges leaving the sink or entering the source.These two properties imply that thefinal assignmentin a sense contains an optimum assignment for all degrees .Let be the number of jobs assigned to machine by thefinal assignment.Then we have the following.Lemma2.3For all integers we have that.Further,if the degree of a machine is less than in assignment,then the degree will not change throughout the rest of the algorithm.Proof.Thefirst statement will follow from the monotonic-ity of the degrees during the augmentations.Consider as-signment.The augmentations done after this assignment will not decrease the degrees due to the monotonicity prop-erty.Hence.The right hand side is the size of the assignment of maximum degree obtained by deleting edges from entering nodes of degree more than.The matching is a maximum such matching,so we also have the opposite inequality. The second statement follows immediately from thefirst one and the monotonicity of the degrees.The lemma immediately implies that the assignment is optimum.Theorem2.5The algorithm abovefinds the optimum as-signment of jobs to machines for the load balancing prob-lem.Next we consider a more general version of the fair load balancing problem on machines.We will still assume that machines are uniform,in that the maximum possible load of each machine is the same.However,jobs will no longer be uniform.Assume that we have an upper bound for the amount of processing power a job can use.Now an assignment of jobs to machines,and loads for each job,must satisfy the following.(i).(ii)If denotes the set of jobs assigned to machine, we must have that.(iii)The allocation of loads to jobs satisfies the max-min equilibrium condition():we cannot increase the load of one job with without decreasing the load of some other job that has.We can think of this assignment problem as aflow prob-lem in the following three-layer graph.We have a source connected to nodes representing each of the machines with an edge of capacity.There is an edge of infinite ca-pacity from machine node to job node if belongs to.Finally there is an edge from each job node to a corresponding terminal with capacity.A fairest fractionalflow[12]in this network corresponds to a fairest fractional assignment of job loads to machines. Let denote this fairest fractional assignment,and let denote the load of job in.Now consider an assignment of jobs to machines,and let be the set of jobs assigned to machine.Given suchof the most natural of these without relaxing the equilibrium condition().First,the single-source unsplittableflow problem ona two-level unit-capacity graph is equivalent to thefollowing load balancing problem:we have a set of jobs,and a set of machines;for each job,there is a seton which can be run.Each machine has the same“processing power.”We wish to assign each job to a machine,and our fair allocation vectorspecifies the fraction of processing power each job receives on its assigned machine.We will call this the uniform load balancing problem.More generally,each job can have an upper bound on the amount of processing power it wants.In this setting,we will only consider allocation vectors for which for each.We will call this the non-uniform load balancing problem;this problem too can be encoded in the single-source unsplittableflow prob-lem,with the upper bounds appearing as capacities. Wefirst show that a fairest allocation vector for the uni-form load balancing problem can be computed in polyno-mial time.This can be viewed as a natural analogue of Megiddo’s result to a setting with unsplittable assignments; the tractability of the problem comes essentially from its connection with bipartite matching,although it is important to note that the allocations in the optimal fractional and in-tegerflows are not the same.Finding a fairest allocation for the non-uniform load bal-ancing problem is NP-complete;indeed,even determining whether every job can achieve its upper bound is an NP-complete problem considered by Lenstra,Shmoys,and Tar-dos[10].We give a polynomial-time algorithm that pro-duces a prefix-sum-approximation to the fairest alloca-tion.The approximate allocation we produce is(following our discussion above)in max-min equilibrium.We begin from a fairest fractional allocation of jobs to machines—here the allocation of one job can be spread over sev-eral machines in its set—computed via Megiddo’s al-gorithm.We then build on the fractional rounding algo-rithm in[10]to obtain the approximation.Our prefix-sum approximation in fact shows a type of integrality gap in this multi-coordinate setting;it is a prefix-sum-approximation to the optimal fractional allocation.We will describe simple examples in which there cannot be a coordinate-wise-approximation to this fractional optimum.Organization.The remaining three sections of the paper can be read independently.Section2develops the algo-rithms for the load balancing problem without relaxing the equilibrium condition().In Section3we consider the single-source fair unsplittableflow problem on an arbitrary unit capacity directed graph.We develop a general approxi-mation algorithm for this problem by relaxing both the opti-mality and the equilibrium requirements.Finally,Section4 shows that the single-source unsplittable fairflow problem is NP-complete on unit capacity directed graphs.2Fair Load Balancing AlgorithmsThe fair load balancing problem is concerned with as-signing jobs to machines.Assume that we have a set of jobs,and a set of machines;and for each job,there is a seton which job can be run.An assignment is a function so that assigns each job to a machine in .First we consider the special case of the uniform load balancing problem,and show that an optimum fair solution can be found in this case.Then we consider extensions to problems where the jobs have different needs.The uniform fair load balancing problem can be restated as follows.We want to assign jobs to machines,and choose a load for each job so that the following two conditions hold.First,if denotes the set of jobs assigned to ma-chine,we must have that.Second,the set of allocated loads sorted from smaller to larger should be lexicographically maximal.If we are given an assignment of jobs to machines the corresponding fair loads are very easy to compute: Lemma2.1Given an assignment of jobs to machines,the fairest allocation load is to assign loada polynomial-time algorithm for computing a fairest rout-ing,he showed that the fairestflow is a maximumflow—with fractionalflow,one does not sacrifice throughput byimposing fairness.In this work,we focus on the analogous problem,com-puting a fairest routing,in the setting of single-source un-splittableflow[3,8,9].Once we move to unsplittableflow, the basic problem becomes NP-complete,even in the unit-capacity case with all equal to.More precisely,we canprove that the following decision problem is NP-completein the unit-capacity case:given,,the terminals,and a vector,is there a routing of the terminals for which theallocation vector satisfies?(Additionally,we can show that the fairestflow need not be a maximum unsplit-tableflow.)In view of this NP-completeness result,we focus on ob-taining both general approximation algorithms and exact al-gorithms for polynomial-time special cases.The optimiza-tion problems here are over the ordering on allocation vec-tors defined by fairness—hence,since there is no single nu-merical measure,we must be careful in how we define our notion of approximation to the optimum.We propose the following two natural definitions of approximation.First, we say that is a coordinate-wise-approximation to if for each,the smallest entry in is at least times the value of the smallest entry in.As a weaker no-tion,we say that is a prefix-sum-approximation to if for each,the sum of the smallest entries in is at least times the sum of the smallest entries in.In other words,a prefix-sum approximation ensures that the subsets of terminals with the smallest allocations receive sufficient bandwidth.When we move to approximate solutions,it is very im-portant that we can keep in mind that the equilibrium con-dition(),or a relaxed version of(),serves as an addi-tional feasibility requirement on the solutions we can pro-duce:in effect,we are able to choose only the paths, for then the network uses()to enforce the unique equilib-rium allocation vector.(Of course,in the fairest routing, the allocation will necessarily be in equilibrium.)This requirement rules out,for example,the following simple approach based on the Dinitz-Garg-Goemans unsplittable flow approximation algorithm[3]:compute the fairest frac-tionalflow using Megiddo’s algorithm,scale all resulting allocations down by a factor of,and route them as unsplit-table demands.The problem is that these scaled demands are generally very far from equilibrium for the paths used. For example,if the fairest fractionalflow has allocations of widely varying magnitude,it is easy tofind examples in which the Dinitz-Garg-Goemans algorithm produces a routing whereflow paths with both small and large alloca-tion share edges,and the allocation vector is arbitrarily far from satisfying the equilibrium condition().All previous single-source unsplittableflow algorithms[8,9]exhibit thesame problem.Summary of results:Routing.For the single-source un-splittableflow problem on an arbitrary directed graph with unit capacities,we indicated above thatfinding a fairest al-location vector is NP-complete.We develop a general ap-proximation algorithm for this problem by relaxing both theoptimality and the equilibrium requirements.First,what do we mean by relaxing the equilibrium requirements?For a constant,we say that an allocation vector is in a state of -approximate equilibrium if it is not possible to raise the value of an entry without decreasing some other entry such that.Thus,-approximate equilibrium indeedcorresponds to max-min equilibrium;we believe that ap-proximate relaxations of these natural equilibrium notions raise a number of interesting issues in their own right.We give an algorithm that produces a routing whose allo-cation is in-approximate equilibrium,and is a coordinate-wise-approximation to the allocation of the fairest frac-tional routing.We develop the algorithm by computing a fairestflow for the following“discretized”version of the fairest rout-ing problem.Suppose we only consider routings whose al-location vectors have entries that are all inverse powers of two;we will call such routings and allocation vectors bi-nary.Then we can restrict our fairness ordering to bi-nary allocation vectors,and seek a fairest allocation of this type.We show how tofind a fairest binary routing in poly-nomial time,for the single-source unsplittableflow problem on an arbitrary unit-capacity directed graph.It is not dif-ficult to show that the fairest binary routing we obtain is both a coordinate-wise-approximation to the unrestricted fractional optimum,and in a state of-approximate equilib-rium.Wefind the existence of a polynomial-time algorithm for fairest binary routings somewhat surprising,given that the same problem for unrestricted routings is NP-complete.As a basic building block in the algorithm,wefirst establish the special case that if all terminals can be routed with at most two paths on any edge,then the fairest unrestricted routing (which will be binary)can be computed in polynomial time. We then apply this result over increasingly large cuts in the graph to piece together an optimal binaryflow.A natural problem is to provide a good approximation to the fairest unsplittable routing in an arbitrary directed graph without relaxing the equilibrium condition();we leave this as an open question.Summary of results:Load Balancing.The setting of single-source unsplittableflow contains a range of load bal-ancing problems.We begin by providing algorithms for twofixed set of paths,and one wants to associate rates with these paths.It is easy to show that the max-min fair allocation for afixed set of paths is unique,and a number of simple,ef-ficient algorithms have been developed to compute this al-location(e.g.[1,2,5]).A wide range of network routing protocols employ such algorithms to enforce max-min fair-ness(or a close approximation)on the paths used for routing connections.Note that all of this takes place,however,after the paths themselves have been chosen;very little work has been devoted to understanding the relationship between the way in which one selects paths for routing,and the amount of throughput one obtains from the resulting fair allocation on these paths.Suppose we want to select paths for rout-ing so as to provide a bandwidth allocation that is as fair as possible(in the max-min sense);how should we go about doing this?Megiddo[12]addressed this problem in the set-ting of single-source fractionalflow,in whichflow must be sent fractionally to a collection of terminals from a common source,and provided an elegant polynomial-time algorithm.In this work,we consider the setting in which each connection must be routed on a single path—i.e.we seek an unsplittableflow.The single-source case here presents qualitatively new issues from those encountered in Megiddo’s setting,for we can show that the fundamental analogue of his problem is now NP-complete.A number of basic load balancing problems arise naturally as special cases of this single-source unsplittableflow model.We ob-tain thefirst approximation algorithms for the problem of optimizing over path selection to provide the fairest possi-ble routing.The issues that arise in this framework turn out to involve a number of interesting and very basic trade-offs between the throughput and the type of equilibrium con-straints imposed by max-min fairness.We now provide a concrete formulation of these opti-mization problems,and then summarize our results in more detail.Formulating the problem:Max-min fairness and ap-proximation guarantees.We seek routings from a com-mon source node to a collection of terminals in a network.A routing,in the present framework,consists of two com-ponents—the choice of paths that the traffic will use,and the allocation of available bandwidth on these paths to the different connections.Thus,let be a directed graph with a capacity on each edge.We designate a source and a set of terminals.A rout-ing of the terminals consists of a set of paths—with a path from to—and an allocation vector.We view the-connection as being assigned path,with bandwidth allocation,or rate,.We say that this routing is feasible if,for all edges,the total bandwidth allocated for paths using is at most;that is, the sum of over all containing is at most.One can derive max-min fairness from the following in-tuitive approach tofinding the“fairest”allocation:One shouldfirst make sure that the minimum bandwidth given to any connection is as large as possible;then,ignoring this“minimum”connection,one should make sure that the minimum bandwidth given to any of the connections thatcan still get additional bandwidth is as large as possible; and so on.More formally,given two-tuples of num-bers and,each in non-decreasing order,we say that lexicographically dominates if,or there is some index for which andfor all.Given two allocation vectors and, we say that is as fair as(written)if the sorted or-der of the coordinates of lexicographically dominates the sorted order of the coordinates in.We will say that and are equivalent if both and.This relation defines a total order on the equivalence classes of alloca-tion vectors;the vectors in the unique maximal equivalence class under are thus the fairest allocations.One can also use the following equivalent definition of a routing with allocation vector being“fairest”in the max-min sense:There is no way to increase any entry without decreasing some other entry such that.As we discussed above,max-min fairness in the net-working community has been applied primarily to the set-ting in which one is given not only a set of connections in a network,but also the paths that they are to use. Thus the only issue is to determine the allocation vector, which is unique in this case;and this can be accomplished by a variety of efficient algorithms(see e.g.[1,2,5]).Net-work protocols that employ max-min fairness thus enforce the following max-min equilibrium condition:()For any routing with paths and allocationvector,must be a fairest allocation given thepaths.The crucial issue raised in the discussion above is then the following.We wish to choose paths for routing a set of connections,with the bandwidth allocation vector then uniquely determined by the equilibrium condition().The amount of bandwidth utilization in a fairest allocation de-pends heavily on the set of paths that one chooses; some choices of paths allow for much greater fair utiliza-tion of the network than others.The fundamental question we seek to address is that of determining the fairest rout-ing,optimizing over all possible choices of paths,with the allocation vector determined by().For example,does the fairest routing achieve the maximum possible throughput of any routing?This was the precise problem considered by Megiddo[12]in the context of the single-source fractional flow problem,in which all connections share a common endpoint,but one can divide theflow for a single connec-tion fractionally over many paths.In addition to providing。

Dependent Rounding in Bipartite GraphsRajiv Gandhi Samir Khuller Srinivasan Parthasarathy Aravind SrinivasanAbstractWe combine the pipage rounding technique of Ageev&Sviridenko with a recent rounding method developed bySrinivasan,to develop a new randomized rounding approachfor fractional vectors defined on the edge-sets of bipartitegraphs.We show various ways of combining this techniquewith other ideas,leading to the following applications:richer random-graph models for graphs with a givendegree-sequence;improved approximation algorithms for:(i)throughput-maximization in broadcast scheduling,(ii)delay-minimization in broadcast scheduling,and(iii)capaci-tated vertex cover;fair scheduling of jobs on unrelated parallel machines.A useful feature of our method is that it lets us prove certain(probabilistic)per-user fairness properties.1.IntroductionVarious combinatorial optimization problems includehard cardinality constraints:e.g.,a broadcast server may beable to broadcast at most one topic per time step.Two of theknown approaches to accommodate such constraints are thedeterministic method of Ageev&Sviridenko[1],and a prob-abilistic method developed by Srinivasan[17].In this work,we combine these two approaches to develop a dependentrandomized rounding scheme(the term“dependent”under-scores the fact that various random choices we make here(a)Random-graph models for massive graphs.There has been considerable interest recently in modeling mas-sive graphs like the Web graph and the Internet graph(see, e.g.,the talks at[8]);in particular,there has been much study of the power law property of the degree-sequences of such graphs(see,e.g.,[6]).Random graph models for such graphs can let us simulate various algorithms on such mas-sive graphs[7],and hence there has been much renewed in-terest in generating(and studying the properties of)random graphs with a given degree sequence;see,e.g.,[10].How-ever,since a graph is far more than its degree sequence,we ask:can we model additional features of such graphs?Con-cretely,suppose empirical measurements show,e.g.,that ver-tices of degreeOur applications come about by combining the dependentrounding with various other ideas.The per-user guarantees that we are able to provide,as well as application(a),aresome of the novel features of our results;in particular,to ourknowledge,these are not achievable through currently known approaches.2.The Dependent Rounding SchemeSuppose we are given the bipartite graph andthe values as in the introduction.Our dependent random-ized rounding scheme is as follows.Initialize foreach.We will probabilistically modify the inseveral(at most)iterations such that at the end(at which point we will set for all).Our iterations will satisfy the following two invariants:(I1)For all,.(I2)Call rounded if,andfloating if.Once an edge gets rounded,never changes.An iteration proceeds as follows.Let be the current set offloating edges.If,we are done.Otherwise,find(in linear time)a simple cycle or maximal path in the subgraph,and partition the edge-set of into two matchings and.Note that such a partition exists since is a bipartite graph.DefineSince the edges in are currentlyfloating,it is easy to see that the positive reals and exist.Now,independent of all random choices made so far,we execute the following randomized step:With probability,setfor all,and for all;with the complementary probability of,set for all,and for all.This completes the description of an iteration.A simple check shows that the invariants(I1)and(I2)are maintained, and that at least onefloating edge gets rounded in every iter-ation.Let us now analyze the above randomized algorithm.First of all,since every iteration rounds at least onefloating edge, we see from(I2)that we need at most iterations.Let us now prove(P2)for a vertex.If had at most onefloating edge incident on it at the beginning of our dependent round-ing,it is easy to verify that(P2)holds;so suppose initially had at least twofloating edges incident on it.We claim that as long as has at least twofloating edges incident on it,the value remains at its initial value of .To see this,first note that if is not in the cycle/maximal path chosen in an iteration,then is not altered in that iteration.Next,consider an iteration in which had at least twofloating edges incident on it,and in which was in the cycle/path.Then,must have degree two in,and so, it must have one edge in and one in.Then,since edges have their value increased/decreased by the same amount as edges in have their value de-creased/increased,we see that does not change in this iteration.Now consider the last iteration at the beginning of which had at least twofloating edges incident on it.At the end of this iteration,we will have,and will have at most onefloating edge incident on it.It is now easy to note that(P2)holds.Properties(P1)and(P3)can be proved by induction on the number offloating edges,inspired by the approach of[17]; we just give a sketch of the proofs here.Fix a vertex and an edge;let be the random variable denoting the value of at the beginning of iteration.We will show by backward induction on thatPr(2) we may then substitute to see that(P1) holds.The base case where,is trivial.Assuming (2)for,let us prove it for.Supposefor some.In iteration,either is set towith probability,or there are values and such that: with probability,andwith probability.So by the induction hypothesis, Pr equalsThis completes our sketch of the proof for(P1).Property (P3)can be proven by a similar,slightly more complicated, induction.2.1.Random-graph models for massive graphsRecently,there has been growing interest in modeling the underlying graph of the Internet,WWW,and other such mas-sive networks.If we can model such graphs using appropri-ate random graphs,then we can sample multiple times from such a model and test out candidate algorithms we have for such graphs,such as Web-crawlers.A particularly success-ful result of the study of such graphs has been the uncover-ing of the power-law behavior of the vertex-degrees of manysuch graphs(see,e.g.,[6]);hence,there has been much in-terest in generating(and studying)random graphs with a given degree-sequence(see,e.g.,[10]).Web/Internet mea-surements capture a lot of connectivity information in the graph,in addition to the distribution of the degrees of the nodes.In particular,through repeated sampling,these mod-els capture the probability with which a node of a certain degree might share an edge with a node of degree.Our question here is:since a network is much more than its de-gree sequence,can we model connectivity in addition to the degree-sequence?Concretely,given,a degree-sequence ,and values,we wish to generate an-vertex random graphin which:(A1)vertex has degree with probability,and (A2)the probability of edge occurring is.(Note that we must have.)This is the problem we focus on,in order to take a step beyond degree-sequences.It is easy to see that our dependent rounding scheme com-pletely solves this problem,if is bipartite.Next,can we get such a result for general graphs?Unfortunately,the an-swer is no:the reader can verify that no such distribution (i.e.,random graph model)exists for the triangle with(and hence with). This example has being odd,which violates the basic property that the sum of the vertex-degrees should be even.However,even if the vertex-degrees add up to an even number,there are simple cases of non-bipartite graphs where there is no space of random graphs which satisfies(A1)and (A2).(Consider two vertex-disjoint triangles with all six values being,and connect the two triangles by and edge whose value is.)Thus,we need to compromise–hope-fully just a little–for general graphs.We show how to effi-ciently generate random graphs that preserve(A2),and relax (A1)to have with probability one that for each,its(ran-dom)degree satisfies.The only other method we know of in this context is to construct a random graph where each edge is put in independently,with probability.This again preserves(A1),but does much worse for(A2):the high-probability guarantee we get here is that for each,3.1.1Integer Programming FormulationWe use the following integer programming(IP)formulation. The binary variable iff page is broadcast at time .The binary variable iff request is satisfied at some time.Thefirst set of constraints ensure that whenever a request is satisfied,page is broadcast at.The second set of constraints ensure that at most one page is broadcast at any given time.The last two constraints ensure that the variables assume integral values. By letting the domain of and be,we obtain the LP relaxation for the problem.Maximize(3)3.1.2A-approximation Algorithm1.Solve optimally the LP relaxation.2.Construct a bipartite graph as follows. consists of vertices that represent time slots.Let be a ver-tex in corresponding to time.Consider a page and the time instances during which page is broadcast fractionally in the LP solution.Let these time slots besuch that.We will group these time slots into windows,,such that in each window except thefirst and the last,exactly one page is broadcast fraction-ally.Thefirst and last windows may broadcast a full page or less.The grouping of time slots into windows is done as fol-lows.Choose uniformly at random.represents the amount of service provided by thefirst window.For each time instance,we will associate a fraction that rep-resents the amount of contribution made by time slot to-wards the fractional broadcast of page in.For all and for,define and as follows.Ifthen,and oth-erwise.For all,if thenand otherwise.A time slot belongs to iff.This implies that a window consists of consecutive time slots and that a time slot can belong to at most two windows.Also,the total number of windows,. The vertex set consists of vertices that represent pages.For each page,we have vertices in.For all and is connected to vertices corresponding to time-slotsWp W p2pvp1vp2vp3vp4pUVFigure1.Subgraph of relevant to page whose,values are.in.The value of an edge is equal to.This construction is illustrated in Figure1,in which a subgraph of that is induced on the vertices and edges relevant to a particular page are shown.and, values are.3.Perform dependent rounding on.In the rounded solu-tion,if an edge gets chosen then we broadcast page at time.Analysis.Consider a request.Let.Let be the fraction of request satisfied by the optimal LP so-lution before its deadline.Note that the fraction can span at most two adjacent windows.Let. Picking uniformly at random is equivalent to pick-ing uniformly at random.Fix.Let andbe the set of time slots serving in and respec-tively.Let be the random variable that is iff page is broadcast during slot in the rounded solution and is oth-erwise.Note that and are at most, because of property of dependent rounding.Lemma3.1For afixed,let be the random variable that is if is satisfied in the rounded solution and is oth-erwise.Then,E if,and E if.Proof impliesE PrPrPr PrifotherwiseLemma3.2Let be the random variable that is iff is satisfied before in the rounded solution and is other-wise.Then,E.Theorem3.4Let be the random variable representing the total number of requests satisfied by our algorithm.Then, E.R EQUEST C ONSOLIDATION page1234for down to do56if then78910else1112returnFigure2.Algorithm to obtainrequest in,we have a vertex in.Let be the set of time slots that satisfy half of request in the LP solution at minimum cost.For each time slot ,define.In other words,is the contribution of time slot towards satisfying exactly half fraction of request.The edge set consists of edges that connect each vertex to the vertices corresponding to time slots in.The value associated with an edge,where is.Note that for any two edges and,and correspond to request for two different pages.4.Perform dependent rounding on.For any request,if an edge is selected then broadcast page at.3.2.3AnalysisFor any request,let be the fraction of request satisfied in the LP solution at or before thefirst time instance such that and.Let be the cost of satisfying this fraction of request.Let be the cost of satisfying the next half of request,i.e,the cost of satisfying exactly half fraction of after.Let be the cost of satisfying the last fraction of request .Let be the cost of satisfying in the LP solution.Note that for a request,sincewe have and.For a request, .Let be the random variable that is iff page is broadcast during slot in the rounded solution and is otherwise.Lemma3.5For any request,if is the random variable denoting the cost of satisfying in the rounded solution then we have E.Proof Since,we get E Pr Theorem3.7The above rounding scheme yields a-speed, -approximate solution.3.2.4A-speed,-factor AlgorithmIn this section we give a-algorithm that builds on the -algorithm developed in Section3.2.2.Note that in the -speed solution the requests in get satisfied optimally us-ing the two channels as shown in Lemma3.5.By using two channels we can only guarantee a factor of for the requests in.We now show that by using an extra channel we can satisfy the requests in optimally thus obtaining a-speed,-approximate solution.In addition to the four steps in Section3.2.2,we perform steps and as described be-low.5.Construct a bipartite graph as follows. For each time instance,we have a vertex in.In, for each time,we have one vertex representing all requests such that and. Each vertex is connected to where and .The value associated with each edge is .6.Perform dependent rounding on.For an edgethat gets chosen in the rounded solution,broadcast page at time.We will refer to the broadcast on this channel as the third channel.Lemma3.8For any request,if is the random variable denoting the cost of satisfying in the rounded solution then we have E.Proof Recall the definition of from Section 3.2.3.Let.By property(P2)of dependent round-ing at most one edge incident on the vertex representing gets chosen.By property(P1)of dependent rounding,re-quest gets satisfied on the third channel with a probability with an expected cost of.It gets satisfied on thefirsttwo channels(pages broadcast in step)with a probability.E(5) Let be the last time instance that contributes towards the cost..Also,.Combining these facts with Equation(5),we get E4.Capacitated Vertex CoverLet be an undirected graph with vertex setand edge set.Suppose that denotes the weight of vertex and denotes the capacity of vertex (we assume that is an integer).A capacitated vertex cover is a function such that there exists an orientation of the edges of in which the number of edges directed into vertex is at most.(These edges are said to be covered by or assigned to.)The weight of the cover is,where.The MINIMUM CA-PACITATED VERTEX COVER problem is that of computing a minimum weight capacitated cover.The problem generalizes the MINIMUM WEIGHT VERTEX COVER problem which can be obtained by setting for every.The main difference is that in vertex cover,by picking a node in the cover we can cover all edges incident to,in this prob-lem we can only cover a subset of at most edges incident to node.Clearly,the problem is NP-hard since it general-izes a well known NP-hard problem.We denote by the edges in which are incident to .We also denote by the degree of. For we denote by the subgraph induced by.We denote an edge with end-vertices as a set.We deal with orientation(direction)of edges. Orienting an edge from to is equivalent to replacing it by a directed edge(an arc).A primal-dual factor2 approximation was given by Guha,Hassin,Khuller and Or [12]and a factor4approximation was given using LP round-ing.In this paper,we derive a2approximation by a simple LP rounding method,using dependent rounding.One advan-tage of this approach is the ease of implementation compared to a primal-dual algorithm(since very fast and easy to use LP solvers are available).In addition,more general objec-tive functions can be easily captured in this framework,such as assignment costs(see Section4.2).Recently,Chuzhoy and Naor[5]addressed a variant of capacitated vertex cover problem in which there is a bound on.In other words, a vertex can be used at most times to cover edges.They gave a-approximation for the unweighted case and showed that the weighted case is hard to approximate within a factor of.As a corollary to our rounding procedure,for the weighted version,we obtain a-approximate solution in which a vertex is used at most times.4.1.IP formulation and rounding schemeAn IP formulation is as follows([12]).Minimize(6)In this formulation,denotes that the edgeis covered by vertex.Clearly,the values of in a feasible solution correspond to a capacitated cover.While we do not need the constraints for the IP formulation,they will play an important role in the relaxation.Algorithm Threshold and Round:1.Solve the above LP to obtain an optimal fractional solu-tion.2.Pick a value uniformly at random in the interval.In other words,after rounding the values to we simply define the value to be the number of copies of that are required to cover all the edges assigned to it.Theorem4.1The expected cost of the integral solution produced by Algorithm Threshold and Round,is at most,where is the cost of the minimum frac-tional solution to the relaxation.Moreover,E.Corollary4.2If is an upper bound on,then Algorithm Threshold and Round produces a-approximate solution in which.The proof of Theorem4.1is quite complicated and omit-ted.We will show that if we pick asthen the expected cost of the algo-rithm is at most.Proof We will show that for any vertex,the expected cost of is at most.Since the cost of the solution produced is,the bound follows.Let be the number of edges assigned to by edges that have their value at least.Let,where and is an integer.Notice thatEWe would like to prove that this is at most.We consider two cases:If then the LHS is simply1.If,the claim follows. If and then for the unassigned edges we have,i.e.,at most three times the cost of the opti-mal LP solution..Combining this with Theorem4.1where we bound the expected cost of the weighted sum of the chosen vertices by ,we clearly obtain an integral solution that is a ap-proximation for the problem where our objective is the sum of the weighted cost of vertices and the assignment cost of edges.Theorem4.5Algorithm Threshold and Roundfinds a so-lution such that the expected weight of vertices is at most and the expected assignment cost is at moststar graph,whose center is some machine and whoseleaves are the jobs.We have a dependent rounding in-stance on this graph given by the vector;we modify our dependent rounding scheme as follows.Note that there is no cycle in.In dependent rounding,suppose we pick apath;let the values be the probabilisti-cally changing values as in Section2.We now define tobe the smallest positive for which either or;define to be the smallest positive for which either or. With probability,increment by and decre-ment by;with probability, decrement by and increment by. Finally,suppose the maximal path is just an edge. If and,set to be zero(this is crucial);else(i.e.,if or if),set with probability and set with proba-bility.This scheme has some useful properties which we exploit below.Algorithm.We are given a constant,and proceed as follows.1.Find the lower bound by bisection search,and solve LP optimally to get a solution vector.2.Consider a bipartite graph,where is the set of jobs,is the set of machines and an edgeiff.Repeatedly applying a“scaling-rounding-rescaling”technique of[14]a certain number of times,we obtain the following modified instance.The load on each machine is at most.Moreover,every job is assigned at least fractionally,where.Crucially,there are constants and(with) such that for all,one of the following two conditions holds: (a),or(b)for all such that, we have.3.For each,let be the subgraph of inducedon vertex and its neighbors.Perform-weighted dependent rounding on all the independently,for a certain .Schedule job on an arbitrary machine for which gets rounded to,if such an exists.Theorem5.1The above algorithm yields a-approximate solution in which each job is scheduled with a probability of at leastpubl.html[2] A.Bar-Noy,R.Bar-Yehuda, A.Freund,J.Naor andB.Schieber.A Unified Approach to Approximating Re-source Allocation and Scheduling.Proc.ACM Sympo-sium on Theory of Computing,735-744,2000.[3] A.Bar-Noy,S.Guha,Y.Katz,J.Naor, B.Schieberand H.Shachnai.Throughput Maximization of Real-TimeScheduling with Batching.Proc.ACM-SIAM Symposiumon Discrete Algorithms,742-751,2002.[4] C.Chekuri and S.Khanna.A PTAS for the Multiple Knap-sack Problem.Proc.ACM-SIAM Symposium on DiscreteAlgorithms,213–222,2000.[5]J.Chuzhoy and J.Naor.Covering Problems with HardCapacities.Proc.IEEE Symposium on Foundations ofComputer Science,2002(to appear).[6] C.Cooper and A.Frieze.On a general model of webgraphs.Proc.European Symposium on Algorithms,500–511,2001.[7] C.Cooper and A.Frieze.Crawling on web graphs.Proc.ACM Symposium on Theory of Computing,419–427,2002.[8]DIMACS Workshop on Internet and WWW Mea-surement,Mapping and Modeling,2002.See/Workshops/Internet/program.html.[9]T.Erlebach,A.Hall.NP-Hardness of broadcast schedul-ing and inapproximability of single-source unsplittablemin-costflow.Proc.13th Annual ACM-SIAM Sympo-sium on Discrete Algorithms,194-202,2002.[10] F.Chung Graham and L.Lu.Connected components inrandom graphs with given degree sequences.Manuscript. [11]R.Gandhi,S.Khuller,Y.Kim and Y.C.Wan.Algorithmsfor Minimizing Response Time in Broadcast Schedul-ing.Proc.Ninth Conference on Integer Programming andCombinatorial Optimization,425–438,2002.[12]S.Guha,R.Hassin,S.Khuller and E.Or.CapacitatedVertex Covering with Applications.Proc.ACM-SIAMSymposium on Discrete Algorithms,858-865,2002. [13] B.Kalyanasundaram,K.Pruhs,and M.Velauthapillai.Scheduling broadcasts in wireless networks.In Proc.Eu-ropean Symposium of Algorithms,LNCS1879,Springer-Verlag,290-301,2000.[14] F.T.Leighton,C.J.Liu,S.B.Rao and A.Srinivasan.New Algorithmic Aspects of the Local Lemma with Ap-plications to Routing and Partitioning.SIAM Journal onComputing,V ol.31,626-641,2001.[15]J.K.Lenstra,D.B.Shmoys and´E.Tardos.Approximationalgorithms for scheduling unrelated parallel machines.Mathematical Programming,46:259–271,1990.[16] D.B.Shmoys,´E.Tardos and K.Aardal.ApproximationAlgorithms for Facility Location Problems.Proc.ACMSymposium on Theory of Computing,265–274,1997. [17] A.Srinivasan.Distributions on Level-Sets with Appli-cations to Approximation Algorithms.Proc.IEEE Sym-posium on Foundations of Computer Science,588–597,2001.。

Approximation algorithms for Max-3-Cut and other problems via complex semidefinite programmingMichel X. GoemansMIT 77 Mass. Ave., Room 2-351 Cambridge, MA 02139David P. WilliamsonIBM Almaden 650 Harry Rd., K53/B1 San Jose, CA 95120goemans@ ABSTRACTdpw@ 1. INTRODUCTIONA number of recent papers on approximation algorithms have used the square roots of unity, ?1 and 1 to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semide nite programming in order to obtain near optimal solutions to these problems. In this paper, we consider using the cube roots of unity, 1, ei2 =3 , and ei4 =3 , to represent ternary decision variables for problems in combinatorial optimization. Here the natural relaxation is that of unit vectors in complex space. We use an extension of semide nite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique introduced by the authors in 8] to obtain near-optimal solutions to the problems. In particular, we consider the problem of maximizing the total weight of satis ed equations xu ? xv c (mod 3) and inequations xu ? xv 6 c (mod 3), where xu 2 f0; 1; 2g for all u. This problem can be used to model the Max-3-Cut problem and a directed variant we call Max-3-Dicut. For the general problem, we obtain a .79373-approximation algorithm. If the instance contains only inequations (as it does for Max-3-Cut), we obtain a performance guarantee 7 of 12 + 4 32 arccos2 (?1=4) :83601. This compares with proven performance guarantees of .800217 for Max-3-Cut (by Frieze and Jerrum 7]) and 1 + 10?8 for the general 3 problem (by Andersson, Engebretson, and Hastad 2]). It matches the guarantee of .836008 for Max-3-Cut found independently by de Klerk, Pasechnik, and Warners 4]. We show that all these algorithms are in fact identical in the case of Max-3-Cut./cs/people/dpwA current version of the paper can be found at .Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. STOC’01, July 6-8, 2001, Hersonissos, Crete, Greece. Copyright 2001 ACM 1-58113-349-9/01/0007 ... 5.00.$The uses of linear programming for designing algorithms for combinatorial optimization problems has long been known. Since the seminal paper of Lovasz 13], researchers have investigated the use of nonlinear programming, particularly semide nite programming, since semide nite programs can be solved in polynomial time (up to any prescribed accuracy). At rst it was shown that semide nite programs could be solved via the ellipsoid method 9, 10]; later it was shown that practical interior-point methods for linear programs could be adapted to semide nite programming 1, 15]. One particular use of semide nite programming that has received a good deal of attention is its application to approximation algorithms. An -approximation algorithm is a polynomial-time algorithm for a combinatorial optimization problem that produces a solution of value with a factor of of the optimal value. In 8], the authors introduced the following technique. An optimization problem with binary decisions (e.g. MAX CUT, MAX 2SAT) is modelled with n variables xi 2 f?1; +1g, and an objective function quadratic in these variables. These variables xi are relaxed to n-dimensional unit length vectors vi , and their products xi xj to inner products hvi ; vj i. It is not di cult to show that this relaxation is a semide nite program, and thus can be solved in polynomial time, up to any given accuracy. The solution to the relaxation is mapped to the solution in the original variables by choosing a random vector r from the ndimensional normal distribution, and deriving the solution xi = sgn(hr; vi i). The expected value of this solution can be compared to the value of the relaxation. This technique has been applied, with modi cations, to several other problems in combinatorial optimization (e.g. 2, 3, 6, 7, 12, 14, 21, 23]). In the meantime, researchers in mathematical programming have shown that the interior-point methods that extend polynomial-time solvability from linear programming to semide nite programming also extend polynomial-time solvability to the class of symmetric cones. This includes the second-order cone (also called the ice-cream cone), the cone of semide nite matrices over real numbers/complex numbers/quaternions, and the cone of 3 3 semide nite matrices over octonions. Toh and Trefethen showed that semide nite programming over the complex domain is solvable in polynomial time 22]. Guler 11] showed that theself-scaled cones for which Nesterov and Todd 16, 17] had provided polynomial-time algorithms are exactly the symmetric cones. We propose to take advantage of these developments by using semide nite programming over the complex domain; we call this complex semide nite programming (CSDP). Previously we modelled binary decisions with the square roots of unity 1; we now model ternary decisions with the cube roots of unity 1, ei2 =3 , and ei4 =3 . Given a model of this problem with an objective function quadratic in these variables, we relax these variables to unit length vectors vi 2 C n , where C n is n-dimensional complex space, and relax their products xi xj to inner products hvi ; vj i. This relaxation turns out to be a semide nite program over the complex domain, and is solvable in polynomial time. We extend our randomized rounding technique by drawing a random vector r from the n-dimensional complex normal distribution, then mapping back to the original space by considering the angle of the inner product sei = hr; vi i. We apply these ideas to the problem of maximizing the weight of satis ed two variable equations or inequations mod 3. In particular, in the problem Max 2-Lin-Mod-3 we have n variables xi and m equations xi ? xj c (mod 3) or inequations xi ? xj 6 c (mod 3). For each (in)equation j we are given a nonnegative weight wj , and we must nd values of the xi 2 f0; 1; 2g that maximize the total weight of the satis ed (in)equations. The problem Max 2-Lin-Mod3 can be used to model other optimization problems. We give two examples here, Max-3-Cut and Max-3-Dicut. In Max-3-Cut, we are given a graph G = (V; E ) with a weight we on edge e 2 E . We assume that the weights are nonnegative. For a partition of V into 3 sets V0 , V1 and V2 , we let (V0 ; V1 ; V2 ) = fe = (u; v) 2 E : u 2 Vi ; v 2 Vj for i 6= j g. The goal is to nd a 3-partition (V0 ; V1 ; V2 ) such that w( (V0 ; V1 ; V2 )) is maximized where w(F ) = Pe2F we . Max-3-Dicut is similarly de ned except that G is now a digraph and we would like to maximize w( + (V0 ; V1 ; V2 )) where + (V0 ; V1 ; V2 ) = fe = (u; v) 2 E : u 2 Vi ; v 2 Vj with j ? i 1 (mod 3)g: To model these two problems, we introduce a variable xv for each v 2 V . For the problem Max-3-Cut, we introduce an inequation xu ? xv 6 0 (mod 3) of weight we for each edge e = (u; v). For the problem Max-3-Dicut, we introduce an equation xv ? xu 1 (mod 3) of weight we for each directed edge e = (u; v). We obtain a :79373-approximation algorithm for the general problem Max 2-Lin-Mod-3, a :79373-approximation 7 algorithm for Max-3-Dicut, and a ( 12 + 4 32 arccos2 (?1=4))approximation algorithm for instances of Max 2-Lin-Mod3 that have inequations only, where 3 7 2 12 + 4 2 arccos (?1=4) :83601: This implies a :83601-approximation algorithm for Max-3Cut. Previously, Andersson, Engebretson, and Hastad 2] considered a more general variant of the problem Max 2Lin-Mod-p (for two-variable equations mod p) and shown 1 that they could obtain an ( p + (p))-approximation algorithm, where (p) > 0 is a constant that depends on p; for our simpler version, they gave a proven performance guar1 antee of p (1 + 10?8 ). Their algorithm is based on a (real)semide nite programming relaxation involving p vectors for each variable. In the conclusion of their manuscript, the authors claim numerical evidence for a bound of 1=1:27 :787 in the case p = 3. This is actually not surprising since we are able to show that our complex semide nite programming relaxation (for p = 3) and our rounding scheme are both equivalent to theirs; we can therefore prove that their performance guarantee is :79373. Frieze and Jerrum 7] gave a ( k?1 + (k))-approximation algorithm for the Max k-Cut k problem, and in particular a :800217-approximation algorithm for Max-3-Cut. In 7, pg. 74], the authors state that by computing further terms in their series expansion, they are able to obtain a bound of .832718 for Max-3-Cut. Frieze and Jerrum also use a (real) semide nite programming relaxation and we can show that in the case of Max-3-Cut, our complex relaxation and our rounding scheme is equivalent to theirs, and thus the performance guarantee of their algorithm is :83601. Independently, de Klerk, Pasechnik, and Warners 4] have shown that the performance guarantee of Frieze and Jerrum is .836008. In terms of negative results, Andersson et al. 2] have shown that no -approximation algorithm for Max 2-Lin-Mod-3 can have > 17=18 :944 unless P = NP . Our use of complex semide nite programming is in some sense purely a modelling decision, since complex semide nite programming is reducible to standard (real) semide nite programming. However, we think it makes for cleaner models, algorithms, and analysis than the equivalent models using standard semide nite programming. For instance, the performance guarantee of de Klerk et al. for Max-3-Cut is determined numerically, whereas our performance guarantee for Max-3-Cut is analytic. Also, we believe our model is somewhat cleaner. The modelling approach of Frieze and Jerrum 7] for Max-3-Cut of introducing a single 2dimensional vector for each vertex and then relaxing the dimension restriction does not immediately extend to the case of Max-3-Dicut since in the real case the inner product of two vectors commute. To handle the more general case (of Max-3-Dicut or Max 2-Lin-Mod-3), Andersson et al. 2] de ne three 2-dimensional vectors for each vertex. This is also the general approach taken by de Klerk et al. 4]. The approach described in this paper allows the use of a single complex number (1-dimensional vector) for each vertex or each variable, which is then relaxed to a higher-dimensional vector. The fundamental reason why we can easily formulate a non-symmetric problem (such as Max 2-Lin-Mod-3, in which xu ? xv 6 xv ? xu ) comes from the fact that the inner product of two complex vectors does not commute. Our paper is organized as follows. In Section 2, we review basic ideas of complex numbers and matrices, and introduce some notation we will be using. In Section 3, we introduce complex semide nite programming. Section 4 shows how we model the Max 2-Lin-Mod-3 problem in terms of the cube roots of unity, and how its relaxation is a complex semidefinite program. We also show there that our relaxation is equivalent to Frieze and Jerrum's relaxation in the case of Max-3-Cut. In Section 5 we introduce our algorithm and present its analysis. Section 6 contains a brief discussion of some of the complexity issues since almost all computations have to be carried out approximately. The appendix contains the proofs of equivalence between the various algorithms of Frieze and Jerrum 7], Andersson et al. 2], and de Klerk et al. 4] in the case of Max-3-Cut.For a complex number z = x + iy 2 C , we denote its real part x by Re z and its imaginary part y by Im z. For the polar representation z = rei = cos( ) + i sin( ), r is the modulus jzj and is the argument arg z. The complex conjugate of z = x + iy is denoted by z = x ? iy. Let R n n (resp. C n n ) denote the set of n n matrices over the eld R (resp. C ). We denote the transpose of a matrix M = mij ] (of any size, including of a vector) by M T = mji ] and its adjoint by M = M T = mji ]. We extend the operators Re and Im to complex matrices by letting Re M for M 2 C n n be the real matrix Re mij ] and Im M be the real matrix Im mij ], so that M = Re M + iIm M . A real matrix M 2 R n n is symmetric if M = M T and skew-symmetric if M = ?M T . A complex matrix M 2 C n n is Hermitian if M = M . We let Sn denote the set of symmetric n n real matrices and Hn the set of complex n n Hermitian matrices. Note that for M 2 Hn , Re M is symmetric and Im M is skew-symmetric. As an inner product over C n , we use hu; vi = v u. Recall that hv; ui = hu; vi. For any two matrices A; B 2 Hn , where A = (aij ) and B = (bij ), we let hA; B i be the (Frobenius) inner P product of the two matrices; that is, hA; B i = Tr(B A) = i;j bij aij (which is also Tr(BA) or Tr(AB ) since A; B 2 Hn ). Recall that for a Hermitian matrix M , we have that x Mx = hMx; xi is real for all x 2 C n , and all its eigenvalues are real. A Hermitian matrix M 2 Hn is said to be positive semidefinite if x Mx 0 for all x 2 C n . A Hermitian matrix is positive semide nite if and only if all of its eigenvalues are nonnegative. We denote a positive semide nite matrix M 2 Hn by M 0. A Hermitian matrix M = (mij ) 2 Hn is positive semide nite if and only if it can be expressed as M = V V for some V 2 Hn ; thus M is positive semide nite if and only if there exist vectors v1 ; : : : ; vn 2 C n such that mij = hvi ; vj i.3. COMPLEX SEMIDEFINITE PROGRAMMING2. PRELIMINARIESinite programs are also solvable in polynomial time (up to any given degree of accuracy). Additionally, several interiorpoint methods used to solve SDPs can be generalized to CSDPs 5, 19, 18]. For the purpose of our approximation algorithms, most of the computations have to be done approximately and this is discussed in Section 6. For combinatorial optimization problems, decisions which have two alternatives (such as, whether an edge/vertex is present, or whether a job precedes another) are generally formulated by introducing a binary variable x 2 f0; 1g, or possibly x 2 f?1; 1g. When there are three alternatives, we propose to introduce a complex variable x 2 C which takes as values the third roots of unity, 1, ei2 =3 and ei4 =3 . For simplicity of notation, we will denote ei2 =3 by ! and ei4 =3 by !2 (or !?1 ). We let R3 denote the set of cube roots of unity, then: R3 = f1; !; !2 g. To illustrate this principle, we consider the optimization problem Max 2-Lin-Mod-3. In Max 2-Lin-Mod-3, we are given n variables xu , and m equations xu ? xv c (mod 3) or inequations xu ? xv 6 c (mod 3), where c 2 f0; 1; 2g. The j th (in)equation is associated with a nonnegative weight wj 0. We must choose a setting of the variables xu to values in f0; 1; 2g in such a way that we maximize the total weight of satis ed (in)equations. As we showed in the introduction, Max 2-Lin-Mod-3 can be used to model other optimization problems, including Max-3-Cut and Max-3Dicut. To model Max 2-Lin-Mod-3, we introduce a variable yu for each variable xu . Each variable yu is constrained to belong to R3 . For any set of variables xu 2 f0; 1; 2g, we set yu = !xu . For yu ; yv 2 R3 , observe that hyu ; yv i can take only three values, namely the values in R3 . Furthermore, the equation xu ? xv c (mod 3) is satis ed if and only if hyu ; yv i = !c , and the inequation is satis ed if and only if hyu ; yv i 2 R3 n f!c g. Thus the contribution of the j th equation xu ? xv c (mod 3) to the objective function is 1 1 wj 3 + 1 !?c hyu ; yv i + 3 !c hyv ; yu i ; (1) 3 and the contribution of the j th inequation xu ?xv 6 c (mod 3) to the objective function is 2 wj 3 ? 1 !?c hyu ; yv i ? 1 !c hyv ; yu i : (2) 3 3 Instead of imposing that yu 2 R3 for every u, we relax it to: hyu ; yu i = 1, and hyu ; yv i + hyv ; yu i ?1 for every u; v and every 2 R3 . The last constraint says that hyu ; yv i belongs to the triangle with vertices R3 in the complex plane. The relaxation we have obtained can now be formulated as a complex semide nite program. Letting Y = hyu ; yv i] 2 Hn , we have the constraints hEuu ; Y i = 1 (3) for all u, and the constraints hAc ; Y i ?1 (4) uv4. FORMULATING Max2-Lin-Mod-3Just as linear programming can be generalized by semidefinite programming, semide nite programming over the reals can be generalized by semide nite programming over the complex domain. For lack of a better term, we will call this complex semide nite programming (CSDP). As in semidefinite programming, in CSDP we maximize or minimize a linear function over a square matrix Z 2 Hn subject to linear constraints on Z and the constraint that Z is positive semide nite. More formally, we maximize or minimize hC; Z i for an objective matrix C 2 Hn , subject to m linear constraints of the form hAi ; Z i bi or hAi ; Z i = bi or hAi ; Z i bi where Ai 2 Hn , and subject to Z 0, Z 2 Hn . In fact, CSDP is reducible to SDP, and thus is not a strict generalization of it. We omit the simple reduction for space reasons. The reduction is obtained by using the linear transformation T below that maps matrices in Hn to matrices in S2n : Re T (Z ) = Im Z ?ImZZ : Z Re The polynomial-time solvability of semide nite programs (up to any given degree of accuracy) and the reduction claimed above immediately implies that complex semidef-for every u; v and c = 0; 1; 2, where eu is the vector with zeroes everywhere except for a 1 in the uth component, Euu = eu eT , and Ac = !c eu eT + !?c ev eT . Similarly, the u uv v u objective function can be formulated as hC; Y i (5) where C 2 Hn , by appropriately combining (1) and (2) for each equation/inequation. Our discussion implies that if we solve (5) subject to (3), (4) and Y 0, Y 2 Hn , we obtain an upper bound on the optimum objective function value of Max 2-Lin-Mod-3. We would like to mention that if Y is feasible for the above complex semide nite programming relaxation then Y T is also feasible. This is because ! and !2 are both cube roots of unity. However, in general, the objective function value of Y and Y T are not equal. They will be equal in the special case in which every equation is of the form xi ? xj 0 (mod 3) and every inequation of the form xi ? xj 6 0 (mod 3). This includes the case of Max-3-Cut. If the objective function value is unchanged by replacing Y by Y T , it is also by replacing it with (Y + Y T )=2 which is a real matrix. This means that in this special case our complex semide nite programming relaxation simply reduces to a (real) semide nite programming relaxation. In the case of Max-3-Cut, the above argument shows that our relaxation is exactly identical to the relaxation considered by Frieze and Jerrum 7]. In the algorithm and in our analysis, we will however not take advantage of the fact that the optimum solution can be assumed to be real in the case of Max-3-Cut.5. THE ALGORITHM AND ITS ANALYSIS 5.1 The algorithm10.80.60.40.20 1 0.5 0 −0.5 −1 −0.5 0 0.5 1Figure 1: Probability of xu ? xv satis ed as a function of hyu ; yv i.0 (mod 3) beingWe can now describe the algorithm for Max 2-Lin-Mod3. For a given problem instance, we solve the associatedCSDP as described in the previous section in polynomial time (see Section 6 for a discussion of complexity issues), and obtain vectors yu for each u from the solution matrix Y in polynomial time by Cholesky decomposition (see also Section 6). We then pick a random vector p 2 C n from the complex normal distribution. This is equivalent to drawing each entry pk independently from the univariate complex normal distribution, which in turn is equivalent to drawing Re pk and Im pk independently from the univariate real normal distribution. We then consider the inner products hp; yu i for each u. We create a solution x to the Max 2-Lin-Mod3 instance by setting 8 0 if arghp; y i 2 0; 2 =3) < u xu = : 1 if arghp; yu i 2 2 =3; 4 =3) 2 if arghp; yu i 2 4 =3; 2 ):5.2 The analysisWe now turn to the analysis of the algorithm. As in 8], we rst analyze the probability that a given equation xu ? xv c (mod 3) or inequation xu ? xv 6 c (mod 3) is satis ed, solely given the inner product hyu ; yv i. We then compare this probability to the contribution made to the objective function for the given (in)equation, which also depends solely on the inner product hyu ; yv i. Since this inner product must belong to the triangle de ned by R3 in thecomplex plane (by the constraints of the CSDP), we nd the minimum of the ratio of probability to objective function contribution over the triangle R3 . Throughout this paper, arccos( ) has range in 0; ]. Theorem 1. If hyu ; yv i = re?i then the probability that the equation xu ? xv c (mod 3) is satis ed is 1 P = 3 + 83 2 2 arccos2 ?r cos 23 c + ? arccos2 ?r cos 2 (c3+ 1) + ? arccos2 ?r cos 2 (c3? 1) + : For example, if hyu ; yv i = 1 (r = 1, = 0) and c = 0, we 1 have P = 3 + 8 32 2 2 ? 92 ? 92 = 1, while for c = 1, 1 we have P = 3 + 8 32 2 92 ? 2 ? 92 = 0. If hyu ; yv i = 0, 1 1 we have P = 3 + 8 32 2 42 ? 42 ? 42 = 3 , as expected. Figure 5.2 shows the probability given in Theorem 1 over the entire range of values for hyu ; yv i. By simply complementing the probability in Theorem 1, we get Theorem 2. If hyu ; yv i = re?i then the probability that the equation xu ? xv 6 c (mod 3) is satis ed is P = 2 ? 83 2 2 arccos2 ?r cos 23 c + 3 ? arccos2 ?r cos 2 (c3+ 1) + ? arccos2 ?r cos 2 (c3? 1) + : In order to be able to derive a performance guarantee for the algorithm, we need to compare the probabilities in Theorems 1 and 2 with the corresponding contribution to the objective function of the relaxation, namely to (1) and (2) respectively. We are able to show the following guarantees, from which we can easily derive the existence of approximation algorithms with the performance guarantees claimed in the introduction.R3 thenTheorem 3. If hyu ; yv i belongs to the triangle de ned by1. the probability that xu ? xv c (mod 3) is satis ed is at least 0:79373 times ? 1 + 1 !?chy ; y i + 1 !chy ; y i , u v v u 3 3 3 2. the probability that xu ? xv 6 c (mod 3) is satis ed 7 3 is arccos2 ? ? 2 at 1leastchy ;+ i4 ?2 1 !chy ;(y 1=.4) 0:83601 times ? 12 yv ? 3! u v ui 3 3To prepare for the proof of Theorem 1, we rst need a few simplications. Consider the equation xu ? xv c (mod 3), and the vectors yu and yv .Claim 4. The probability that xu ? xv c (mod 3) is satis ed depends only on hyu ; yv i. In particular, given hyu ; yv i = re?i , one can choose without loss 2of generality yu = e1 and yv = (rei ; s; 0; ; 0) 2 C n with r + s2 = 1.1 , a uniformly distributed angle. Given , this implies that arghp; yv i = + 1 . If we add or subtract from arghp; yu i and arghp; yv i any multiple of 2 =3, xv ? xu is una ected. We can therefore replace 1 by , where is uniformly distributed in 0; 2 =3) and assume that xu = 0. Therefore, Pr xv ? xu c (mod 3) satis ed] Z 2 =3 Pr xv = cj 1 = ] 23 d = 0 Z 2 =3 2 c + < 2 (c3+ 1) d : Pr 3 = 23 0Proof. First note that hp; yu i = p1 ei 1 , and thus arghp; yu i =b1 ; ; bn be an orthonormal basis of C n such that b1 = yu and b2 = c(yv ? hyv ; yu iyu ) with c 2 R so that b2 b2 = 1. Let U 2 C n n have bi as ith column. Hence, UU = I and thus U U = I and U is unitary. Consider now the linear transformation that maps x 2 C n to Ux; this is a rotation. We rst observe that Uyu = e1 and Uyv = (yu yv ; cyv yv ? c(yu yv )yu yv ; 0; ; 0), with the second coe cient being real. Since U is unitary, for any x; y 2 C n we have x y = (Ux) (Uy), and therefore anyProof. Letinner product is preserved after the linear transformation. Thus, Uyv = (rei ; s; 0; ; 0) where r2 + s2 = 1. Also, if we let q = Up where p is distributed according to a complex normal distribution, we notice that (i) q is also distributed according to the same distribution (since q q = p p), (ii) hp; yu i = hq; Uyu i and hp; yv i = hq; Uyv i. Therefore, if we consider Uyu and Uyv instead of yu and yv , we obtain exactly the same distribution for xu and xv , proving the claim.We therefore need to study the distribution for = arghp; yv i? arghp; yu i. Since hp; yu i = p1 ei 1 and hp; yv i = p1 rei( 1 ? ) + p2 sei 2 , we have that = arg(p1 rei( 1 ? ) + p2 sei 2 ) ? 1 = arg(p1 re?i + p2 sei( 2 ? 1 ) ) = ? + arg(p1 r + p2 sei ); where = + 2 ? 1 is uniformly distributed and independent of p1 and p2 . We de ne = arg(p1 r + p2 sei ) where p1 ; p2 ; are independent and p1 ; p2 are distributed according to the density (6) and is uniform in 0; 2 ). Thus = ? . The next step in our analysis is to get a grasp of the distribution of . To do this, we will rst need the following lemma. Lemma 6. For a given ` 0, Pr p2 s `p1 r] = (1 ? r`2 )r+ `2 r2 :2 2By the claim, we can assume that yu = e1 and yv = (rei ; s; 0; ; 0). Now consider the inner products hp; yu i and hp; yv i. We can thus restrict our attention to the rst two coordinates of p; call them p1 ei 1 and p2 ei 2 . Since these coordinates are drawn independently from the complex normal distribution, it is equivalent if we draw independently j uniformly from 0; 2 ) and pj from the density function 2 f (r) = re?r =2 : (6) The probability that the equation xv ? xu c (mod 3) is satis ed depends on arghp; yu i, and on arghp; yv i. The following lemma gives a precise dependence. In the lemma below, as in the rest of the paper, whenever we write Pr < ] we assume that and that is determined up to multiples of 2 ; that is, Pr < ] = Pr +2k < for some k 2 Z ]. = arghp; yv i ? arghp; yu i. Then Pr xv ? xu c (mod 3) satisfied] Z 2 =3 2 c = 23 < 2 (c3+ 1) ? d : Pr 3 ? 0Lemma 5. LetWe have Pr p2 s `p1 r] = = =2 Proof. Recall that p1 and p2 have density f (r) = re?r =2 .Z10 0Z1 Z10f (p1 )Z p1`r=s h0f (p2 )dp2 dp11 2 2 2 2 1 = 1 ? ? 1 + `2 r2 =s2 e?(p1 =2)(1+` r =s ) 0 1 `2 r 2 = 1 ? 1 + `2 r2 =s2 = (1 ? r2 ) + `2 r2 ; where we have used the fact that r2 + s2 = 1. We can now prove the following lemma about the distribution of the angle . Lemma 7. For any 0 2 , we have Pr 0 < ] = 21 + p r sin 2 arccos(?r cos ) : 1 ? r2 cos= 1?Z102 h 2 2 2 2 i p1 e?p1 =2 1 ? e?p1 ` r =(2s ) dp10f (p1 ) ?e?p2 =22 2ip1`r=s2 2dp1p1 e?(p1 =2)(1+` r =s ) dp12γpr 1αps 2Figure 2: Angle .Proof. We argue rst for the case , and obtain the general case later by symmetry. Consider Figure 2. Certainly if 2 ( ; 2 ) then 2 0; ], while if 2 0; ], = then 2 0; ]. If 2 ( ; ), we have if and only if sin , p2 s p1 r sin( ? ) , by the law of sines. Thus forFor the proof of Theorem 1, it is useful to be able to compute Pr 1 < 2 ] for any 1 ; 2 even if one of them is outside the range 0; 2 ). For this purpose, we have the following corollary of Lemma 7. Corollary 8. For any , let g(r; ) = 21 + p r sin 2 arccos(?r cos ) : 1 ? r2 cos Then, for any 1 ; 2 with 0 2 ? 1 2 , we have that Pr 1 < 2 ] = g(r; 2 ) ? g(r; 1 ):Proof. The corollary follows from the fact that (i) g(r; 2 + ) = 1 + g(r; ) and (ii) for 0 1 2 2 , we have that Pr 1 < 2 ] = Pr 0 < 2 ] ? Pr 0 < 1 ]. We can now prove Theorem 1. Proof of Theorem 1. By Lemma 5 and the fact that = ? , we have that Pr xv ? xu c (mod 3) satis ed] is Z 3 2 =3 Pr 2 c + ? < 2 (c3+ 1) + ? d : 2 0 3 By Corollary 8, this is Z 3 2 =3 g(r; 2 (c + 1) + ? ) ? g(r; 2 c + ? ) d : 2 0 3 3 In order to t this integral in the two column format, we take each part at a time. We have that 3 Z 2 =3 g(r; 2 (c + 1) + ? ) d 2 0 3 Z 2 (c+1)=3+ g(r; )d (9) = 23 2 c=3+ Z 2 (c+1)=3+ = 23 21 d 2 c=3+ ! 1 arccos2 (?r cos ) 2 (c+1)=3+ ? 2 (10) 2 c=3+ " # 3 2 (c + 1) + 2 ? 2 c + 2 = 8 2 3 3 + 83 2 arccos2 ?r cos 23 c + ? arccos2 ?r cos 2 (c3+ 1) + ; where (9) follows from a change of variable and (10) from observing that g(r; ) = 21 ? 1 dd farccos2 (?r cos )g : 2 Similarly, we have that Z 2 =3 g(r; 23 c + ? ) d ? 23 0 # " 3 2 (c ? 1) + 2 ? 2 c + 2 = 8 2 3 3 + 83 2 arccos2 ?r cos 23 c + ? arccos2 ?r cos 2 (c3? 1) + :Pr 0sin sin( ? ) p1 r d ; where 2 is the probability that 2 0; ] and the other term is the probability that 2 0; ] given that 2 ( ; ). For convenience, we change variables so that = ? , and the probability becomes Z 1 + ? Pr p s sin p r d : Pr 0 < ]= 2 2 sin 1 0 Then we get Pr 0 < ] Z ? r2 sin2 (7) d = 21 + 2 ) sin2 (1 ? r + r2 sin2 0 = 21 + p r sin 2 1 ? r2 cos ! p = ? tan 1 ? r2 cos2 (8) arctan r sin =0 p 2 2 r = 21 + p r sin 2 arctan ? 1 ?coscos r 1 ? r2 cos = 21 + p r sin 2 arccos(?r cos ) 1 ? r2 cos where (7) follows by applying Lemma 6 and (8) follows from 20, pg. 441, number 360]. To obtain the proof statement for all values of , we use symmetry. First observe that for 0 , we have that Pr 0 < ] = Pr 2 ? < 2 ]. Thus (using the fact that takes any speci c angle value with probability 0): Pr 0 <2 ? ] = 1 ? Pr 0 < ] 1 p r sin = 1? 2 arccos(?r cos ) 1 ? r2 cos2 = 21 ((2 ? ) ! r sin(2 ? ) arccos(?r cos(2 ? )) : +p 1 ? r2 cos2 (2 ? ) This is the same expression as in the statement of the lemma with replaced by 2 ? . We have thus shown the lemma for all values of . + Pr p2 s< ] = 21Z。

Approximation AlgorithmsQ. Suppose I need to solve an NP-hard problem. What should I do?4Load BalancingInput. m identical machines; n jobs, job j has processing time t j . Job j must run contiguously on one machine.A machine can process at most one job at a time.Def. Let J(i) be the subset of jobs assigned to machine i. The load of machine i is L i = Σj ∈J(i)t j .Def. The makespan is the maximum load on any machine L = max i L i .Load balancing. Assign each job to a machine to minimize makespan.Decision Version.Is the makespan bound by a number K?5Machine 2Machine 1a d fb c e gyesLoad Balancing on 2 MachinesClaim. Load balancing is hard even if only 2 machines.Pf. NUMBER-PARTITIONING ≤P LOAD-BALANCE .a df b c ge length of job fTime L0machine 1machine 2NP-complete6Greedy-scheduling algorithm.Consider n jobs in some fixed order.Assign job j to machine whose load is smallest so far.Implementation.O(n log m) using a priority queue.Load Balancing: Greedy SchedulingGreedy-Scheduling(m, n, t 1,t 2,…,t n ) {for i = 1 to m {L i ←0J(i)←φ}for j = 1 to n {i = argmin k { L k }J(i)←J(i)∪{j}L i ←L i + t j }return J(1), …, J(m)}jobs assigned to machine iload on machine imachine i has smallest loadassign job j to machine iupdate load of machine i7ρ-approximationAn algorithm for an optimization problem is a ρ-approximation if the solution found by the algorithm is always within a factor ρof the optimal solution.Minimization Problem: ρ= approximate-solution/optimal-solution Maximization Problem: ρ= optimal-solution/approximate-solution8Load Balancing: Greedy Scheduling AnalysisTheorem. [Graham, 1966]Greedy algorithm is a 2-approximation. First worst-case analysis of an approximation algorithm.Need to compare resulting solution with optimal makespan L*.Lemma 1. The optimal makespan L* ≥max j t j .Pf. Some machine must process the most time-consuming job. ▪Lemma 2. The optimal makespan Pf. The total processing time is Σj t j .One of m machines must do at least a 1/m fraction of total work. ▪L *≥1m tj j ∑.9Load Balancing: Greedy Scheduling AnalysisTheorem. Greedy algorithm is a 2-approximation.Pf. Consider max load L i of bottleneck machine i.Let j be last job scheduled on machine i.When job j assigned to machine i, i had smallest load. Its loadbefore assignment is L i -t j ⇒L i -t j ≤L k for all 1 ≤k ≤m.j0L = L iL i -t j machine i blue jobs scheduled before j10Load Balancing: Greedy Scheduling AnalysisTheorem. Greedy algorithm is a 2-approximation.Pf. Consider max load L i of bottleneck machine i.Let j be last job scheduled on machine i.When job j assigned to machine i, i had smallest load. Its loadbefore assignment is L i -t j ⇒L i -t j ≤L k for all 1 ≤k ≤m.Sum inequalities over all k and divide by m:Now ▪L i − t j ≤1m L kk ∑=1m t kk ∑≤L *L i = (L i −t j )≤ L *1 2 4 3 4 +t j ≤ L *{ ≤ 2L *.Lemma 2Lemma 111Load Balancing: Greedy Scheduling AnalysisQ. Is our analysis tight?A. Essentially yes.Ex: m machines, m(m-1) jobs length 1 jobs, one job of length mGreedy solution = 2m-1;machine 2 idlemachine 3 idlemachine 4 idlemachine 5 idlemachine 6 idlemachine 7 idlemachine 8 idlemachine 9 idlemachine 10 idlelist scheduling makespan = 19m = 1012Load Balancing: List Scheduling AnalysisQ. Is our analysis tight?A. Essentially yes.Ex: m machines, m(m-1) jobs length 1 jobs, one job of length m Greedy solution = 2m-1; Optimal makespan = m; ρ= 2-1/m.m = 10optimal makespan = 1013Load Balancing: LPT RuleLongest processing time (LPT). Sort n jobs in descending order of processing time, and then run Greedy scheduling algorithm.LPT-Greedy-Scheduling(m, n, t 1,t 2,…,t n ) {Sort jobs so that t 1 ≥t 2 ≥…≥t nfor i = 1 to m {L i ←0J(i)←φ}for j = 1 to n {i = argmin k L k J(i)←J(i)∪{j}L i ←L i + t j }return J(1), …, J(m)}jobs assigned to machine iload on machine imachine i has smallest loadassign job j to machine iupdate load of machine i14Load Balancing: LPT RuleObservation. If at most m jobs, then greedy-scheduling is optimal.Pf. Each job put on its own machine. ▪Lemma 3. If there are more than m jobs, L* ≥2t m+1.Pf.Consider first m+1 jobs t 1, …, t m+1.Since the t i 's are in descending order, each takes at least t m+1time. There are m+1 jobs and m machines, so by pigeonhole principle, atleast one machine gets two jobs. ▪Theorem. LPT rule is a 3/2 approximation algorithm.Pf. Same basic approach as for the first greedy scheduling.▪L i = (L i −t j )≤ L *1 2 4 3 4 +t j ≤ 12L *{ ≤ 32L *.Lemma 3( by observation, can assume number of jobs > m )15Load Balancing: LPT RuleQ. Is our 3/2 analysis tight?A. No.Theorem. [Graham, 1969]LPT rule is a 4/3-approximation.Pf. More sophisticated analysis of the same algorithm.Q. Is Graham's 4/3 analysis tight?A. Essentially yes.Ex: m machines, n = 2m+1 jobs, 2 jobs of length m+1, m+2, …, 2m-1 and three jobs of length m.Greedy solution = 4m-1; Optimal makespan = 3m; ρ= 4/3 -1/3m.11.6 LP Rounding: Weighted Vertex Cover17Weighted Vertex CoverWeighted vertex cover. Given an undirected graph G = (V, E) with vertex weights w i ≥0, find a minimum weight subset of nodes S such that every edge is incident to at least one vertex in S.36107A E H B D I C F J G 61610723910933total weight = 553218Weighted Vertex Cover: IP FormulationWeighted vertex cover. Given an undirected graph G = (V, E) with vertex weights w i ≥0, find a minimum weight subset of nodes S such that every edge is incident to at least one vertex in S.Integer programming formulation.Model inclusion of each vertex i using a 0/1 variable x i .Vertex covers in 1-1 correspondence with 0/1 assignments:S = {i ∈V : x i = 1}Objective function: minimize Σi w i x i .For each edge (i, j), must take either i or j: x i + x j ≥1.x i = 0if vertex i is not in vertex cover1if vertex i is in vertex cover19Weighted Vertex Cover: IP FormulationWeighted vertex cover. Integer programming formulation.Observation. If x* is optimal solution to (ILP), then S = {i ∈V : x*i = 1} is a minimum weight vertex cover.(ILP )min w i x ii ∈ V∑s. t.x i +x j ≥1(i ,j )∈Ex i ∈{0,1}i ∈V20Integer ProgrammingINTEGER-PROGRAMMING.Given integers a ij and b i , find integers x j that satisfy:Observation. Vertex cover formulation proves that integerprogramming is NP-hard.a ij x j j =1n ∑≥b i 1≤i ≤mx j ≥0 1≤j ≤nx j integral 1≤j ≤neven if all coefficients are 0/1 andat most two variables per inequalitymax c t x s. t.Ax ≥b x integral 21Linear ProgrammingLinear programming. Max/min linear objective function subject to linear inequalities.Input: integers c j , b i , a ij .Output: real numbers x j .Linear. No x 2, xy, arccos(x), x(1-x), etc.Simplex algorithm. [Dantzig 1947]Can solve LP in practice.Ellipsoid algorithm. [Khachian 1979]Can solve LP in poly-time.(P)max c j x j j =1n∑s. t.a ij x j j =1n ∑≥b i 1≤i ≤mx j ≥01≤j ≤n(P)max c t x s. t.Ax ≥b x ≥0LP Feasible RegionLP geometry in 2D.LP Optimal (2.5, 1.5)Max 3x 1+ 2x 2-x 1+ x 2< 1x 2x 13x 1+ x 2< 9132541 2 3 4 5 6 7x 1+ 3x 2< 723Weighted Vertex Cover: LP RelaxationWeighted vertex cover. Linear programming formulation.Observation. Optimal value of (LP) is ≤optimal value of (ILP).Pf. LP has fewer constraints.Note. LP is not equivalent to vertex cover. Q. How can solving LP help us find a small vertex cover?A. Solve LP and round fractional values.(LP )min w i x ii ∈ V∑s. t.x i +x j ≥1(i ,j )∈Ex i ≥0i ∈V½½½24Weighted Vertex CoverTheorem. If x* is optimal solution to (LP), then S = {i ∈V : x*i ≥½} is a vertex cover whose weight is at most twice the min possible weight.Pf. [S is a vertex cover]Consider an edge (i, j) ∈E.Since x*i + x*j ≥1, either x*i ≥½or x*j ≥½⇒(i, j) covered.Pf. [S has desired cost]Let S* be optimal vertex cover. Thenw i i ∈S *∑ ≥ w i x i *i ∈S ∑ ≥ 12wi i ∈S∑LP is a relaxation x*i ≥½Weighted Vertex CoverTheorem. 2-approximation algorithm for weighted vertex cover.Theorem. [Dinur-Safra 2001] If P ≠NP, then no ρ-approximationfor ρ< 1.3607, even with unit weights.10 √5 -21Open research problem. Close the gap.2511.8 Knapsack ProblemPolynomial Time Approximation SchemePTAS. (1 + ε)-approximation algorithm for any constant ε> 0.Load balancing. [Hochbaum-Shmoys 1987]Euclidean TSP. [Arora 1996]Consequence. PTAS produces arbitrarily high quality solution, but tradesoff time for accuracy.This section. PTAS for knapsack problem via rounding and scaling.2728Knapsack ProblemKnapsack problem.Given n objects and a "knapsack."Item i has value v i > 0 and weighs w i > 0. Knapsack can carry weight up to W.Goal: fill knapsack so as to maximize total value.Ex: { 3, 4 } has value 40.1Value 1822281Weight56627Item 13452W = 11we'll assume w i ≤W 29Knapsack is NP-CompleteKNAPSACK : Given a finite set X, nonnegative weights w i , nonnegative values v i , a weight limit W, and a target value V, is there a subset S ⊆X such that:SUBSET-SUM : Given a finite set X, nonnegative values u i , and an integer U, is there a subset S ⊆X whose elements sum to exactly U?Claim. SUBSET-SUM ≤P KNAPSACK .Pf. Given instance (u 1, …, u n , U) of SUBSET-SUM , create KNAPSACK instance:w i i ∈S∑≤Wv i i ∈S∑≥Vv i =w i =u i u i i ∈S∑≤UV =W =U u i i ∈S∑≥U30Knapsack Problem: Dynamic Programming 1Def. OPT(i, w) = max value subset of items 1,..., i with weight limit w. Case 1: OPT does not select item i.–OPT selects best of 1, …, i–1 using up to weight limit wCase 2: OPT selects item i.–new weight limit = w –w i–OPT selects best of 1, …, i–1 using up to weight limit w –w iRunning time. O(n W).W = weight limit.Not polynomial in input size!OPT (i ,w )=0if i =0OPT (i −1,w )if w i >wmax OPT (i −1,w ),v i +OPT (i −1,w −w i ){}otherwise31Knapsack Problem: Dynamic Programming IIDef. OPT(i, v) = min weight subset of items 1, …, i that yields value exactly v.Case 1: OPT does not select item i.–OPT selects best of 1, …, i-1 that achieves exactly value vCase 2: OPT selects item i.–consumes weight w i , new value needed = v –v i–OPT selects best of 1, …, i-1 that achieves exactly value vOPT (i ,v )=0if v =0∞if i =0, v >0OPT (i −1,v )if v i >vmin OPT (i −1,v ),w i +OPT (i −1,v −v i ){}otherwise32Knapsack: FPTASOPT (i ,v )=0if v =0∞if i =0, v >0OPT (i −1,v )if v i >vmin OPT (i −1,v ),w i +OPT (i −1,v −v i ){}otherwise1Value 3461Weight56127Item 13452W = 11012345678910111213141500x x x x x x x x x x x x x x x 1020304050i = 0 or v = 033Knapsack: FPTASOPT (i ,v )=0if v =0∞if i =0, v >0OPT (i −1,v )if v i >vmin OPT (i −1,v ),w i +OPT (i −1,v −v i ){}otherwise1Value 3461Weight56127Item 13452W = 11012345678910111213141500x x x x x x x x x x x x x x x 101x x x x x x x x x x x x x x 20304050i = 1 , v = …34Knapsack: FPTASOPT (i ,v )=0if v =0∞if i =0, v >0OPT (i −1,v )if v i >vmin OPT (i −1,v ),w i +OPT (i −1,v −v i ){}otherwise1Value 3461Weight56127Item 13452W = 11012345678910111213141500x x x x x x x x x x x x x x x 101x x x x x x x x x x x x x x 2013x x x x x x x x x x x x x304050i = 2 , v = (35)Knapsack: FPTASOPT (i ,v )=0if v =0∞if i =0, v >0OPT (i −1,v )if v i >vmin OPT (i −1,v ),w i +OPT (i −1,v −v i ){}otherwise1Value 3461Weight56127Item 13452W = 11012345678910111213141500x x x x x x x x x x x x x x x 101x x x x x x x x x x x x x x 2013x x x x x x x x x x x x x3013568x x x x x x x x x x 4050i = 3 , v = (36)Knapsack: FPTASOPT (i ,v )=0if v =0∞if i =0, v >0OPT (i −1,v )if v i >vmin OPT (i −1,v ),w i +OPT (i −1,v −v i ){}otherwise1Value 3461Weight 56127Item 13452W = 11012345678910111213141500x x x x x x x x x x x x x x x 101x x x x x x x x x x x x x x 2013x x x x x x x x x x x x x3013568x x x x x x x x x x 40135679111214x x x x x x50i = 4, v = …37Knapsack: FPTASOPT (i ,v )=0if v =0∞if i =0, v >0OPT (i −1,v )if v i >vmin OPT (i −1,v ),w i +OPT (i −1,v −v i ){}otherwise1Value 3461Weight 56127Item 13452W = 11012345678910111213141500x x x x x x x x x x x x x x x 101x x x x x x x x x x x x x x 2013x x x x x x x x x x x x x3013568x x x x x x x x x x 40135679111214x x x x x x5013567781012131416181921i = 5, v = (38)Knapsack Problem: Dynamic Programming IIDef. OPT(i, v) = min weight subset of items 1, …, i that yields value exactly v.Case 1: OPT does not select item i.–OPT selects best of 1, …, i-1 that achieves exactly value v Case 2: OPT selects item i.–consumes weight w i , new value needed = v –v i–OPT selects best of 1, …, i-1 that achieves exactly value vRunning time. O(n V*) = O(n 2 v max ).V* = optimal value = maximum v such that OPT(n, v) ≤W.Not polynomial in input size!OPT (i ,v )=0if v =0∞if i =0, v >0OPT (i −1,v )if v i >vmin OPT (i −1,v ),w i +OPT (i −1,v −v i ){}otherwiseV* ≤n v max39Knapsack: FPTASIntuition for approximation algorithm.Round all values up to lie in smaller range.Run dynamic programming algorithm on rounded instance.Return optimal items in rounded instance.W = 11original instance rounded instanceW = 111Value 1822281Weight 56627Item 13452934,221Value 17,810,01321,217,80027,343,1991Weight 565,956,34227Item 1345240Knapsack: FPTASKnapsack FPTAS. Round up all values: –v max = largest value in original instance–ε= precision parameter–θ= scaling factor = εv max / nObservation. Optimal solution to problems with or are equivalent.Intuition. close to v so optimal solution using is nearly optimal;small and integral so dynamic programming algorithm is fast.Running time. O(n 3/ ε).Dynamic program II running time is , where= =θθθii ii v v v v ˆ, ˆv v vv ˆ v O (n 2ˆ v max )= =εθnv v ˆmax max 41Knapsack: FPTASKnapsack FPTAS. Round up all values: Theorem. If S is solution found by our algorithm and S* is any other feasible solution of the original problem, then Pf. Let S* be any feasible solution satisfying weight constraint.v i i ∈S *∑≤v i i ∈S *∑≤v i i ∈S ∑≤(v i i ∈S ∑+θ)≤v i i ∈S ∑+ n θ≤(1+ε)v i i ∈S∑always round upsolve rounded instance optimallynever round up by more than θ(1+ε)v i ≥ v ii ∈S *∑i ∈S ∑|S| ≤n n θ= εv max , v max ≤Σi ∈S v i DP alg can take v maxθθ=i i v v。