Question? Leave a message!
I Agree to Thesis Scientist
Terms and Conditions
Not a member?
Sign Up Now
Register a Free Account
I Agree to Thesis Scientist
Terms and Conditions
Sign up At Thesis Scientist
Done, your profile is created.Finish your profile by filling in the following fields
Earn Money,Free Notes
Password sent to your Email Id, Please Check your Mail
Updating Cart........ Please Wait........
exact exponential algorithms
exact exponential algorithms
comments powered by Disqus.
INTRACTABILITY III special cases: trees ‣ special cases: planarity ‣ approximation algorithms ‣ exact exponential algorithms ‣ Lecture slides by Kevin Wayne Copyright © 2005 PearsonAddison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on Nov 24, 2014, 8:24 AMCoping with NPcompleteness Q. Suppose I need to solve an NPhard problem. What should I do A. Sacrifice one of three desired features. i. Solve arbitrary instances of the problem. ii. Solve problem to optimality. iii. Solve problem in polynomial time. Coping strategies. i. Design algorithms for special cases of the problem. ii. Design approximation algorithms or heuristics. iii. Design algorithms that may take exponential time. 2INTRACTABILITY III special cases: trees ‣ special cases: planarity ‣ approximation algorithms ‣ exact exponential algorithms ‣ SECTION 10.2Independent set on trees Independent set on trees. Given a tree, find a maximum cardinality subset of nodes such that no two are adjacent. Fact. A tree has at least one node that is a leaf (degree = 1). Key observation. If node v is a leaf, there exists a max cardinality independent set containing v. u Pf. exchange argument v Consider a max cardinality independent set S. If v ∈ S, we're done. Let (u, v) be some edge. if u ∉ S and v ∉ S, then S ∪ v is independent ⇒ S not maximum if u ∈ S and v ∉ S, then S ∪ v − u is independent ▪ 4Independent set on trees: greedy algorithm Theorem. The following greedy algorithm finds a max cardinality independent set in forests (and hence trees). Pf. Correctness follows from the previous key observation. ▪ INDEPENDENTSETINAFOREST (F) S ← ∅. WHILE (F has at least 1 edge) e ← (u, v) such that v is a leaf. S ← S ∪ v . delete u and v and all incident edges F ← F – u, v . RETURN S ∪ nodes remaining in F . Remark. Can implement in O(n) time by considering nodes in postorder. 5Weighted independent set on trees Weighted independent set on trees. Given a tree and node weights w 0, v find an independent set S that maximizes Σ w . v ∈ S v Dynamic programming solution. Root tree at some node, say r. OPT (u) = max weight independent set of subtree rooted at u, in containing u. OPT (u) = max weight independent set of subtree rooted at u, out not containing u. r OPT = max OPT (r), OPT (r) . in out OPT (u) = w + OPT (v) OPT (u) = w + ∑ OPT (v) ∑ in u out in u out v∈ children(u) v∈ children(u) u OPT (u) = max OPT (v), OPT (v) OPT (u) = ∑ max OPT (v), OPT (v) ∑ out in out out in out v w x v∈ children(u) v∈ children(u) children(u) = v, w, x € € 6Weighted independent set on trees: dynamic programming algorithm Theorem. The dynamic programming algorithm finds a max weighted independent set in a tree in O(n) time. can also find independent set itself (not just value) WEIGHTEDINDEPENDENTSETINATREE (T) Root the tree T at a node r. S ← ∅. FOREACH (node u of T in postorder) IF (u is a leaf) ensures a node is visited M u = w . in u after all its children M u = 0. out ELSE M u = w + Σ M v. in u v ∈ children(u) out M u = Σ max M v, M v . out v ∈ children(u) in out RETURN max M r, M r . in out 7NPhard problems on trees: context Independent set on trees. Tractable because we can find a node that breaks the communication among the subproblems in different subtrees. u Lineartime on trees. VERTEXCOVER, DOMINATINGSET, GRAPHISOMORPHISM, ... 8INTRACTABILITY III special cases: trees ‣ special cases: planarity ‣ approximation algorithms ‣ exact exponential algorithms ‣ SECTION 23.1Planarity Def. A graph is planar if it can be embedded in the plane in such a way that no two edges cross. K is nonplanar K is nonplanar 5 3,3 planar Applications. VLSI circuit design, computer graphics, ... 10Planarity testing Theorem. HopcroftTarjan 1974 There exists an O(n) time algorithm to determine whether a graph is planar. simple planar graph has at ≤ 3n edges Efficient Planarity Testing JOHN HOPCROFT AND ROBERT TAR JAN Cornell University, Ithaca, New York ABSTRACT. This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by Auslander and Parter and correctly formulated by Goldstein. The algorithm uses depthfirst search and has O(V) time and space bounds, where V is the number of vertices in G. An ALGOS implementation of the algorithm successfully tested graphs with as many as 900 vertices in less than 12 seconds. KEY WORDS AND PHRASES: algorithm, complexity, depthfirst search, embedding, genus, graph, palm tree, planarity, spanning tree CR CATEGORIES: 3.24, 5.25, 5.32 1. Introduction Graph theory is an endless source of easily stated yet very hard problems. Many of these problems require algorithms; given a graph, one may ask if the graph has a certain prop erty, and an algorithm is to provide the answer. Since graphs are widely used as models of real phenomena, it is important to discover ecient algorithms for answering graph theoretic questions. This paper presents an efficient algorithm to determine whether a graph G can be embedded (without any crossing edges) in the plane. 11 The planarity algorithm may be viewed as an iterative version of a recursive method originally proposed by Auslander and Patter 1 and correctly formulated by Goldstein 2. The algorithm uses depthfirst search to order the calculations and thereby achieve efficiency. Depthfirst search, or backtracking, has been widely used for finding solu tions to problems in combinatorial theory and artificial intelligence 3, 4. Recently this type of search has been used to construct efficient algorithms for solving several problems in graph theory, including finding biconnected components 5, 6, finding triconnected components 7, 81, finding strongly connected components 61, finding dominators 9, and determining whether a directed graph is reducible 10, 11. In order to analyze the theoretical efficiency of the planarity algorithm, a random ac cess computer model is used. Data storage and retrieval, arithmetic operations, compari sons, and logical operations are assumed to require fixed times. A memory cell is allowed to hold integers whose absolute value is bounded by kV for some constant k, where V is the number of vertices in the problem graph. Cook 12 describes an exact computer model along these lines. If f and g are functions of x, we say "f(x) is O(g(x))" if, for some constants kI and k2, If(x) I ki I g(x) I + k2 for all x. Within this framework, the planarity algorithm has 0 (V) time and space bounds and is optimal to within a constant factor. The practical efficiency of the algorithm was measured by implementing it in ALGOL Copyright () 1974, Association for Computing Machinery, Inc. General permission to republish, but not for profit, all or part of this material is granted provided that ACM's copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery. This research was supported by the Hertz Foundation, the NSF, and the Office of Naval Research under grants N0O014AOl120057 and N0001467A00770021. Authors' present addresses: J. Hopcroft, Department of Computer Science, Cornell University, Ithaca, NY 14850; R. Tarjan, Department of Electrical Engineering, University of California, Berkeley, CA 94720. Journal of the Association for Computing Machinery, Vol. 21, No. 4, October 1974, pp. 549568. Polynomial time detour Graph minor theorem. RobertsonSeymour 1980s Pf of theorem. Tour de force. 3 Corollary. There exist an O(n ) algorithm to determine if a graph can be embedded in the torus in such a way that no two edges cross. more than 2↑2↑2↑(n/2) Mind boggling fact 1. The proof is highly nonconstructive Mind boggling fact 2. The constant of proportionality is enormous “ Unfortunately, for any instance G = (V, E) that one could ﬁt into the known 70 universe, one would easily prefer n to even constant time, if that constant had to be one of Robertson and Seymour's. ” — David Johnson Theorem. There exists an explicit O(n) algorithm. 3 Practice. LEDA implementation guarantees O(n ). 12Problems on planar graphs Fact 0. Many graph problems can be solved faster in planar graphs. Ex. Shortest paths, max flow, MST, matchings, … Fact 1. Some NPcomplete problems become tractable in planar graphs. Ex. MAXCUT, ISING, CLIQUE, GRAPHISOMORPHISM, 4COLOR, ... Fact 2. Other NPcomplete problems become easier in planar graphs. Ex. INDEPENDENTSET, VERTEXCOVER, TSP, STEINERTREE, ... An O(nlogn)AlgorithmforMaximum stFlow inaDirectedPlanarGraph GLENCORABORRADAILEANDPHILIPKLEIN Brown University, Providence, Rhode Island Abstract. Wegivetheﬁrstcorrect O(nlogn)algorithmforﬁndingamaximumstﬂowinadirected planargraph.Afterapreprocessingstepthatconsistsinﬁndingsinglesourceshortestpathdistances inthedual,thealgorithmconsistsofrepeatedlysaturatingtheleftmostresidual stot path. Categories and Subject Descriptors: F.2.2 Analysis of Algorithms and Problem Complexity: NonnumericalAlgorithmsandProblems GeneralTerms:Algorithms AdditionalKeyWordsandPhrases:Maximumﬂow,planargraphs ACMReferenceFormat: Borradaile, G. and Klein, P. 2009. An O(nlogn) algorithm for maximum stﬂow in a directed 13 planar graph. J. ACM 56, 2, Article 9 (April 2009), 30 pages. DOI = 10.1145/1502793.1502798 http://doi.acm.org/10.1145/1502793.1502798 9 1. Introduction Informally,themaximumstﬂowproblemisasfollows:givenagraphwithpositive arccapacities,andgivenasourcevertex s andasinkvertex t,thegoalistoﬁnda waytoroutethemaximumamountofasinglecommodityalongstot pathsinsuch awaythattheamountofcommoditypassingthroughanarcisatmostthecapacity of the arc. In the minimum stcut problem, the goal is to ﬁnd a minimumcapacity set of arcs such that each stot path includes at least one arc in the set. Formal deﬁnitionswillbegiveninSection4.5. The history of maximumﬂow and minimumcut problems Schrijver 2002 is tied closely to planar graphs. During the height of the cold war, the United States A preliminary version of this article was published in Proceedings of the 17th Annual ACMSIAM Symposium on Discrete Algorithms (SODA’06),ACM,NewYork,2006,pp.524–533. G.BorradailewassupportedbyNSERCPGSD,RowlandLloydCST,Kanellakis,aBrownUniversity DissertationFellowship,andNSFGrantCCF0635089.P.KleinwassupportedbyNSFGrantCCF 0635089. Authors’ addresses: Department of Computer Science, Brown University, Providence, RI 02912, email:glencora;kleincs.brown.edu. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for proﬁt or commercial advantageandthatcopiesshowthisnoticeontheﬁrstpageorinitialscreenofadisplayalongwiththe full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstractingwithcreditispermitted.Tocopyotherwise,torepublish,topostonservers,toredistribute tolists,ortouseanycomponentofthisworkinotherworksrequirespriorspeciﬁcpermissionand/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, NewYork,NY101210701USA,fax+1(212)8690481,orpermissionsacm.org. ⃝ C 2009ACM00045411/2009/04ART95.00 DOI10.1145/1502793.1502798 http://doi.acm.org/10.1145/1502793.1502798 JournaloftheACM,Vol.56,No.2,Article9,Publicationdate:April2009.Planar graph 3colorability PLANAR3COLOR. Given a planar graph, can it be colored using 3 colors so that no two adjacent nodes have the same color 14Planar map 3colorability PLANARMAP3COLOR. Given a planar map, can it be colored using 3 colors so that no two adjacent regions have the same color yes instance 15Planar map 3colorability PLANARMAP3COLOR. Given a planar map, can it be colored using 3 colors so that no two adjacent regions have the same color no instance 16Planar graph and map 3colorability reduce to one another Theorem. PLANAR3COLOR ≣ PLANARMAP3COLOR. P Pf sketch. Nodes correspond to regions. Two nodes are adjacent iff they share a nontrivial border. e.g., not Arizona and Colorado 17Planar 3colorability is NPcomplete Theorem. PLANAR3COLOR ∈ NPcomplete. Pf. Easy to see that PLANAR3COLOR ∈ NP. We show 3COLOR ≤ PLANAR3COLOR. P Given 3COLOR instance G, we construct an instance of PLANAR3COLOR that is 3colorable iff G is 3colorable. 18Planar 3colorability is NPcomplete Lemma. W is a planar graph such that: In any 3coloring of W, opposite corners have the same color. Any assignment of colors to the corners in which opposite corners have the same color extends to a 3coloring of W. planar gadget W 19Planar 3colorability is NPcomplete Lemma. W is a planar graph such that: In any 3coloring of W, opposite corners have the same color. Any assignment of colors to the corners in which opposite corners have the same color extends to a 3coloring of W. Pf. The only 3colorings (modulo permutations) of W are shown below. ▪ planar gadget W 20Planar 3colorability is NPcomplete Construction. Given instance G of 3COLOR, draw G in plane, letting edges cross. Form planar G' by replacing each edge crossing with planar gadget W. Lemma. G is 3colorable iff G' is 3colorable. In any 3coloring of W, a ≠ a' and b ≠ b'. If a ≠ a' and b ≠ b' then can extend to a 3coloring of W. b b a' a a' a b' a crossing gadget W b' 21Planar 3colorability is NPcomplete Construction. Given instance G of 3COLOR, draw G in plane, letting edges cross. Form planar G' by replacing each edge crossing with planar gadget W. Lemma. G is 3colorable iff G' is 3colorable. In any 3coloring of W, a ≠ a' and b ≠ b'. If a ≠ a' and b ≠ b' then can extend to a 3coloring of W. a W W W a' a' a multiple crossings concatenate copies of gadget W 22Planar map kcolorability Theorem. AppelHaken 1976 Every planar map is 4colorable. Resolved centuryold open problem. Used 50 days of computer time to deal with many special cases. First major theorem to be proved using computer. BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY Volume 82, Number 5, September 1976 RESEARCH ANNOUNCEMENTS 1 EVERY PLANAR MAP IS FOUR COLORABLE BY K. APPEL AND W. HAKEN Communicated by Robert Fossum, July 26, 1976 The following theorem is proved. THEOREM . Every planar map can be colored with at most four colors. As has become standard, the four color map problem will be considered in the dual sense as the problem of whether the vertices of every planar graph (without loops) can be colored with at most four colors in such a way that no pair of vertices which lie on a common edge have the same color. The restriction to triangulations with all vertices of degree at least five is a consequence of the Remarks. work of A. B. Kempe. Over the past 100 years, a number of authors including A. B. Kempe, G. D. Birkhoff, and H. Heesch have developed a theory of 4 AppelHaken yields O(n ) algorithm to 4color of a planar map. reducibility to attack the problem. Simultaneously, a theory of unavoidable sets has been developed and the fusion of these has led to the proof. 2 Best known: O(n ) to 4color; O(n) to 5color. A configuration is a subgraph of a planar triangulation consisting of a circuit (called the ring) and its interior. A configuration is called reducible if it can be shown by certain standard methods that it cannot be immersed in a Determining whether 3 colors suffice is NPcomplete. minimal counterexample to the four color conjecture. (For details, see 3 or 4.) A set of configurations is called unavoidable if every planar triangulation contains some member of the set. From the definitions, it is immediate that 23 the four color theorem is proved if an unavoidable set of reducible configurations is provided. The most efficient known method of producing unavoidable sets of con figurations is called the method of discharging. This method treats the planar triangulation as an electrical network with charge assigned to the vertices. Euler's formula is used to show that the initial charge distribution, giving positive charge to vertices of degree five and negative charge to vertices of degree greater than six, has positive total charge. Next, the initial charge is redistributed in a manner which obeys the principle of conservation of charge. This means that some vertices must end up with positive charge. Such an algorithm can be made sufficiently sophisticated that a finite list of neighborhoods of all possible vertices of ultimately positive charge can be described in detail. AMS (MOS) subject classifications (1970). Primary 05C15. 1 This work appears in full in two papers, Every planar map is four colorable; part I, Discharging, by K. Appel and W. Haken and part II, Reducibility, by K. Appel, W. Haken, and J. Koch. These papers have been submitted to another journal. Copyright © 1976, American Mathematical Society 711 Polynomialtime special cases NPhard problems Trees. VERTEXCOVER, INDEPENDENTSET, DOMINATINGSET, GRAPHISOMORPHISM, ... Bipartite graphs. VERTEXCOVER, 2COLOR, ... Chordal graphs. KCOLOR, CLIQUE, INDEPENDENTSET, ... Planar graphs. MAXCUT, ISING, CLIQUE, GRAPHISOMORPHISM, 4COLOR, ... Bounded treewidth. 3COLOR, HAMCYCLE, INDEPENDENTSET, GRAPHISOMORPHISM. Small integers. KNAPSACK, PARTITION, SUBSETSUM, ... 24INTRACTABILITY III special cases: trees ‣ special cases: planarity ‣ approximation algorithms ‣ exact exponential algorithms ‣ SECTION 11.8Approximation algorithms ρapproximation algorithm. Guaranteed to run in polytime. Guaranteed to solve arbitrary instances of the problem. Guaranteed to find solution within ratio ρ of true optimum. Ex. Given a graph G, the greedy algorithms finds a VERTEXCOVER that uses ≤ 2 OPT(G) vertices in O(m + n) time. Challenge. Need to prove a solution's value is close to optimum value, without even knowing what optimum value is 26Knapsack problem Knapsack problem. Given n objects and a knapsack. we assume w ≤ W for each i Item i has value v 0 and weighs w 0. i i i Knapsack has weight limit W. Goal: fill knapsack so as to maximize total value. Ex: 3, 4 has value 40. item value weight 1 1 1 2 6 2 3 18 5 4 22 6 5 28 7 original instance (W = 11) 27Knapsack is NPcomplete KNAPSACK. Given a set X, weights w ≥ 0, values v ≥ 0, a weight limit W, and a i i target value V, is there a subset S ⊆ X such that: w ≤ W ∑ i i∈S v ≥ V ∑ i i∈S SUBSETSUM. Given a set X, values u ≥ 0, and an integer U, is there a subset S i ⊆ X whose elements sum to exactly U € Theorem. SUBSETSUM ≤ KNAPSACK. P Pf. Given instance (u , …, u , U) of SUBSETSUM, create KNAPSACK instance: 1 n v =w =u u ≤ U ∑ i i i i i∈S V =W =U u ≥ U ∑ i i∈S 28 € Knapsack problem: dynamic programming I Def. 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 w. Case 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 . i ⎧ 0 if i = 0 ⎪ OPT(i, w) = OPT(i−1, w) if w w ⎨ i ⎪ max OPT(i−1, w), v + OPT(i−1, w− w ) otherwise ⎩ i i Theorem. Computes the optimal value in O(n W) time. € Not polynomial in input size. Polynomial in input size if weights are small integers. 29Knapsack problem: dynamic programming II Def. OPT(i, v) = min weight of a knapsack for which we can obtain a solution of value ≥ v using a subset of items 1,..., i. Note. Optimal value is the largest value v such that OPT(i, v) ≤ W. Case 1. OPT does not select item i. OPT selects best of 1, …, i – 1 that achieves value v. Case 2. OPT selects item i. Consumes weight w , need to achieve value v – v . i i OPT selects best of 1, …, i – 1 that achieves value v – v . i 0B7 v 0 OPT(i,v)= B7 i=0M/ v 0 min OPT(i 1,v),w +OPT(i 1,v v )Qi2`rBb2 i i 30Knapsack problem: dynamic programming II Theorem. Dynamic programming algorithm II computes the optimal value 2 in O(n v ) time, where v is the maximum of any value. max max Pf. The optimal value V ≤ n v . max There is one subproblem for each item and for each value v ≤ V. It takes O(1) time per subproblem. ▪ Remark 1. Not polynomial in input size Remark 2. Polynomial time if values are small integers. 31Knapsack problem: polynomialtime approximation scheme Intuition for approximation algorithm. Round all values up to lie in smaller range. Run dynamic programming algorithm II on rounded instance. Return optimal items in rounded instance. item value weight item value weight 1 934221 1 1 1 1 2 5956342 2 2 6 2 3 17810013 5 3 18 5 4 21217800 6 4 22 6 5 27343199 7 5 28 7 original instance (W = 11) rounded instance (W = 11) 32Knapsack problem: polynomialtime approximation scheme Round up all values: v = largest value in original instance. ⎡ ⎤ ⎡ ⎤ max v v i i ˆ v = θ, v = i i ⎢ ⎥ ⎢ ⎥ ε = precision parameter. ⎢ ⎥ ⎢ ⎥ θ θ θ = scaling factor = ε v / n. max € Observation. Optimal solutions to problem with are equivalent to v v ˆ optimal solutions to problem with . Intuition. v close to v so optimal solution using is nearly optimal; v € small and integral so dynamic programming algorithm II is fast. € v ˆ € € € 33Knapsack problem: polynomialtime approximation scheme ⎡ ⎤ v i v = θ Round up all values: i ⎢ ⎥ ⎢ ⎥ θ € Theorem. If S is solution found by rounding algorithm and S is any other feasible solution, then (1+ε) v ≥ v ∑ ∑ i i i∈ S i∈ S Pf. Let S be any feasible solution satisfying weight constraint. € always round up v ≤ v ∑ v v v v ≤≤≤≤ ∑ v v v v ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ i i i i i i i i i i i∈ S i∈ S i i i i∈ ∈ ∈ ∈ S S S S i i i i∈ ∈ ∈ ∈ S S S S ≤ v ≤≤≤≤ ∑ v v v v ∑ ∑ ∑ ∑ solve rounded instance optimally i i i i i i∈ S i i i i∈ ∈ ∈ ∈ S S S S ≤ (v + θ) never round up by more than θ ≤≤≤≤ ∑ ( ( ( (v v v v + + + + θθθθ) ) ) ) ∑ ∑ ∑ ∑ i i i i i i∈ S i i i i∈ ∈ ∈ ∈ S S S S ≤ v + nθ ≤≤≤≤ ∑ v v v v + + + + n n n nθθθθ ∑ ∑ ∑ ∑ S ≤ n i i i i i DP alg can take v max i∈ S i i i i∈ ∈ ∈ ∈ S S S S ≤ (1+ε) v ≤≤≤≤ ( ( ( (1 1 1 1+ + + +εεεε) ) ) )∑ v v v v ∑ ∑ ∑ ∑ i i i i i nθ = ε v , v ≤ Σ v max max i ∈ S i i∈ S i i i i∈ ∈ ∈ ∈ S S S S 34 € € € € € Knapsack problem: polynomialtime approximation scheme Theorem. For any ε 0, the rounding algorithm computes a feasible solution 3 whose value is within a (1 + ε) factor of the optimum in O(n / ε) time. Pf. We have already proved the accuracy bound. 2 Dynamic program II running time is , wher O(n v ˆ ) e max ⎡ ⎤ ⎡ ⎤ v n max ˆ v = = max ⎢ ⎥ ⎢ ⎥ € ⎢ ⎥ ⎢ ⎥ θ ε PTAS. (1 + ε)approximation algorithm for any constant ε 0. € Produces arbitrarily high quality solution. Trades off accuracy for time. But such algorithms are unlikely to exist for certain problems... 35Inapproximability MAX3SAT. Given a 3SAT instance Φ, find an assignment that satisfies the maximum number of clauses. Theorem. KarloffZwick 1997 There exists a ⅞approximation algorithm. Theorem. Håstad 2001 Unless P = NP, there does not exist a ρ approximation for any ρ ⅞. A ApproximationAlgorithm forMAX3SAT HowardKarloff UriZwick A ApproximationAlgorithm forMAX3SAT SomeOptimalInapproximabilityResults HowardKarloff UriZwick ˚ JOHANHASTAD Abstract that the performance ratio of his algorithm is actually 2/3. Royal Institute of Technology, Stockholm, Sweden Many years passed beforeYannakakis37 obtained a 3/4 approximation algorithm for the problem. Goemans and We describe a randomized approximation algorithm which Williamson 17 then obtained a different and somewhat Abstract. We prove optimal, up to an arbitrary ϵ0, inapproximability results for MaxEkSat for takesaninstanceofMAX3SATasinput. Iftheinstance—a Abstract that the performance ratio of his algorithm is actually 2/3. k≥ 3, maximizing the number of satisﬁed linear equations in an overdetermined system of linear simpler 3/4approximation algorithm. Their algorithm is collectionofclauseseachoflengthatmostthree—issatisﬁ Many years passed beforeYannakakis37 obtained a 3/4 equations modulo a prime p and Set Splitting. As a consequence of these results we get improved basedonalinearprogrammingrelaxationoftheproblem. able,thentheexpectedweightoftheassignmentfoundisat approximation algorithm for the problem. Goemans and We describe a randomized approximation algorithm which lowerboundsfortheefﬁcientapproximabilityofmanyoptimizationproblemsstudiedpreviously.In least ofoptimal. Weprovidestrongevidence(butnota Williamson 17 then obtained a different and somewhat particular,forMaxE2Sat,MaxCut,MaxdiCut,andVertexcover. In a major breakthrough, Goemans and Williamson 18 takesaninstanceofMAX3SATasinput. Iftheinstance—a proof)thatthealgorithmperformsequallywellonarbitrary simpler 3/4approximation algorithm. Their algorithm is obtained a 0.878approximation algorithm for MAX CUT collectionofclauseseachoflengthatmostthree—issatisﬁ CategoriesandSubjectDescriptors:F2.2AnalysisofAlgorithmsandProblemComplexity:Non MAX3SATinstances. numericalAlgorithmsandProblems basedonalinearprogrammingrelaxationoftheproblem. and MAX 2SAT, the version of MAX SAT in which each able,thentheexpectedweightoftheassignmentfoundisat GeneralTerms:Theory clause is of size at most two. Goemans and Williamson least ofoptimal. Weprovidestrongevidence(butnota Our algorithm uses semideﬁnite programming and may be In a major breakthrough, Goemans and Williamson 18 used semideﬁnite rAdditional elaxationKseoyfW thords eseand proPhrases: blems. Inapproximability Feige and ,linearequations,maxsat,NPhardoptimiza proof)thatthealgorithmperformsequallywellonarbitrary seenasasequeltotheMAXCUTalgorithmofGoemansand obtained a 0.878approximation algorithm for MAX CUT tionproblems,probabilisticallycheckableproofs Goemans 15 then obtained a 0.931approximation algo MAX3SATinstances. WilliamsonandtheMAX2SATalgorithmofFeigeandGoe and MAX 2SAT, the version of MAX SAT in which each rithmforMAX2SAT.Using theMAX2SATalgorithmsof mans. Thoughthealgorithmitself is fairlysimple,its anal clause is of size at most two. Goemans and Williamson Our algorithm uses semideﬁnite programming and may be 36 Goemans and Williamson or of Feige and Goemans, slight ysis is quite complicated as it involves the computation of used semideﬁnite relaxationsof these problems. Feige and seenasasequeltotheMAXCUTalgorithmofGoemansand 1. Introduction improvements in the performance ratio for general MAX volumesofsphericaltetrahedraG.oemans 15 then obtained a 0.931approximation algo WilliamsonandtheMAX2SATalgorithmofFeigeandGoe SAT can bemade.Man Goem ynatural ansandoptimization Williamson problems 18 obtainare edNPhard,whichimpliesthattheyareprob rithmforMAX2SAT.Using theMAX2SATalgorithmsof mans. Thoughthealgorithmitself is fairlysimple,its anal Ha˚stad has recently shown that, assuming ,no ably hard to solve exactly in the worst case. In practice, however, it is sufﬁcient a 0.758 bound for MAX SAT. Asano 4 (following 5) Goemans and Williamson or of Feige and Goemans, slight ysis is quite complicated as it involves the computation of polynomialtime algorithm for MAX 3SAT can achieve a togetreasonablygoodsolutionsforall(orevenmost)instances.Inthispaper,we slightlyimprovedthisboundto0.770. improvements in the performance ratio for general MAX volumesofsphericaltetrahedra. performance ratio exceeding , even when restricted to study the existence of polynomial time approximation algorithms for some of the SAT can bemade. Goemansand Williamson 18 obtained While semideﬁnite relaxations yield a huge improvement satisﬁableinstancesoftheproblem. Ouralgorithmisthere Ha˚stad has recently shown that, assuming ,no basicNPcompleteproblems.Foramaximizationproblemwesaythatanalgorithm a 0.758 bound for MAX SAT. Asano 4 (following 5) forMAX2SAT(from0.75to0.931),theygive,sofar,only foreoptimalin thissense. polynomialtime algorithm for MAX 3SAT can achieve a isaCapproximationalgorithmifit,foreachinstance,producesansolutionwhose slightlyimprovedthisboundto0.770. a minor improvementfor MAX SAT (from 0.75 to 0.770). objective value is at least OPT/C where OPT is the global optimum. A similar performance ratio exceeding , even when restricted to We also describe a method of obtaining direct semideﬁnite The reason for this seems to be that the semideﬁnite relax While semideﬁnite relaxations yield a huge improvement deﬁnitionappliestominimizationproblems. satisﬁableinstancesoftheproblem. Ouralgorithmisthere relaxations of any constraint satisfaction problem of the ationsusedtillnowdonotdirectlyhandleclausesoflength forMAX2SAT(from0.75to0.931),theygive,sofar,oAnlfundamental y questionis,foragivenNPcompleteproblem,forwhatvalueof foreoptimalin thissense. form MAXCSP , where is a ﬁnite family of Boolean threeormore. C can we hope for a polynomial time Capproximation algorithm. Posed in this a minor improvementfor MAX SAT (from 0.75 to 0.770). functions. Ourrelaxationsarethestrongestpossiblewithin We also describe a method of obtaining direct semideﬁnite generality, this is a large research area with many positive and negative results. In The reason for this seems to be that the semideﬁnite relax An attempt to squeeze more from the MAX 2SAT algo anaturalclassofsemideﬁniterelaxations. relaxations of any constraint satisfaction problem of the this paper, we concentrate on negative results, that is, results of the form that for ationsusedtillnowdonotdirectlyhandleclausesoflength rithm of Feige and Goemans 15 was made by Trevisan, form MAXCSP , where is a ﬁnite family of Boolean someC1acertainproblemcannotbeapproximatedwithinCinpolynomialtime. threeormore. Sorkin, Sudan and Williamson 34. They used an op functions. Ourrelaxationsarethestrongestpossiblewithin These results are invariably based on plausible complexity theoretic assumptions, timal gadget, a concept formalized by Bellare, Goldre An attempt to squeeze more from the MAX 2SAT algo anaturalclassofsemideﬁniterelaxations. theweakestpossiblebeingNP≠ PsinceifNP=P,allconsideredproblemscanbe 1 Introduction ich and Sudan 7, to reduce MAX 3SAT (the problem rithm of Feige and Goemans 15 was made by Trevisan, solvedexactlyinpolynomialtime. in which each clause has length at most three) to MAX Sorkin, Sudan and Williamson 34. They used an op ThemostbasicNPcompleteproblemissatisﬁabilityofCNFformulasandprob MAXSATisacentralproblemin theoreticalcomputersci 2SAT, thereby obtaining a 0.801approximation algorithm timal gadget, a concept formalized by Bellare, Goldre ably the most used variant of this is 3SAT where each clause contains at most 3 1 Introduction ence. AsitisNPhardand,infact,MAXSNPcomplete(Pa for MAX 3SAT. Trevisan 33 recently obtained a 0.826 ich and Sudan 7, to reduce MAX 3SAT (the problem padimitriouandYannakakis30),muchattentionhasbeen approximation algorithm for satisﬁable instances of MAX in which each clause has length at most three) to MAX An earlier version of this paper appeared in Proceedings of the 29th Annual ACM Symposium on devoted to approximatingit. The ﬁrst approximationalgo 3SAT,anda0.8approximationalgorithmfor satisﬁablein MAXSATisacentralproblemin theoreticalcomputersci 2SAT, thereby obtaining a 0.801approximation algorithm Theory of Computing(ElPaso,Tex.,May4–6).ACM,NewYork,1997,pp.1–10. rithm forMAX SAT was proposedby Johnson 23. John stancesofMAXSAT. ence. AsitisNPhardand,infact,MAXSNPcomplete(Pa for MAX 3SAT. Trevisan 33 recently obtained a 0.826 Author’saddress:DepartmentofNumericalAnalysisandComputerScience,RoyalInstituteofTech sonshowedthattheperformanceratioofhisalgorithmisat padimitriouandYannakakis30),muchattentionhasbeen approximation algorithm for satisﬁable instances ofnology MAX ,S10044Stockholm,Sweden,email:johanhnada.kth.se. In anothermajorbreakthrough,followinga long line of re least . Chen, Friesen and Zheng 12 recently showed devoted to approximatingit. The ﬁrst approximationalgo Permissiontomakedigital/hardcopyofpartorallofthisworkforpersonalorclassroomuseisgranted 3SAT,anda0.8approximationalgorithmfor satisﬁablein searchbymanyauthors16,3,2,8,7,Has ˚ tad20recently without fee provided that the copies are not made or distributed for proﬁt or commercial advantage, rithm forMAX SAT was proposedby Johnson 23. John stancesofMAXSAT. CollegeofComputing,GeorgiaInstituteofTechnology,Atlanta,Geor showed that MAX E3SAT, the version of the MAX SAT thecopyrightnotice,thetitleofthepublication,anditsdateappear,andnoticeisgiventhatcopying sonshowedthattheperformancergiataio30332 ofhi0280, salgo Ur.Sit.h Am . Riesseat arch supported in part by NSF grant CCR probleminwhicheachclauseisoflengthexactlythree,can In anothermajorbreakthrough,followinga long lineisoby f re permission of the Association for Computing Machinery (ACM), Inc. To copy otherwise, to 9319106. Emailaddress: howardcc.gatech.edu. least . Chen, Friesen and Zheng 12 recently showed not be approximated in polynomial time to within a ratio republish,topostonservers,ortoredistributetolists,requirespriorspeciﬁcpermissionand/orafee. searchbymanyauthors16,3,2,8,7,Has ˚ tad20recently Department of Computer Science, TelAviv University, TelAviv ⃝ C 2001ACM00045411/01/070007985.00 greater than 7/8, unless . Has ˚ tad shows, in fact, CollegeofComputing,GeorgiaInstitut69978, eofTecIhsrnaoello.gTyhi ,A stw lan ortka,wGaeo sdone r whislehtohiw sed author that waM s viA siX tingEI3 CS SIAaT n,dthe version of the MAX SAT UCBerkeley. Emailaddress: zwickmath.tau.ac.il. that no polynomialtimealgorithmcan havea performance gia 303320280, U.S.A. Research supported in part by NSF grant CCR probleminwhicheachclauseisoflengthexactlythree,can JournaloftheACM,Vol.48,No.4,July2001,pp.798–859. 9319106. Emailaddress: howardcc.gatech.edu. not be approximated in polynomial time to within a ratio Department of Computer Science, TelAviv University, TelAviv greater than 7/8, unless . Has ˚ tad shows, in fact, 69978,Israel. Thisworkwasdonewhile this authorwas visiting ICSIand 1 UCBerkeley. Emailaddress: zwickmath.tau.ac.il. that no polynomialtimealgorithmcan havea performance 1INTRACTABILITY III special cases: trees ‣ special cases: planarity ‣ approximation algorithms ‣ exact exponential algorithms ‣Exact exponential algorithms Complexity theory deals with worstcase behavior. Instances you want to solve may be "easy." “ For every polynomialtime algorithm you have, there is an exponential algorithm that I would rather run.” — Alan Perlis 38Exact algorithms for 3satisﬁability Brute force. Given a 3SAT instance with n variables and m clauses, n the bruteforce algorithm takes O((m + n) 2 ) time. Pf. n There are 2 possible truth assignments to the n variables. We can evaluate a truth assignment in O(m + n) time. ▪ 39Exact algorithms for 3satisﬁability A recursive framework. A 3SAT formula Φ is either empty or the disjunction of a clause (ℓ ∨ℓ ∨ℓ) and a 3SAT formula Φ' with one fewer clause. 1 2 3 = Φ (ℓ ∨ ℓ ∨ ℓ) ∧ Φ' 1 2 3 = (ℓ ∧ Φ') ∨ (ℓ ∧ Φ') ∨ (ℓ ∧ Φ') 1 2 3 = (Φ' ℓ = true) ∨ (Φ' ℓ = true) ∨ (Φ' ℓ = true) 1 2 3 Notation. Φ x = true is the simplification of Φ by setting x to true. Ex. Φ = (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z) ∧ (w ∨ y ∨ ¬z) ∧ (¬x ∨ y ∨ z). Φ' = (x ∨ ¬y ∨ z) ∧ (w ∨ y ∨ ¬z) ∧ (¬x ∨ y ∨ z). (Φ' x = true) = (w ∨ y ∨ ¬z) ∧ (y ∨ z). each clause has ≤ 3 literals 40Exact algorithms for 3satisﬁability A recursive framework. A 3SAT formula Φ is either empty or the disjunction of a clause (ℓ ∨ℓ ∨ℓ) and a 3SAT formula Φ' with one fewer clause. 1 2 3 3SAT (Φ) IF Φ is empty RETURN true. (ℓ ∨ ℓ ∨ ℓ) ∧ Φ' ← Φ. 1 2 3 IF 3SAT(Φ' ℓ = true) RETURN true. 1 IF 3SAT(Φ' ℓ = true) RETURN true. 2 IF 3SAT(Φ' ℓ = true) RETURN true. 3 RETURN false. n Theorem. The bruteforce 3SAT algorithm takes O(poly(n) 3 ) time. Pf. T(n) ≤ 3T(n – 1) + poly(n). ▪ 41Exact algorithms for 3satisﬁability Key observation. The cases are not mutually exclusive. Every satisfiable assignment containing clause (ℓ ∨ℓ ∨ℓ) must fall into one of 3 classes: 1 2 3 ℓ is true. 1 ℓ is false; ℓ is true. 1 2 ℓ is false; ℓ is false; ℓ is true. 1 2 3 3SAT (Φ) IF Φ is empty RETURN true. (ℓ ∨ ℓ ∨ ℓ) ∧ Φ' ← Φ. 1 2 3 IF 3SAT(Φ' ℓ = true ) RETURN true. 1 IF 3SAT(Φ' ℓ = false, ℓ = true) RETURN true. 1 2 IF 3SAT(Φ' ℓ = false, ℓ = false, ℓ = true) RETURN true. 1 2 3 RETURN false. 42Exact algorithms for 3satisﬁability n Theorem. The bruteforce algorithm takes O(1.84 ) time. Pf. T(n) ≤ T(n – 1) + T(n – 2) + T(n – 3) + O(m + n). ▪ 3 2 largest root of r = r + r + 1 3SAT (Φ) IF Φ is empty RETURN true. (ℓ ∨ ℓ ∨ ℓ) ∧ Φ' ← Φ. 1 2 3 IF 3SAT(Φ' ℓ = true ) RETURN true. 1 IF 3SAT(Φ' ℓ = false, ℓ = true) RETURN true. 1 2 IF 3SAT(Φ' ℓ = false, ℓ = false, ℓ = true) RETURN true. 1 2 3 RETURN false. 43Exact algorithms for 3satisﬁability n Theorem. There exists a O(1.33334 ) deterministic algorithm for 3SAT. AFullDerandomizationofScho¨ning’s kSAT Algorithm Robin A. Moser and Dominik Scheder Institute for Theoretical Computer Science Department of Computer Science ETH Zu ¨rich, 8092 Zu ¨rich, Switzerland robin.moser, dominik.schederinf.ethz.ch August 25, 2010 Abstract Scho¨ning 7 presents a simple randomizedalgorithmforkSAT with running time n O(a poly(n)) for a =2(k−1)/k. We give a deterministic version of this algorithm k k n running in time O((a + ϵ) poly(n)), where ϵ 0 can be made arbitrarily small. k 1Introduction In 1999, Uwe Sch¨oning 7 gave an extremely simple randomized algorithm for kSAT. Ten years on, the fastest algorithms for kSAT are only slightly faster than his, and far more complicated. His algorithm works as follows: Let F be a (≤ k)CNF formula over n variables. Start with a random truth assignment. If this doesnotsatisfy F,pickan arbitrary unsatisﬁed clause C.From C,pickaliteraluniformlyatrandom,andchange the truth value of its underlying variable, thus satisfying C.Repeatthisreassignment step O(n)times. If F is satisﬁable, this ﬁnds a satisfying assignment with probability at least " n k 44 . 2(k−1) ∗ n ∗ n By repetition, this gives a randomized O (1.334 )algorithmfor3SAT,an O (1.5 )for ∗ 4SAT, and so on (we useO to suppresspolynomial factors inn). Shortly after Scho¨ning published his algorithm, Dantsin, Goerdt, Hirsch, Kannan, Kleinberg, Papadimitriou, Raghavan and Scho¨ning 2 (henceforth Dantsin et al. for the sake of brevity) came up with a deterministic algorithm that can be seen as an attempt to derandomize Scho¨ning’s ∗ n algorithm. We say attempt because its running time is O ((2k/(k+1)) ), which is ex ∗ n ponentially slower than Sch¨oning’s. For example, this gives an O (1.5 )algorithmfor ∗ n 3SAT and O (1.6 )for4SAT.Subsequentpapershaveimproveduponthisrunning time, mainly focusing on 3SAT: Dantsin et al. already improve the running time for n n n 3SAT to O(1.481 ), Brueggemann and Kern 1 to O(1.473 ), Scheder 6 to O(1.465 ), ∗ n andKutzkov andScheder 4 toO (1.439 ). All improvements suﬀerfrom two drawbacks: First, they fall short of achieving the running time of Scho¨ning’s randomized algorithm, and second, they are all fairly complicated. In this paper, wegivearathersimpledeter ministic algorithm with a running time that comes arbitrarily close to Scho¨ning’s, thus completely derandomizing his algorithm. We also show how to derandomize Sch¨oning’s algorithm forconstraintsatisfaction problems,whichareageneralizationofSAT,allowing more than two truth values. 1 arXiv:1008.4067v1 cs.DS 24 Aug 2010Exact algorithms for satisﬁability DPPL algorithm. Highlyeffective backtracking procedure. Splitting rule: assign truth value to literal; solve both possibilities. Unit propagation: clause contains only a single unassigned literal. Pure literal elimination: if literal appears only negated or unnegated. A Computing Procedure for Quantification Theory III. Splitting Rule. Let the given formula F be put in A Machine Program for RTIiN Dvs the form TheoremProvingt Rensselaer Polytechnic Institute, Hartford Division, East Windsor Hill, Conn. (A Vp) (BV/5) R AND HILARY PUTNAM' Martin Davis, George Logemann, and where A, B, and R are free of p. Then F is inconsistent if Princeton University, Princeton, New Jersey Donald Loveland and only if A R and B R are both inconsistent. JUSTIFICATION OF RULE III. For 1 p = 0, F = A R ; The hope that mathematical methods employed in the investigation of formal Institute of Mathematical Sciences, New York University logic would lead to purely computational methods for obtaining mathematical forp = 1, F = B R. theorems goes back to Leibniz and has been revived by Peano around the turn The forms of Rule III are interchangeable; Mthough of the century and by Hilbert's school in the 1920. Hilbert, noting that all of theoretically they are equivalent, in actual applications classical mathematics could be formalized within quantification theory, declared The programming of a proof procedure is discussed in that the problem of finding an algorithm for determining whether or not a given each has certain desirable features. We used Rule III be connection with trial runs and possible improvements. formula of quantification theory is valid was the central problem of mathe cause of the fact that Rule III can easily increase the matical logic. And indeed, at one time it seemed as if investigations of this "de In 1 is set forth an algorithm for proving theorems of mlmber and the lengths of the clauses in the expression cision" problem were on the verge of success. However, it was shown by Church quantification theory which is an improvement in certain and by Turing that such an algorithm can not exist. This result led to consider rather quickly after several applications. This is prohibi able pessimism regarding the possibility of using modern digital computers in respects over previously available algorithms such as that tive in a computer if ones fast access storage is limited. deciding significant mathematical questions. However, recently there has been of 2. The present paper deals with the programming of Also, it was observed that after performing Rule III, a revival of interest in the whole question. Specifically, it has been realized that while no decision procedure exists for quantification theory there are many proof the algorithm of 1 for the New York University, In many duplicated and thus redundant clauses were present,. procedures availablethat is, uniform procedures which will ultimately locate stitute of Mathematical Sciences' IBM 704 computer, Some success was obtained by causing the machine to sys a proof for any formulai of quantification theory which is valid but which will with some modifications in the algorithm suggested by tematically eliminate the redundancy; but the problem of usually involve seeking "forever" in the Case of a formula which is not valid and that some of these proof procedures could well turn out to be feasible for this work, with the results obtained using the completed total length increasing rapidly still remained when more use with modern computing machinery. algorithm. Familiarity with 1 is assumed throughout. complicated problems were attempted. Also use of Rule Hao Wang 9 and P. C. Gilmore 3 have each produced wordng programs which employ proof procedures in quantification theory. Gilmore's program III can seldom yield new oneliterM clauses, whereas use Changes in the Algorithm and Programming employs a form of a basic theorem of mathematical logic due to Herbrand, and of Rule III often will. Wang's makes use of a formulation of quantification theory related to those Techniques Used In programming Rule III, we used auxiliary tape studied by Gentzen. However, both programs encounter decisive difficulties 45 with any but the simplest formulas of quantification theory, in connection with The algorithm of 1 consists of two interlocking parts. storage. The rest of the testing for consistency is carried methods of doing propositional calculus. Wang's program, because of its use of The first part, called the QFlGenerator, generates (from out using only fast access storage. When the "Splitting Gentzenlike methods, involves exponentiation on the total number of truth the formula whose proof is being attempted) a growing Rule" is used one of the two formulas resulting is placed functional connectives, whereas Gilmore's program, using normal forms, in volves exponentiation on the number of clauses present. Both methods are su propositional calculus formula in conjunctive normal form, on tape. Tape memory records are organized in tbe cafe perior in many cases to truth table methods which involve exponentiation on the the "quantifierfree lines." The second part, the Processor, terial stackofplates scheme: the last record written is Received September, 1959. This research was supported by the United States Air tests, at regular stages in its "growth," the consistency of the first to be read. Force through the Air Force Office of Scientific Research of the Air Research and Develop ment Command, under Contract No. AF 49(638)527. Reproduction in whole or in part is this propositional calculus formula. An inconsistent set In the program written for the IBN 704, the matrix and permitted for any purpose of the United States Government. of quantifierfree lines constitutes a proof of the original conjunction of quantifierfree lines are coded into cross 201 formula. referenced associated (or linked) memory tables by the The algorithm of 1 used in testing for consistency QFLGenerator and then analyzed by the Processor. In particular, the QFLGenerator is programmed to read in proceeded by successive elimination of atomic formulas, first eliminating oneliteral clauses (oneliterM clause rule), the matrix M in suitably coded Polish (i.e., "parenthesis free") form. The conversion to a quantifierfree matrix in and then atomic formulas all of whose occurrences were positive or all of whose occurrences were negative (affirma conjunctive normal form requires, of course, a certain tivenegative rule). Finally, the remaining atomic formulas amount of pencil work on the formula, which could have were to have been eliminated by the rule: been done by the computer. In doing this, we departed III. Rule for Eliminating Atomic Formulas. Let the from 1, by not using prenex normal form. The steps are: given formula F be put into the form (1) Write all truthfunctional connectives in terms of , 6, V. (A V p) (B V ) R (2) Move all 's inward successively (using de Morgan laws) until they either are cancelled (with another ,,) or where A, B, and R are free of p. (This can be done acting on an atomic formula. simply by grouping together the clauses containing p and (3) Now, replace existential quantifiers by function "factoring out" occurrences of p to obtain A, grouping symbols (cf. 1, p. 205), drop universal quantifiers, and the clauses containing and "factoring out" to obtain place in conjunctive normal form. A simple onetoone B, and grouping the remaining clauses to obtain R.) Then assembler was written to perform the final translation of F is inconsistent if and only if (A V B) R is inconsistent. the matrix M into octal numbers. After programming the algorithm using this form of It will be recalled that the generation of quantifierfree Rule III, it was decided to replace it by the following rule: lines is accomplished by successive substitutions of "con stants" for the variables in the matrLx M. In the program t The research reported in this document has been sponsored by the Mathematical Sciences Directorate, Air Force Office of Scientific Research, under Contract No. AF 49(638)777. As in 1, I stands for "truth", and 0 for "falsehood". 394 Communications of the ACM Exact algorithms for satisﬁability Chaff. Stateoftheart SAT solver. Solves realworld SAT instances with 10K variable. Developed at Princeton by undergrads. Chaff: Engineering an Efficient SAT Solver Matthew W. Moskewicz Conor F. Madigan Ying Zhao, Lintao Zhang, Sharad Malik Department of EECS Department of EECS Department of Electrical Engineering UC Berkeley MIT Princeton University moskewczalumni.princeton.edu cmadiganmit.edu yingzhao, lintaoz, sharadee.princeton.edu Many publicly available SAT solvers (e.g. GRASP 8, ABSTRACT POSIT 5, SATO 13, relsat 2, WalkSAT 9) have been Boolean Satisfiability is probably the most studied of developed, most employing some combination of two main combinatorial optimization/search problems. Significant effort strategies: the DavisPutnam (DP) backtrack search and heuristic has been devoted to trying to provide practical solutions to this local search. Heuristic local search techniques are not problem for problem instances encountered in a range of guaranteed to be complete (i.e. they are not guaranteed to find a applications in Electronic Design Automation (EDA), as well as satisfying assignment if one exists or prove unsatisfiability); as a in Artificial Intelligence (AI). This study has culminated in the result, complete SAT solvers (including ours) are based almost development of several SAT packages, both proprietary and in exclusively on the DP search algorithm. the public domain (e.g. GRASP, SATO) which find significant use in both research and industry. Most existing complete solvers 1.1 Problem Specification are variants of the DavisPutnam (DP) search algorithm. In this Most solvers operate on problems for which f is specified in paper we describe the development of a new complete solver, conjunctive normal form (CNF). This form consists of the Chaff, which achieves significant performance gains through logical AND of one or more clauses, which consist of the logical careful engineering of all aspects of the search – especially a OR of one or more literals. The literal comprises the particularly efficient implementation of Boolean constraint fundamental logical unit in the problem, being merely an propagation (BCP) and a novel low overhead decision strategy. instance of a variable or its complement. (In this paper, Chaff has been able to obtain one to two orders of magnitude complement is represented by ¬.) All Boolean functions can be 46 performance improvement on difficult SAT benchmarks in described in the CNF format. The advantage of CNF is that in comparison with other solvers (DP or otherwise), including this form, for f to be satisfied (sat), each individual clause must GRASP and SATO. be sat. Categories and Subject Descriptors 1.2 Basic DavisPutnam Backtrack Search J6 ComputerAided Engineering: ComputerAided Design. We start with a quick review of the basic DavisPutnam backtrack search. This is described in the following pseudocode General Terms fragment: Algorithms, Verification. while (true) Keywords if (decide()) // if no unassigned vars Boolean satisfiability, design verification. return(satisifiable); while (bcp()) 1. Introduction if (resolveConflict()) return(not satisfiable); The Boolean Satisfiability (SAT) problem consists of determining a satisfying variable assignment, V, for a Boolean function, f, or determining that no such V exists. SAT is one of the central NPcomplete problems. In addition, SAT lies at the bool resolveConflict() core of many practical application domains including EDA (e.g. d = most recent decision not ‘tried both automatic test generation 10 and logic synthesis 6) and AI ways’; (e.g. automatic theorem proving). As a result, the subject of if (d == NULL) // no such d was found practical SAT solvers has received considerable research return false; attention, and numerous solver algorithms have been proposed and implemented. flip the value of d; mark d as tried both ways; undo any invalidated implications; return true; The operation of decide() is to select a variable that is not currently assigned, and give it a value. This variable assignment is referred to as a decision. As each new decision is made, a record of that decision is pushed onto the decision stack. Exact algorithms for TSP and Hamilton cycle Theorem. The bruteforce algorithm for TSP (or HAMCYCLE) takes O(n) time. Pf. There are ½ (n – 1) tours. Computing the length of a tour takes O(n) time. ▪ n Note. The function n grows exponentially faster than 2 . 40 12 2 = 1099511627776 10 . 48 40 = 815915283247897734345611269596115894272000000000 10 . 47Exact algorithms for TSP and Hamilton cycle 2 n Theorem. Bellman 1962, HeldKarp 1962 There exists a O(n 2 ) time algorithm for TSP (and HAMILTONCYCLE). Dynamic Programming Treatment of the Travelling Salesman Problem RICHARD ELLMAN RAND Corporation, Santa Monica, California Introdction The wellknown travelling salesman problem is the following: "A salesman is required ,o visit once and only once each of n different cities starting from a base city, and returning to this city. What path minimizes the total distance travelled by the salesman" The problem has been treated by a number of different people using a variety of techniques; el. Dantzig, Fulkerson, Johnson 1, where a combination of ingemtity and linear programming is used, and Miller, Tucker and Zemlin 2, whose experiments using an allinteger program of Gomory did not produce results i cases with ten cities although some success was achieved in eases of simply four cities. The purpose of this note is to show that this problem can easily be formulated in dynamic programming terms 3, and resolved computa tionally for up to 17 cities. For larger numbers, the method presented below, combined with various simple manipulations, may be used to obtain quick approximate solutions. Results of this nature were independently obtained by M. Held and R. M. Karp, who are in the process of publishing some extensions and computational results. Dynamic Programming Formulation Consider the problem as a multistage decision problem. With no loss in gen erality, since the tour is a round trip, fix the origin at some city, say 0. Suppose that at a certain stage of an optimal tour starting at 0 one has reached a city 48 i and there remain k cities jl, j, • • • , jk to be visited before returning to 0. Then it is clear that, the tour being optimal, the path from i through jl ,j2, • • • ,jk in some order and then to 0 must be of minimum length; for, if not the entire tour could not be optimal, since its total length could be reduced by choosing a shorter path from i through jl, j2, • • • , jk to 0. Therefore, let us define f(i; j, j2, " • • , jz) = length of a path of minimum length from i to 0 which passes once and only once through each of the re (1) maining k unvisited cities jl, j2, • • • , fl • Thus, if we obtuin f(0; jl, j..,, • • • , j), and a path which has this length, the problem has been solved. Received March, 1961; revised July, 1961. 61 Exact algorithms for TSP and Hamilton cycle 2 n Theorem. Bellman 1962, HeldKarp 1962 There exists a O(n 2 ) time algorithm for TSP (and HAMILTONCYCLE). Pf. dynamic programming Define c(s, v, X) = cost of cheapest path between s and v that visits every node in X exactly once (and uses only nodes in X). Observe OPT = min c(s,v,V)+ c(v,s). v= s n There are n 2 subproblems and they satisfy the recurrence: c(s,v)B7 X=2 c(s,v,X)= min c(s,u,X\v)+c(u,v)B7 X 2. u X\s,v The values c(s, v, X) can be computed increasing order of the cardinality of X. ▪ 49Exact algorithms for Hamilton cycle n Theorem. Björklund 2010 There exists a O(1.657 ) time randomized algorithm for HAMILTONCYCLE. 2010 IE 2010 IE 2010 IEE E EE E E 51st 51st 51st Annua Annua Annual l l Sym Sym Symposi posi posium um um on Founda on Founda on Foundat t ti i ions of C ons of C ons of Com om omput put pute e er Sc r Sc r Sci i ie e enc nc nce e e 2010 IE 2010 IE 2010 IEE E EE E E 51st 51st 51st Annua Annua Annual l l Sym Sym Symposi posi posium um um on Founda on Founda on Foundat t ti i ions of C ons of C ons of Com om omput put pute e er Sc r Sc r Sci i ie e enc nc nce e e DeterminantSumsforUndirectedHamiltonicity DeterminantSumsforUndirectedHamiltonicity Andreas Bjorklund ¨ Andreas Bjorklund ¨ Department of Computer Science Department of Computer Science Lund University Lund University Lund, Sweden Lund, Sweden Email: andreas.bjorklundyahoo.se Email: andreas.bjorklundyahoo.se Abstract—We present a Monte Carlo algorithm for Hamil Theorem 1: There is a Monte Carlo algorithm detecting Abstract—We present a Monte Carlo algorithm for Hamil Theorem 1: There is a Monte Carlo algorithm detecting tonicity detection in an vertex undirected graph running in whether an undirected graph on vertices is Hamiltonian tonicity detection in an vertex undirected graph running in ∗ whether an undirected graph on vertices is Hamiltonian " (1.657 ) time. To the best of our knowledge, this is the ∗ ∗ " (1.657 ) time. To the best oforour notkno running wledge, in this ( (1is.657 the ) time, with no false positives ∗ or not running in ( (1.657 ) time, with no false positives ﬁrst superpolynomial improvement on the worst case runtime ﬁrst superpolynomial improvement on the worst case runtime and false negatives with probability exponentially small in ∗ for the problem since the " (2 ) bound established for TSP and false negatives with probability exponentially small in ∗ for the problem since the " (2 ) bound established for TSP . almost ﬁfty years ago (Bellman 1962, Held and Karp 1962). . almost ﬁfty years ago (Bellman 1962, Held and Karp 1962). It answers in part the ﬁrst open problem in Woeginger’s 2003 For graphs having an induced subgraph with many dis It answers in part the ﬁrst open problem in Woeginger’s 2003 For graphs having an induced subgraph with many dis survey on exact algorithms for NPhard problems. connected components, most notably bipartite graphs, we survey on exact algorithms for NPhard problems. ∗ connected components, most notably bipartite graphs, we For bipartite graphs, we improve the bound to " (1.414 ) ∗ For bipartite graphs, we imprget ovean theebound ven stronger to " (1bound. .414 ) get an even stronger bound. time. Both the bipartite and the general algorithm can be time. Both the bipartite and the general algorithm can be Theorem 2: There is a Monte Carlo algorithm detecting implemented to use space polynomial in . Theorem 2: There is a Monte Carlo algorithm detecting implemented to use space polynomial in . whether an undirected graph on vertices with a given We combine several recently resurrected ideas to get the whether an undirected graph on vertices with a given We combine several recently resurrected ideas to get the results. Our main technical contribution is a new reduction independent set of size ' is Hamiltonian or not running in results. Our main technical contribution is a new reduction independent set of size ' is Hamiltonian or not running in ∗ −" inspired by the algebraic sieving method for Path (Koutis ( (2 ) time, with no false positives and false negatives ∗ −" inspired by the algebraic sieving method for Path (Koutis ( (2 ) time, with no false positives and false negatives ICALP 2008, Williams IPL 2009). We introduce the Labeled ICALP 2008, Williams IPL 2009). We introduce the Labeled with probability exponentially small in . with probability exponentially small in . Cycle Cover Sum in which we are set to count weighted arc Cycle Cover Sum in which we are set to count weighted arc We also note that our algorithm can be used to solve labeled cycle covers over a ﬁnite ﬁeld of characteristic two. We We also note that our algorithm can be used to solve labeled cycle covers over a ﬁnite ﬁeld of characteristic two. We TSP with integer weights via selfreducibility at the cost reduce Hamiltonicity to Labeled Cycle Cover Sum and apply TSP with integer weights via selfreducibility at the cost reduce Hamiltonicity to Labeled Cycle Cover Sum and apply the determinant summation technique for Exact Set Covers of a runtime blowup by roughly a factor of the sum of all the determinant summation technique for Exact Set Covers of a runtime blowup by roughly a factor of the sum of all (Bjorklund ¨ STACS 2010) to evaluate it. edges’ weights. (Bjorklund ¨ STACS 2010) to evaluate it. edges’ weights. Theorem 3: There is a Monte Carlo algorithm ﬁnding the Theorem 3: There is a Monte Carlo algorithm ﬁnding the I. INTRODUCTION I. INTRODUCTION weight of the lightest TSP tour in a positive integer edge weight of the lightest TSP tour in a positive integer edge ∗ An undirected graph =(",) on vertices is said weightedgraphonverticesin( (01.657 )time,where0 ∗ An undirected graph =(",) on vertices is said 50 weightedgraphonverticesin( (01.657 )time,where0 to be Hamiltonian if it has a Hamiltonian cycle, a vertex isthesumofallweights,witherrorprobabilityexponentially to be Hamiltonian if it has a Hamiltonian cycle, a vertex isthesumofallweights,witherrorprobabilityexponentially order ( , ,⋅⋅⋅, ) such that ∈ for all '. small in . 0 1 −1 " "+1 order ( , ,⋅⋅⋅, ) such that ∈ for all '. small in . 0 1 −1 " "+1 The indices are enumerated modulo requiring also that The indices are enumerated modulo requiring also that A. Previous Work is an edge. The problem of detecting if a graph is A. Previous Work −1 0 is an edge. The problem of detecting if a graph is −1 0 Hamiltonianiscalledthe HAMILTONICITYproblemandwas Bellman’s 3, 4 and Held and Karp’s 11 algorithm Hamiltonianiscalledthe HAMILTONICITYproblemandwas Bellman’s 3, 4 and Held and Karp’s 11 algorithm one of the ﬁrst identiﬁed as NPhard. It is on Karp’s original for TSP in an vertex complete graph =(",) with one of the ﬁrst identiﬁed as NPhard. It is on Karp’s original for TSP in an vertex complete graph =(",) with + list 16, but is perhaps best known as a special case of the edge weights ℓ : →ℝ is based on deﬁning 0 (2) for + , list 16, but is perhaps best known as a special case of the edge weights ℓ : →ℝ is based on deﬁning 0 (2) for , Traveling Salesman Problem (TSP). The TSP asks for a 3,4∈ 2 ⊆ " as the weight of the lightest path from 3 to 4 Traveling Salesman Problem (TSP). The TSP asks for a 3,4∈ 2 ⊆ " as the weight of the lightest path from 3 to 4 tour visiting every vertex of an edge weighted graph exactly in the induced graph 2 visiting all vertices in 2 exactly tour visiting every vertex of an edge weighted graph exactly in the induced graph 2 visiting all vertices in 2 exactly once that minimizes the total weight. Bellman 3, 4 and once. This quantity obeys the simple recursion once that minimizes the total weight. Bellman 3, 4 and once. This quantity obeys the simple recursion independently Held and Karp 11 described in the early independently Held and Karp 11 described in the early min 0 (2∖4)+ℓ(54):∣2∣ 2 ∈'∖, , min 0 (2∖4)+ℓ(54):∣2∣ 2 1960’s a dynamic programming recurrence that solves the 0 (2)= ∈'∖, , , 1960’s a dynamic programming recurrence that solves the 0 (2)= ℓ(34): , ∣2∣=2 2 ℓ(34):∣2∣=2 general TSP in (( 2 ) time. Their bound also holds for 2 general TSP in (( 2 ) time. Their bound also holds for thespecialcaseof HAMILTONICITY andisstillthestrongest Using bottomup dynamic programming with 3 ﬁxed, the thespecialcaseof HAMILTONICITY andisstillthestrongest Using bottomup dynamic programming with 3 ﬁxed, the known. Under the widely acknowledged Exponential Time lightest tour can be evaluated by min 0 (")+ℓ(34) ∈(∖ , known. Under the widely acknowledged Exponential Time lightest tour can be evaluated by min 0 (")+ℓ(34) ∈(∖ , 2 Hypothesis, the HAMILTONICITY problem has )+(Ω()) in total (( 2 ) time. An HAMILTONICITY instance 2 Hypothesis, the HAMILTONICITY problem has )+(Ω()) in total (( 2 ) time. An HAMILTONICITY instance can naturally be embedded in a TSP instance on the same runtime 14. There is however no known reason to expect can naturally be embedded in a TSP instance on the same runtime 14. There is however no known reason to expect the exponential base to be precisely two. Woeginger in his number of vertices. Simply let the weight function ℓ take the exponential base to be precisely two. Woeginger in his number of vertices. Simply let the weight function ℓ take survey on exact algorithms for NPHard problems 22 the value 0 for vertex pairs corresponding to an edge in , survey on exact algorithms for NPHard problems 22 the value 0 for vertex pairs corresponding to an edge in , ∗ and 1 otherwise. observes this and asks in Open problem 3.1 for a ( (, ) ∗ and 1 otherwise. observes this and asks in Open problem 3.1 for a ( (, ) time algorithm for TSP and HAMILTONICITY for some Another algorithm amenable to HAMILTONICITY with time algorithm for TSP and HAMILTONICITY for some Another algorithm amenable to HAMILTONICITY with ∗ , 2. ( (. ()) suppresses polylogarithmic functions in (almost) the same running time is the inclusion–exclusion ∗ , 2. ( (. ()) suppresses polylogarithmic functions in (almost) the same running time is the inclusion–exclusion . (). We solve the latter problem. counting overlong closed walks in the induced subgraphs. . (). We solve the latter problem. counting overlong closed walks in the induced subgraphs. 02725428/ 02725428/ 02725428/10 26.00 © 10 26.00 © 10 26.00 © 2010 IE 2010 IE 2010 IEE E EE E E 173 173 173 02725428/ 02725428/ 02725428/10 26.00 © 10 26.00 © 10 26.00 © 2010 IE 2010 IE 2010 IEE E EE E E 173 173 173 DOI 10.1109/ DOI 10.1109/ DOI 10.1109/FOC FOC FOCS.2010.24 S.2010.24 S.2010.24 DOI 10.1109/ DOI 10.1109/ DOI 10.1109/FOC FOC FOCS.2010.24 S.2010.24 S.2010.24Euclidean traveling salesperson problem Euclidean TSP. Given n points in the plane and a real number L, is there a tour that visit every city exactly once that has distance ≤ L Proposition. EUCLIDEANTSP is NPhard. 5+ 6+ 18 4+ 12+ 12 Remark. Not known to be in NP. 8.928198407 8.928203230 13509 cities in the USA and an optimal tour 51Euclidean traveling salesperson problem Theorem. Arora 1998, Mitchell 1999 Given n points in the plane, for any constant ε 0, there exists a polytime algorithm to find a tour whose length is at most (1 + ε) times that of the optimal tour. Pf idea. Structure theorem + dynamic programming. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems Sanjeev Arora Princeton University Association for Computing Machinery, Inc., 1515 Broadway, New York, NY 10036, USA Tel: (212) 5551212; Fax: (212) 5552000 We present a polynomial time approximation scheme for Euclidean TSP in ﬁxed dimensions. For 2 every ﬁxedc 1 and given any n nodes in ℜ , a randomized version of the scheme ﬁnds a O(c) (1+1/c)approximation to the optimum traveling salesman tour in O(n(logn) ) time. When √ d−1 d (O( dc)) the nodes are inℜ , the running time increases to O(n(logn) ). For every ﬁxed c,d the running time is n ·poly(logn), i.e., nearly linear in n. The algorithm can be derandomized, but d this increases the running time by a factor O(n ). The previous best approximation algorithm for the problem (due to Christoﬁdes) achieves a 3/2approximation in polynomial time. WealsogivesimilarapproximationschemesforsomeotherNPhardEuclideanproblems: Mini mumSteinerTree, kTSP,andkMST.(TherunningtimesofthealgorithmforkTSPandkMST involve an additional multiplicative factor k.) The previous best approximation algorithms for all these problems achieved a constantfactor approximation. We also give eﬃcient approximation schemes for Euclidean MinCost Matching, a problem that can be solved exactly in polynomial time. All our algorithms also work, with almost no modiﬁcation, when distance is measured using any geometric norm (such as ℓ for p≥ 1 or other Minkowski norms). They also have eﬃcient p parallel (i.e., NC) implementations. 52 Categories and Subject Descriptors: F.2.2 Analysis of Algorithms and Problem Complex ity: Geometricalproblemsandcomputations, Routingandlayout; G.2.2GraphTheory: Path and circuit problems, Trees General Terms: Algorithms, Theory Additional Key Words and Phrases: Approximation Algorithms, Traveling Salesman Problem, Steiner Problem, Network Design, Matching Research supported by NSF CAREER award NSF CCR9502747, an Alfred Sloan Fellowship, and a Packard Fellowship. Address: Computer Science Department, Princeton University, Princeton NJ08444. aroracs.princeton.edu Permissiontomakedigitalorhardcopiesofpartorallofthisworkforpersonalorclassroomuseis grantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforproﬁtordirectcommercial advantage and that copies show this notice on the ﬁrst page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior speciﬁc permission and/or a fee. Permissions may be requested from Publications Dept, ACM Inc., 1515 Broadway, New York, NY 10036 USA, fax +1 (212) 8690481, or permissionsacm.org.Concorde TSP solver Concorde TSP solver. ApplegateBixbyChvátalCook Linear programming + branchandbound + polyhedral combinatorics. Greedy heuristics, including LinKernighan. MST, Delaunay triangulations, fractional bmatchings, ... Remarkable fact. Concorde has solved all 110 TSPLIB instances. 53TSP line art 30 CHAPTER 1 Figure 1.30 Continuous line drawings via the TSP. Images courtesy of Robert Bosch and Continuous line drawings via the TSP by Robert Bosch and Craig Kaplan Craig Kaplan. 54 cities in the resulting TSP. The technique for placing the cities was reﬁned by Kaplan and Bosch 303, using an algorithm developed by Secord 496. In this approach the tone of the image is used as a density fuction to build a weighted Voronoi diagram, that is, a partition of the space into regions such that all points in region i have city i as their nearest neighbor. In computing the nearest neighbor, the density function is used to weight the geometric distance, so that dark Voronoi regions will tend to be smaller than light regions. In an iteration of Secord’s placement algorithm, the cities are replaced by the centers of the regions and a new diagram is computed. Bosch and Kaplan used the above methodology to create the drawings of the Mona Lisa and the Colosseum given in Figure 1.30. The Mona Lisa TSP has 10,000 cities and the Colosseum TSP has 11,999 cities. In each case the drawn tour was computed with Concorde, using a heuristic search module (the tours are most likely not optimal). CHALLENGE PROBLEMS AND THE TSPLIB Geometric examples have long been the primary source of challenge problems for TSP researchers. The example solved in 1954 by Dantzig, Fulkerson, and Johnson 151 consists of ﬁnding a tour through 49 cities in the United States. This began a tradition of creating instances by selecting sets of actual cities and deﬁning the cost of travel as the distance between the city locations. Over the years, increasingly larger examples were considered by taking 120 cities in Germany, 532 cities in the USA, 666 cities all over the world, and so on. Test instances of this type, together with geometric instances from industrial sources and a number of other examples, were gathered together by Gerhard Reinelt 472 in the early 1990s. His library is called TSPLIB and contains over 100 challenge instances, with sizes ranging up to 85,900 cities. This collection has been of great help in TSP research, providing a common test bed for both new and old solution approaches. That’s all, folks: keep searching Wohohohoh, find the longest path I have been hard working for so long. Wohohohoh, find the longest path I swear it's right, and he marks it wrong. Some how I'll feel sorry when it's done: GPA 2.1 Is more than I hope for. If you said P is NP tonight, There would still be papers left to write. I have a weakness; Garey, Johnson, Karp and other men (and women) Tried to make it order N log N. I'm addicted to completeness, Am I a mad fool And I keep searching for the longest path. If I spend my life in grad school, Forever following the longest path The algorithm I would like to see Is of polynomial degree. But it's elusive: Wohohohoh, find the longest path Wohohohoh, find the longest path Nobody has found conclusive Wohohohoh, find the longest path. Evidence that we can find a longest path. Written by Dan Barrett in 1988 while a student at Johns Hopkins during a difficult algorithms takehome ﬁnal 55
Add To Cart
Lecture notes for Advanced data structures and Algorithms
Data Structures and Algorithms PPT
Data Structures and Algorithms in Python
Lecture Notes on Data Structures and Algorithms for Big Databases
Lecture notes on Data structures and Algorithms and C
Problem Solving with Algorithms and Data Structures
Hexacta Corporate Presentation
Lecture notes in Design and analysis of algorithms
Lecture notes design and analysis of algorithms
LECTURE NOTES ON DESIGN AND ANALYSIS OF ALGORITHMS
Lecture notes on Randomized Algorithms
Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques
Genetic Algorithms: Theory and Applications
Lecture Notes on Iterative Optimization Algorithms
Study With Thesis Scientist
How to Sell
Tips and Tricks
Get To Know Us
© Copyright @ Thesis Scientist Pvt. Ltd.
Terms & Conditions
Tips & Tricks