Dependent Rounding in Bipartite Graphs Rajiv Gandhi

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 by Srini-vasan,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)capacitated 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.IntroductionV arious combinatorial optimization problems include hardcardinality constraints:e.g.,a broadcast server may be ableto 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 heregraphs 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 massive graphs[7], and hence there has been much renewed interest in generating (and studying the properties of)random graphs with a given degree sequence;see,e.g.,[10].However,since a graph is far more than its degree sequence,we ask:can we model addi-tional features of such graphs?Concretely,suppose empirical measurements show,e.g.,that vertices of degreeOur applications come about by combining the dependent rounding with various other ideas.The per-user guaranteesthat 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 knownapproaches.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 for each.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 currentset offloating edges.If,we are done.Otherwise,find(in linear time)a simple cycle or maximal path in thesubgraph,and partition the edge-set of into twomatchings 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 that(2) we may then substitute to see that(P1) holds.The base case where,is trivial.Assum-ing(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,equalsThis completes our sketch of the proof for(P1).Property(P3) can be proven by a similar,slightly more complicated,induc-tion.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 appro-priate 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 suc-cessful result of the study of such graphs has been the un-covering of the power-law behavior of the vertex-degrees ofmany such graphs(see,e.g.,[6]);hence,there has been much interest 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 de-gree 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 probabilityof 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 answer is no:the reader can verify that no such distribution(i.e.,ran-dom graph model)exists for the triangle with(and hence with).This ex-ample 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 num-ber,there are simple cases of non-bipartitegraphs where there is no space of random graphs which satisfies(A1)and(A2). (Consider two vertex-disjointtriangles with all six values being,and connect the two triangles by and edge whose value is.)Thus,we need to compromise–hopefully just a little–for general graphs.We show how to efficiently generate random graphs that preserve(A2),and relax(A1)to have with probability one that for each,its(random)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,.The binary variable iff request is satisfied at some time.Thefirst set of constraints ensurethat 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 to-tal 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-slots 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 par-Wp W p2pvp1vp2vp3vp4WpFigure 1.Subgraph of relevant to page whose,values are.ticular 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:implies EifotherwiseLemma3.2Let be the random variable that is iff is satisfied before in the rounded solution and is otherwise. Then,EProof:E EOPT.Proof:Since,E E. Using Lemma3.2,we get ER EQUEST C ONSOLIDATION page1234for down to do56if then78910else1112returnFigure2.Algorithm to obtain,where is.Note that for any two edgesand,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 re-quest satisfied in the LP solution at or before thefirst time in-stance 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 satis-fying exactly half fraction of after.Let be the cost of satisfying the last fraction of request.Letbe the cost of satisfying in the LP so-lution.Note that for a request,since we 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 ELemma3.6Consider any requests and,where isfirst such time instance after.If is the random variable denoting the cost of sat-isfying in the rounded solution then we have E.Proof:Since,we have E.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 below.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 thefirst two channels(pages broadcast in step)with a probability.E(5) Let be the last time instance that contributes towards the cost..Also,.Com-bining these facts with Equation(5),we get ETheorem3.9The above rounding scheme yields a-speed, -approximate solution.Proof In steps1-4,we broadcast at most two pages per time instance as argued in Theorem3.7.In steps5-6,we broad-cast at most one page at any time instance since the fractional value of edges incident on any vertex in is at most one. Thus steps1-6ensure a-speed solution.The proof of opti-mality follows from Lemmas 3.5and3.8.4.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 orienta-tion 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 CAPACI-TATED VERTEX COVER problem is that of computing a min-imum 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 problem we can only cover a subset of at most edges incident to node .Clearly,the problem is NP-hard since it generalizes 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.Ori-enting 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 prob-lem 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 Algo-rithm Threshold and Round produces a-approximate solu-tion 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 op-timal LP solution.4.2.Assignment CostsWe can generalize this problem in the following way:in addition to having weights on the vertices,we have an assign-ment cost for assigning an edge to vertex.In the IP, the only change that we make is to addto the objective function.We now solve the resulting relax-ation of the IP to the natural LP and run Algorithm Threshold and Round by choosing in the same way.Suppose that in the optimal solution of the linear program, the optimum cost is which represents the optimum fractional cost due to the weighted sum of chosen vertices and the assignment cost of edges.Theorem4.4Algorithm Threshold and Roundfinds a solu-tion such that the expected assignment cost is at most.Thus this gives a2approximation for the problem with vertex weights and assignment costs(since the total cost is at most).5.Scheduling on Unrelated Parallel MachinesGiven a set of jobs,a set of machines,and(for each and)the time required to process job on machine,the problem is to schedule the jobs on the ma-chines so as to minimize the makespan.Lenstra,Shmoys and Tardos[15]give a-approximate solution for this problem; their result is as follows.Define a linear program LP with a variable for each machine and job;is iff job is scheduled on machine.Let.LP asks for a feasible solution for the following system of lin-ear constraints:(i)for all;(ii)for all;(iii)for all;and(iv)for all.It is easy to see that the given instance has makespan at most only if LP has a feasible solution; thus,the infimum of all such“feasible”is a lower bound on the optimal makespan.We will throughout let be a lower bound on this infimum which is close to the infimum with high precision;such a can be computed efficiently via a bisection search.Then,the work of[15]presents a round-ing method to produce a schedule of makespan at most, which is a-approximation.Since then,it has been an open question if we can do better in polynomial time.In the spirit of offering per-user guarantees,we can also ask the following question.Are there constants and for which we can construct a randomized schedule that has makespan at most with probability,and where each given job gets scheduled with probability at least?(The al-gorithm of[15]provides and.)As pointed out by Chandra Chekuri to us,this is indeed possible forand[4].It is not clear how to extend this approach to achieve and;we show such a result here.Let be as above,and let the vector denote an op-timal solution to LP.We need the following notion of -weighted dependent rounding.Briefly,we will work with a star graph,whose center is some machine and whose leaves are the jobs.We have a dependent round-ing instance 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 a path;let the values be the probabilis-tically changing values as in Section2.We now define to be 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.Ifand,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 ma-chine 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 induced on vertex and its neighbors.Perform-weighted de-pendent 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.Chuzhoyand J.Naor.Covering Problems with Hard Ca-pacities.Proc.IEEE Symposium on Foundations of Com-puter 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.Capacitated Ver-tex Covering with Applications.Proc.ACM-SIAM Sym-posium 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.。