算法设计与分析算法设计与分析 (13).ppt

1Chapter 12Local SearchSlides by Kevin Wayne.Copyright 2005 Pearson-Addison Wesley.All rights reserved.2Coping With NP-HardnessQ.Suppose I need to solve an NP-hard problem.What should I do?A.Theory says youre unlikely to find poly-time algorithm.Must sacrifice one of three desired features.nSolve problem to optimality.nSolve problem in polynomial time.nSolve arbitrary instances of the problem.12.1 Landscape of an Optimization Problem4Gradient Descent:Vertex CoverVERTEX-COVER.Given a graph G=(V,E),find a subset of nodes S of minimal cardinality such that for each u-v in E,either u or v(or both)are in S.Neighbor relation.S S if S can be obtained from S by adding or deleting a single node.Each vertex cover S has at most n neighbors.Gradient descent.Start with S=V.If there is a neighbor S that is a vertex cover and has lower cardinality,replace S with S.Remark.Algorithm terminates after at most n steps since each update decreases the size of the cover by one.5Gradient Descent:Vertex CoverLocal optimum.No neighbor is strictly better.optimum=center node onlylocal optimum=all other nodesoptimum=all nodes on left sidelocal optimum=all nodes on right sideoptimum=even nodeslocal optimum=omit every third node6Local SearchLocal search.Algorithm that explores the space of possible solutions in sequential fashion,moving from a current solution to a nearby one.Neighbor relation.Let S S be a neighbor relation for the problem.Gradient descent.Let S denote current solution.If there is a neighbor S of S with strictly lower cost,replace S with the neighbor whose cost is as small as possible.Otherwise,terminate the algorithm.A funnelA jagged funnel12.4 Maximum Cut8Maximum CutMaximum cut.Given an undirected graph G=(V,E)with positive integer edge weights we,find a node partition(A,B)such that the total weight of edges crossing the cut is maximized.Toy application.nn activities,m people.nEach person wants to participate in two of the activities.nSchedule each activity in the morning or afternoon to maximize number of people that can enjoy both activities.Real applications.Circuit layout,statistical physics.9Maximum CutSingle-flip neighborhood.Given a partition(A,B),move one node from A to B,or one from B to A if it improves the solution.Greedy algorithm.10Maximum Cut:Local Search AnalysisTheorem.Let(A,B)be a locally optimal partition and let(A*,B*)be optimal partition.Then w(A,B)e we w(A*,B*).Pf.nLocal optimality implies that for all u A:Adding up all these inequalities yields:nSimilarlynNow,each edge counted onceweights are nonnegative11Maximum Cut:Big Improvement FlipsLocal search.Within a factor of 2 for MAX-CUT,but not poly-time!Big-improvement-flip algorithm.Only choose a node which,when flipped,increases the cut value by at least Claim.Upon termination,big-improvement-flip algorithm returns a cut(A,B)with(2+)w(A,B)w(A*,B*).Pf idea.Add to each inequality in original proof.Claim.Big-improvement-flip algorithm terminates after O(-1 n log W)flips,where W=e we.nEach flip improves cut value by at least a factor of(1+/n).nAfter n/iterations the cut value improves by a factor of 2.nCut value can be doubled at most log W times.if x 1,(1+1/x)x 212Maximum Cut:ContextTheorem.Sahni-Gonzales 1976 There exists a-approximation algorithm for MAX-CUT.Theorem.Goemans-Williamson 1995 There exists an 0.878567-approximation algorithm for MAX-CUT.Theorem.Hstad 1997 Unless P=NP,no 16/17 approximation algorithm for MAX-CUT.0.94117612.7 Nash Equilibria14Multicast RoutingMulticast routing.Given a directed graph G=(V,E)with edge costsce 0,a source node s,and k agents located at terminal nodes t1,tk.Agent j must construct a path Pj from node s to its terminal tj.Fair share.If x agents use edge e,they each pay ce/x.outer2outermiddle41 pays5+15/2+1middle41outermiddlemiddleouter82 pays85/2+15+1st1vt24811515Nash EquilibriumBest response dynamics.Each agent is continually prepared to improve its solution in response to changes made by other agents.Nash equilibrium.Solution where no agent has an incentive to switch.Fundamental question.When do Nash equilibria exist?Ex:nTwo agents start with outer paths.nAgent 1 has no incentive to switch paths(since 4 5+1).nOnce this happens,agent 1 prefers middlepath(since 4 5/2+1).nBoth agents using middle path is a Nashequilibrium.st1vt24581116Nash Equilibrium and Local SearchLocal search algorithm.Each agent is continually prepared to improve its solution in response to changes made by other agents.Analogies.nNash equilibrium:local optimum.nBest response dynamics:local search algorithm.nUnilateral move by single agent:local neighborhood.Contrast.Best-response dynamics need not terminate since no single objective function is being optimized.17Socially OptimumSocial optimum.Minimizes total cost to all agent.Observation.In general,there can be many Nash equilibria.Even when its unique,it does not necessarily equal the social optimum.st1vt235511Social optimum=7Unique Nash equilibrium=8 stk1+Social optimum=1+Nash equilibrium A=1+Nash equilibrium B=kk agents18Price of StabilityPrice of stability.Ratio of best Nash equilibrium to social optimum.Fundamental question.What is price of stability?Ex:Price of stability=(log k).Social optimum.Everyone takes bottom paths.Unique Nash equilibrium.Everyone takes top paths.Price of stability.H(k)/(1+).st2t3tkt1.11/21/31/kt00001+1+1/2+1/k19Finding a Nash EquilibriumTheorem.The following algorithm terminates with a Nash equilibrium.Pf.Consider a set of paths P1,Pk.nLet xe denote the number of paths that use edge e.nLet(P1,Pk)=eE ce H(xe)be a potential function.nSince there are only finitely many sets of paths,it suffices to show that strictly decreases in each step.H(0)=0,20Finding a Nash EquilibriumPf.(continued)nConsider agent j switching from path Pj to path Pj.nAgent j switches becausen increases by n decreases by nThus,net change in is negative.21Bounding the Price of StabilityClaim.Let C(P1,Pk)denote the total cost of selecting paths P1,Pk.For any set of paths P1,Pk,we havePf.Let xe denote the number of paths containing edge e.nLet E+denote set of edges that belong to at least one of the paths.22Bounding the Price of StabilityTheorem.There is a Nash equilibrium for which the total cost to all agents exceeds that of the social optimum by at most a factor of H(k).Pf.nLet(P1*,Pk*)denote set of socially optimal paths.nRun best-response dynamics algorithm starting from P*.nSince is monotone decreasing (P1,Pk)(P1*,Pk*).previous claimapplied to Pprevious claimapplied to P*23SummaryExistence.Nash equilibria always exist for k-agent multicast routing with fair sharing.Price of stability.Best Nash equilibrium is never more than a factor of H(k)worse than the social optimum.Fundamental open problem.Find any Nash equilibria in poly-time.