Question? Leave a message!




exact exponential algorithms

exact exponential algorithms
INTRACTABILITY III special cases: trees ‣ special cases: planarity ‣ approximation algorithms ‣ exact exponential algorithms ‣ Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinberg-tardos Last updated on Nov 24, 2014, 8:24 AMCoping with NP-completeness Q. Suppose I need to solve an NP-hard 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. ▪ INDEPENDENT-SET-IN-A-FOREST (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) WEIGHTED-INDEPENDENT-SET-IN-A-TREE (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 _____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 7NP-hard 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 Linear-time on trees. VERTEX-COVER, DOMINATING-SET, GRAPH-ISOMORPHISM, ... 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. Hopcroft-Tarjan 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 depth-first 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, depth-first 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 depth-first search to order the calculations and thereby achieve efficiency. Depth-first 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 N-0O014-A-Ol12-0057 and N-00014-67-A-0077-0021. 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. 549-568. Polynomial time detour Graph minor theorem. Robertson-Seymour 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 fit 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 NP-complete problems become tractable in planar graphs. Ex. MAX-CUT, ISING, CLIQUE, GRAPH-ISOMORPHISM, 4-COLOR, ... Fact 2. Other NP-complete problems become easier in planar graphs. Ex. INDEPENDENT-SET, VERTEX-COVER, TSP, STEINER-TREE, ... An O(nlogn)AlgorithmforMaximum st-Flow inaDirectedPlanarGraph GLENCORABORRADAILEANDPHILIPKLEIN Brown University, Providence, Rhode Island Abstract. Wegivethefirstcorrect O(nlogn)algorithmforfindingamaximumst-flowinadirected planargraph.Afterapreprocessingstepthatconsistsinfindingsingle-sourceshortest-pathdistances inthedual,thealgorithmconsistsofrepeatedlysaturatingtheleftmostresidual s-to-t path. Categories and Subject Descriptors: F.2.2 Analysis of Algorithms and Problem Complexity: NonnumericalAlgorithmsandProblems GeneralTerms:Algorithms AdditionalKeyWordsandPhrases:Maximumflow,planargraphs ACMReferenceFormat: Borradaile, G. and Klein, P. 2009. An O(nlogn) algorithm for maximum st-flow 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-flowproblemisasfollows:givenagraphwithpositive arc-capacities,andgivenasourcevertex s andasinkvertex t,thegoalistofinda waytoroutethemaximumamountofasinglecommodityalongs-to-t pathsinsuch awaythattheamountofcommoditypassingthroughanarcisatmostthecapacity of the arc. In the minimum st-cut problem, the goal is to find a minimum-capacity set of arcs such that each s-to-t path includes at least one arc in the set. Formal definitionswillbegiveninSection4.5. The history of maximum-flow and minimum-cut 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 ACM-SIAM Symposium on Discrete Algorithms (SODA’06),ACM,NewYork,2006,pp.524–533. G.BorradailewassupportedbyNSERCPGS-D,Rowland-LloydCST,Kanellakis,aBrownUniversity DissertationFellowship,andNSFGrantCCF-0635089.P.KleinwassupportedbyNSFGrantCCF- 0635089. Authors’ addresses: Department of Computer Science, Brown University, Providence, RI 02912, e-mail: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 profit or commercial advantageandthatcopiesshowthisnoticeonthefirstpageorinitialscreenofadisplayalongwiththe full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstractingwithcreditispermitted.Tocopyotherwise,torepublish,topostonservers,toredistribute tolists,ortouseanycomponentofthisworkinotherworksrequirespriorspecificpermissionand/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, NewYork,NY10121-0701USA,fax+1(212)869-0481,orpermissionsacm.org. ⃝ C 2009ACM0004-5411/2009/04-ART95.00 DOI10.1145/1502793.1502798 http://doi.acm.org/10.1145/1502793.1502798 JournaloftheACM,Vol.56,No.2,Article9,Publicationdate:April2009.Planar graph 3-colorability PLANAR-3-COLOR. Given a planar graph, can it be colored using 3 colors so that no two adjacent nodes have the same color? 14Planar map 3-colorability PLANAR-MAP-3-COLOR. 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 3-colorability PLANAR-MAP-3-COLOR. 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 3-colorability reduce to one another Theorem. PLANAR-3-COLOR ≣ PLANAR-MAP-3-COLOR. P Pf sketch. Nodes correspond to regions. Two nodes are adjacent iff they share a nontrivial border. e.g., not Arizona and Colorado 17Planar 3-colorability is NP-complete Theorem. PLANAR-3-COLOR ∈ NP-complete. Pf. Easy to see that PLANAR-3-COLOR ∈ NP. We show 3-COLOR ≤ PLANAR-3-COLOR. P Given 3-COLOR instance G, we construct an instance of PLANAR-3-COLOR that is 3-colorable iff G is 3-colorable. 18Planar 3-colorability is NP-complete Lemma. W is a planar graph such that: In any 3-coloring 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 3-coloring of W. planar gadget W 19Planar 3-colorability is NP-complete Lemma. W is a planar graph such that: In any 3-coloring 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 3-coloring of W. Pf. The only 3-colorings (modulo permutations) of W are shown below. ▪ planar gadget W 20Planar 3-colorability is NP-complete Construction. Given instance G of 3-COLOR, draw G in plane, letting edges cross. Form planar G' by replacing each edge crossing with planar gadget W. Lemma. G is 3-colorable iff G' is 3-colorable. In any 3-coloring of W, a ≠ a' and b ≠ b'. If a ≠ a' and b ≠ b' then can extend to a 3-coloring of W. b b a' a a' a b' a crossing gadget W b' 21Planar 3-colorability is NP-complete Construction. Given instance G of 3-COLOR, draw G in plane, letting edges cross. Form planar G' by replacing each edge crossing with planar gadget W. Lemma. G is 3-colorable iff G' is 3-colorable. In any 3-coloring of W, a ≠ a' and b ≠ b'. If a ≠ a' and b ≠ b' then can extend to a 3-coloring of W. a W W W a' a' a multiple crossings concatenate copies of gadget W 22Planar map k-colorability Theorem. Appel-Haken 1976 Every planar map is 4-colorable. Resolved century-old 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 Appel-Haken yields O(n ) algorithm to 4-color 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 4-color; O(n) to 5-color. 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 NP-complete. 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 Polynomial-time special cases NP-hard problems Trees. VERTEX-COVER, INDEPENDENT-SET, DOMINATING-SET, GRAPH-ISOMORPHISM, ... Bipartite graphs. VERTEX-COVER, 2-COLOR, ... Chordal graphs. K-COLOR, CLIQUE, INDEPENDENT-SET, ... Planar graphs. MAX-CUT, ISING, CLIQUE, GRAPH-ISOMORPHISM, 4-COLOR, ... Bounded treewidth. 3-COLOR, HAM-CYCLE, INDEPENDENT-SET, GRAPH-ISOMORPHISM. Small integers. KNAPSACK, PARTITION, SUBSET-SUM, ... 24INTRACTABILITY III special cases: trees ‣ special cases: planarity ‣ approximation algorithms ‣ exact exponential algorithms ‣ SECTION 11.8Approximation algorithms ρ-approximation algorithm. Guaranteed to run in poly-time. 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 VERTEX-COVER 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 NP-complete 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 SUBSET-SUM. 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. SUBSET-SUM ≤ KNAPSACK. P Pf. Given instance (u , …, u , U) of SUBSET-SUM, 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 )Qi?2`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: polynomial-time 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: polynomial-time 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: polynomial-time 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: polynomial-time 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 MAX-3-SAT. Given a 3-SAT instance Φ, find an assignment that satisfies the maximum number of clauses. Theorem. Karloff-Zwick 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 Max-Ek-Sat for takesaninstanceofMAX3SATasinput. Iftheinstance—a Abstract that the performance ratio of his algorithm is actually 2/3. k≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear simpler 3/4-approximation algorithm. Their algorithm is collectionofclauseseachoflengthatmostthree—issatisfi- 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 lowerboundsfortheefficientapproximabilityofmanyoptimizationproblemsstudiedpreviously.In least ofoptimal. Weprovidestrongevidence(butnota Williamson 17 then obtained a different and somewhat particular,forMax-E2-Sat,Max-Cut,Max-di-Cut,andVertexcover. In a major breakthrough, Goemans and Williamson 18 takesaninstanceofMAX3SATasinput. Iftheinstance—a proof)thatthealgorithmperformsequallywellonarbitrary simpler 3/4-approximation algorithm. Their algorithm is obtained a 0.878-approximation algorithm for MAX CUT collectionofclauseseachoflengthatmostthree—issatisfi- 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 semidefinite programming and may be In a major breakthrough, Goemans and Williamson 18 used semidefinite rAdditional elaxationKseoyfW thords eseand proPhrases: blems. Inapproximability Feige and ,linearequations,max-sat,NP-hardoptimiza- proof)thatthealgorithmperformsequallywellonarbitrary seenasasequeltotheMAXCUTalgorithmofGoemansand obtained a 0.878-approximation algorithm for MAX CUT tionproblems,probabilisticallycheckableproofs Goemans 15 then obtained a 0.931-approximation 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 semidefinite 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 semidefinite relaxationsof these problems. Feige and seenasasequeltotheMAXCUTalgorithmofGoemansand 1. Introduction improvements in the performance ratio for general MAX volumesofsphericaltetrahedraG.oemans 15 then obtained a 0.931-approximation algo- WilliamsonandtheMAX2SATalgorithmofFeigeandGoe- SAT can bemade.Man Goem ynatural ansandoptimization Williamson problems 18 obtainare edNP-hard,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 sufficient 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 polynomial-time 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 semidefinite relaxations yield a huge improvement satisfiableinstancesoftheproblem. Ouralgorithmisthere- Ha˚stad has recently shown that, assuming ,no basicNP-completeproblems.Foramaximizationproblemwesaythatanalgorithm a 0.758 bound for MAX SAT. Asano 4 (following 5) forMAX2SAT(from0.75to0.931),theygive,sofar,only foreoptimalin thissense. polynomial-time algorithm for MAX 3SAT can achieve a isaC-approximationalgorithmifit,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 semidefinite The reason for this seems to be that the semidefinite relax- While semidefinite relaxations yield a huge improvement definitionappliestominimizationproblems. satisfiableinstancesoftheproblem. Ouralgorithmisthere- relaxations of any constraint satisfaction problem of the ationsusedtillnowdonotdirectlyhandleclausesoflength forMAX2SAT(from0.75to0.931),theygive,sofar,oAnlfundamental y questionis,foragivenNP-completeproblem,forwhatvalueof foreoptimalin thissense. form MAXCSP , where is a finite family of Boolean threeormore. C can we hope for a polynomial time C-approximation 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 semidefinite generality, this is a large research area with many positive and negative results. In The reason for this seems to be that the semidefinite relax- An attempt to squeeze more from the MAX 2SAT algo- anaturalclassofsemidefiniterelaxations. 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 finite 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- anaturalclassofsemidefiniterelaxations. 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- ThemostbasicNP-completeproblemissatisfiabilityofCNF-formulasandprob- MAXSATisacentralproblemin theoreticalcomputersci- 2SAT, thereby obtaining a 0.801-approximation algorithm timal gadget, a concept formalized by Bellare, Goldre- ably the most used variant of this is 3-SAT where each clause contains at most 3 1 Introduction ence. AsitisNP-hardand,infact,MAX-SNPcomplete(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 satisfiable 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 first approximationalgo- 3SAT,anda0.8-approximationalgorithmfor satisfiablein- MAXSATisacentralproblemin theoreticalcomputersci- 2SAT, thereby obtaining a 0.801-approximation algorithm Theory of Computing(ElPaso,Tex.,May4–6).ACM,NewYork,1997,pp.1–10. rithm forMAX SAT was proposedby Johnson 23. John- stancesofMAXSAT. ence. AsitisNP-hardand,infact,MAX-SNPcomplete(Pa- for MAX 3SAT. Trevisan 33 recently obtained a 0.826- Author’saddress:DepartmentofNumericalAnalysisandComputerScience,RoyalInstituteofTech- sonshowedthattheperformanceratioofhisalgorithmisat padimitriouandYannakakis30),muchattentionhasbeen approximation algorithm for satisfiable instances ofnology MAX ,S-10044Stockholm,Sweden,e-mail:johanhnada.kth.se. In anothermajorbreakthrough,followinga long line of re- least . Chen, Friesen and Zheng 12 recently showed devoted to approximatingit. The first approximationalgo- Permissiontomakedigital/hardcopyofpartorallofthisworkforpersonalorclassroomuseisgranted 3SAT,anda0.8-approximationalgorithmfor satisfiablein- searchbymanyauthors16,3,2,8,7,Has ˚ tad20recently without fee provided that the copies are not made or distributed for profit 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. E-mailaddress: howardcc.gatech.edu. least . Chen, Friesen and Zheng 12 recently showed not be approximated in polynomial time to within a ratio republish,topostonservers,ortoredistributetolists,requirespriorspecificpermissionand/orafee. searchbymanyauthors16,3,2,8,7,Has ˚ tad20recently Department of Computer Science, Tel-Aviv University, Tel-Aviv ⃝ C 2001ACM0004-5411/01/0700-07985.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. E-mailaddress: zwickmath.tau.ac.il. that no polynomial-timealgorithmcan havea performance gia 30332-0280, U.S.A. Research supported in part by NSF grant CCR- probleminwhicheachclauseisoflengthexactlythree,can- JournaloftheACM,Vol.48,No.4,July2001,pp.798–859. 9319106. E-mailaddress: howardcc.gatech.edu. not be approximated in polynomial time to within a ratio Department of Computer Science, Tel-Aviv University, Tel-Aviv greater than 7/8, unless . Has ˚ tad shows, in fact, 69978,Israel. Thisworkwasdonewhile this authorwas visiting ICSIand 1 UCBerkeley. E-mailaddress: zwickmath.tau.ac.il. that no polynomial-timealgorithmcan havea performance 1INTRACTABILITY III special cases: trees ‣ special cases: planarity ‣ approximation algorithms ‣ exact exponential algorithms ‣Exact exponential algorithms Complexity theory deals with worst-case behavior. Instances you want to solve may be "easy." “ For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run.” — Alan Perlis 38Exact algorithms for 3-satisfiability Brute force. Given a 3-SAT instance with n variables and m clauses, n the brute-force 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 3-satisfiability A recursive framework. A 3-SAT formula Φ is either empty or the disjunction of a clause (ℓ ∨ℓ ∨ℓ) and a 3-SAT 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 3-satisfiability A recursive framework. A 3-SAT formula Φ is either empty or the disjunction of a clause (ℓ ∨ℓ ∨ℓ) and a 3-SAT formula Φ' with one fewer clause. 1 2 3 3-SAT (Φ) ______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ IF Φ is empty RETURN true. (ℓ ∨ ℓ ∨ ℓ) ∧ Φ' ← Φ. 1 2 3 IF 3-SAT(Φ' ℓ = true) RETURN true. 1 IF 3-SAT(Φ' ℓ = true) RETURN true. 2 IF 3-SAT(Φ' ℓ = true) RETURN true. 3 RETURN false. ______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ n Theorem. The brute-force 3-SAT algorithm takes O(poly(n) 3 ) time. Pf. T(n) ≤ 3T(n – 1) + poly(n). ▪ 41Exact algorithms for 3-satisfiability 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 3-SAT (Φ) ______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ IF Φ is empty RETURN true. (ℓ ∨ ℓ ∨ ℓ) ∧ Φ' ← Φ. 1 2 3 IF 3-SAT(Φ' ℓ = true ) RETURN true. 1 IF 3-SAT(Φ' ℓ = false, ℓ = true) RETURN true. 1 2 IF 3-SAT(Φ' ℓ = false, ℓ = false, ℓ = true) RETURN true. 1 2 3 RETURN false. ______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 42Exact algorithms for 3-satisfiability n Theorem. The brute-force 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 3-SAT (Φ) ______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ IF Φ is empty RETURN true. (ℓ ∨ ℓ ∨ ℓ) ∧ Φ' ← Φ. 1 2 3 IF 3-SAT(Φ' ℓ = true ) RETURN true. 1 IF 3-SAT(Φ' ℓ = false, ℓ = true) RETURN true. 1 2 IF 3-SAT(Φ' ℓ = false, ℓ = false, ℓ = true) RETURN true. 1 2 3 RETURN false. ______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 43Exact algorithms for 3-satisfiability n Theorem. There exists a O(1.33334 ) deterministic algorithm for 3-SAT. AFullDerandomizationofScho¨ning’s k-SAT 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 randomizedalgorithmfork-SAT 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 k-SAT. Ten years on, the fastest algorithms for k-SAT 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 unsatisfied clause C.From C,pickaliteraluniformlyatrandom,andchange the truth value of its underlying variable, thus satisfying C.Repeatthisreassignment step O(n)times. If F is satisfiable, this finds a satisfying assignment with probability at least " n k 44 . 2(k−1) ∗ n ∗ n By repetition, this gives a randomized O (1.334 )algorithmfor3-SAT,an O (1.5 )for ∗ 4-SAT, 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 3-SAT and O (1.6 )for4-SAT.Subsequentpapershaveimproveduponthisrunning time, mainly focusing on 3-SAT: Dantsin et al. already improve the running time for n n n 3-SAT 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 sufferfrom 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 satisfiability DPPL algorithm. Highly-effective 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 D_vs the form Theorem-Provingt 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 one-literM 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 QFl-Generator, generates (from out using only fast access storage. When the "Splitting Gentzen-like 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 "quantifier-free lines." The second part, the Processor, terial stack-of-plates 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 quantifier-free lines constitutes a proof of the original conjunction of quantifier-free lines are coded into cross- 201 formula. referenced associated (or linked) memory tables by the The algorithm of 1 used in testing for consistency QFL-Generator and then analyzed by the Processor. In particular, the QFL-Generator is programmed to read in proceeded by successive elimination of atomic formulas, first eliminating one-literal clauses (one-literM clause rule), the matrix M in suitably coded Polish (i.e., "parenthesis- free") form. The conversion to a quantifier-free 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 tive-negative 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 truth-functional 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 one-to-one 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 quantifier-free 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 satisfiability Chaff. State-of-the-art SAT solver. Solves real-world 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, rel_sat 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 Davis-Putnam (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 Davis-Putnam (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 Davis-Putnam Backtrack Search J6 Computer-Aided Engineering: Computer-Aided Design. We start with a quick review of the basic Davis-Putnam backtrack search. This is described in the following pseudo-code 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 NP-complete 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 brute-force algorithm for TSP (or HAM-CYCLE) 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, Held-Karp 1962 There exists a O(n 2 ) time algorithm for TSP (and HAMILTON-CYCLE). Dynamic Programming Treatment of the Travelling Salesman Problem RICHARD ELLMAN RAND Corporation, Santa Monica, California Introdction The well-known 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 all-integer 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, Held-Karp 1962 There exists a O(n 2 ) time algorithm for TSP (and HAMILTON-CYCLE). 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 HAMILTON-CYCLE. 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 first superpolynomial improvement on the worst case runtime first 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 fifty years ago (Bellman 1962, Held and Karp 1962). %. almost fifty years ago (Bellman 1962, Held and Karp 1962). It answers in part the first open problem in Woeginger’s 2003 For graphs having an induced subgraph with many dis- It answers in part the first open problem in Woeginger’s 2003 For graphs having an induced subgraph with many dis- survey on exact algorithms for NP-hard problems. connected components, most notably bipartite graphs, we survey on exact algorithms for NP-hard 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 finite field of characteristic two. We We also note that our algorithm can be used to solve labeled cycle covers over a finite field of characteristic two. We TSP with integer weights via self-reducibility at the cost reduce Hamiltonicity to Labeled Cycle Cover Sum and apply TSP with integer weights via self-reducibility at the cost reduce Hamiltonicity to Labeled Cycle Cover Sum and apply the determinant summation technique for Exact Set Covers of a runtime blow-up by roughly a factor of the sum of all the determinant summation technique for Exact Set Covers of a runtime blow-up 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 finding the Theorem 3: There is a Monte Carlo algorithm finding 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 weightedgraphon%verticesin( (01.657 )time,where0 ∗ An undirected graph =(",) on % vertices is said 50 weightedgraphon%verticesin( (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 first identified as NP-hard. It is on Karp’s original for TSP in an %-vertex complete graph =(",) with one of the first identified as NP-hard. 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 defining 0 (2) for + ,% list 16, but is perhaps best known as a special case of the edge weights ℓ : →ℝ is based on defining 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 bottom-up dynamic programming with 3 fixed, the thespecialcaseof HAMILTONICITY andisstillthestrongest Using bottom-up dynamic programming with 3 fixed, 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 NP-Hard problems 22 the value 0 for vertex pairs corresponding to an edge in , survey on exact algorithms for NP-Hard 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 over%-long closed walks in the induced subgraphs. . (%). We solve the latter problem. counting over%-long closed walks in the induced subgraphs. 0272-5428/ 0272-5428/ 0272-5428/10 26.00 © 10 26.00 © 10 26.00 © 2010 IE 2010 IE 2010 IEE E EE E E 173 173 173 0272-5428/ 0272-5428/ 0272-5428/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. EUCLIDEAN-TSP is NP-hard. 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 poly-time 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) 555-1212; Fax: (212) 555-2000 We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For 2 every fixedc 1 and given any n nodes in ℜ , a randomized version of the scheme finds 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 fixed 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 Christofides) achieves a 3/2-approximation in polynomial time. WealsogivesimilarapproximationschemesforsomeotherNP-hardEuclideanproblems: Mini- mumSteinerTree, k-TSP,andk-MST.(Therunningtimesofthealgorithmfork-TSPandk-MST involve an additional multiplicative factor k.) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. We also give efficient approximation schemes for Euclidean Min-Cost Matching, a problem that can be solved exactly in polynomial time. All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as ℓ for p≥ 1 or other Minkowski norms). They also have efficient 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 CCR-9502747, an Alfred Sloan Fellowship, and a Packard Fellowship. Address: Computer Science Department, Princeton University, Princeton NJ08444. aroracs.princeton.edu Permissiontomakedigitalorhardcopiesofpartorallofthisworkforpersonalorclassroomuseis grantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitordirectcommercial advantage and that copies show this notice on the first 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 specific permission and/or a fee. Permissions may be requested from Publications Dept, ACM Inc., 1515 Broadway, New York, NY 10036 USA, fax +1 (212) 869-0481, or permissionsacm.org.Concorde TSP solver Concorde TSP solver. Applegate-Bixby-Chvátal-Cook Linear programming + branch-and-bound + polyhedral combinatorics. Greedy heuristics, including Lin-Kernighan. MST, Delaunay triangulations, fractional b-matchings, ... 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 refined 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 finding a tour through 49 cities in the United States. This began a tradition of creating instances by selecting sets of actual cities and defining 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 Woh-oh-oh-oh, find the longest path I have been hard working for so long. Woh-oh-oh-oh, 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: Woh-oh-oh-oh, find the longest path Woh-oh-oh-oh, find the longest path Nobody has found conclusive Woh-oh-oh-oh, 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 take-home final 55
Website URL
Comment