6809:
6695:, that describes computational problems in which a solution is guaranteed to exist and can be recognized in polynomial time. For a problem in PLS, a solution is guaranteed to exist because the minimum-cost vertex of the entire graph is a valid solution, and the validity of a solution can be checked by computing its neighbors and comparing the costs of each one to another.
52:
When searching for a local optimum, there are two interesting issues to deal with: First how to find a local optimum, and second how long it takes to find a local optimum. For many local search algorithms, it is not known, whether they can find a local optimum in polynomial time or not. So to answer
43:
and the neighborhood of a solution can be searched in polynomial time. Therefore it is possible to verify whether or not a solution is a local optimum in polynomial time. Furthermore, depending on the problem and the algorithm that is used for solving the problem, it might be faster to find a local
1053:
If we are simply counting the number of satisfied clauses, the problem can be solved in polynomial time since the number of possible costs is polynomial. However, if we assign each clause a positive integer weight (and seek to locally maximize the sum of weights of satisfied clauses), the problem
4806:
of one problem to another may be used to show that the second problem is at least as difficult as the first. In particular, a PLS-reduction is used to prove that a local search problem that lies in PLS is also PLS-complete, by reducing a PLS-complete
Problem to the one that shall be proven to be
53:
the question of how long it takes to find a local optimum, Johnson, Papadimitriou and
Yannakakis introduced the complexity class PLS in their paper "How easy is local search?". It contains local search problems for which the local optimality can be verified in polynomial time.
7021:
is PLS-complete if property P = "has no edges", as it then equals
Weighted-Independent-Set/Change. It has also been proven to be PLS-complete for a general hereditary, non-trivial property P via a tight PLS-reduction from Weighted-Independent-Set/Change to
279:
1356:
6804:
This is an incomplete list of some known problems that are PLS-complete. The problems here are the weighted versions; for example, Max-2SAT/Flip is weighted even though Max-2SAT ordinarily refers to the unweighted version.
4119:
6977:
has been proven to be PLS-complete via a PLS-reduction from Min/Max-circuit/Flip to Max-Uniform-Graph-Partitioning/Kernighan-Lin. There is also a tight PLS-reduction from
Positive-not-all-equal-max-3Sat/Kernighan-Lin to
7172:
has been proven to be PLS-complete via a reduction from 2-Threshold-Games/Change to
Overlay-Network-Design/Change. Analogously to the proof of asymmetric Directed-Network-Congestion-Game/Change, the reduction is
7106:
has been proven to be PLS-complete via a tight reduction from
Positive-not-all-equal-max-3Sat/Flip to Directed-Network-Congestion-Games/Change and also via a tight PLS-reduction from 2-Threshold-Games/Change to
5013:
4755:
can be solved exactly in polynomial time. It is not necessary always to use the standard algorithm, there may be a different, faster algorithm for a certain problem. For example a local search algorithm used for
2031:
1934:
1708:
6904:
has been proven to be PLS-complete via a tight PLS-reduction from Min/Max-circuit/Flip to
Positive-not-all-equal-max-3Sat/Flip. Note that Positive-not-all-equal-max-3Sat/Flip can be reduced from Max-Cut/Flip
5742:
and the edges point from one solution to the neighbor with strictly better cost. Therefore it is an acyclic graph. A sink, which is a node with no outgoing edges, is a local optimum. The height of a vertex
2667:
4265:
to balance the partitions again. Experiments have shown that
Fiduccia-Mattheyses has a smaller run time in each iteration of the standard algorithm, though it sometimes finds an inferior local optimum.
7064:
has been proven to be PLS-complete via a tight PLS-reduction from
Weighted-3Dimensional-Matching/(p, q)-Swap to (2p+q)-Selfish-Multi-Processor-Scheduling/k-change-with-property-t, where (2p + q) ≥ 8.
2527:
5783:
to the nearest sink. The height of the transition graph is the largest of the heights of all vertices, so it is the height of the largest shortest possible path from a node to its nearest sink.
4489:
1561:
7253:
has been proven to be PLS-complete for p ≥9 and q ≥ 15 via a tight PLS-reduction from (2, 3, r)-Max-Constraint-Assignment-2-partite/Change to
Weighted-3Dimensional-Matching/(p, q)-Swap.
7226:
equals Max-4Sat-(B=3)/Flip and has been proven to be PLS-complete via a PLS-reduction from Max-circuit/Flip. It is claimed that the reduction can be extended so tightness is obtained.
4913:
716:
7395:
2317:
7058:
has been proven to be PLS-complete via a tight PLS-reduction from Weighted-3Dimensional-Matching/(p, q)-Swap to Local-Multi-Processor-scheduling/(2p+q)-change, where (2p + q) ≥ 8.
6548:
7325:
2576:
990:
4665:
4535:
2926:
2363:
2853:
2712:
590:
6870:
4321:
6203:
6002:
5470:
5275:
4236:
4169:
4013:
3973:
3735:
3695:
864:
815:
766:
4414:
3879:
3833:
3787:
3655:
3609:
3563:
3517:
1750:
1636:
1503:
1406:
6486:
6418:
6296:
6251:
3460:
2800:
3014:
937:
2747:
2132:
1825:
1783:
1594:
1461:
6615:
6332:
5740:
5563:
5394:
5199:
5107:
3059:
1190:
448:
6581:
4710:
2056:
1134:
6154:
6662:
6379:
6128:
6079:
6029:
5933:
5906:
5875:
5848:
5821:
5664:
5617:
5590:
5524:
5497:
5421:
5358:
5329:
5302:
5226:
5163:
5134:
5071:
5044:
4867:
4840:
4619:
4570:
4263:
4196:
4131:- This neighborhood is similar to the Kernighan-Lin neighborhood structure, it is a greedy sequence of swaps, except that each swap happens in two steps. First the
3933:
3906:
3270:
3243:
3196:
2953:
2254:
2184:
1107:
529:
502:
475:
412:
385:
358:
332:
7244:
has been proven to be PLS-complete if the thresholds are 0 and the weights are negative via a tight PLS-reduction from Max-Cut/Flip to Stable-Configuration/Flip.
168:
6838:
6783:
6760:
6737:
6635:
6438:
6352:
6101:
6052:
5953:
5781:
5761:
5704:
5684:
4792:
4753:
4730:
4685:
4590:
4372:
4352:
3419:
3399:
3379:
3359:
3336:
3316:
3290:
3216:
3165:
3145:
3125:
3105:
3085:
2973:
2454:
2434:
2390:
2224:
2204:
2152:
2096:
2076:
1426:
1230:
1210:
1154:
1080:
1047:
1010:
906:
886:
657:
637:
617:
305:
159:
131:
111:
78:
1235:
3218:
with the best cost, or the least loss of cost, is chosen to be a neighbor of s in the Kernighan-Lin structure. As well as best (or least worst) neighbor of
1026:
It is possible to calculate the cost of a solution in polynomial time, by going once through the whole instance and counting the clauses that are satisfied.
7093:
has been proven to be PLS-complete via a tight PLS-reduction from an asymmetric General-Congestion-Game/Change to symmetric General-Congestion-Game/Change.
7159:
with polynomial bounded costs has been proven to be PLS-complete via a tight PLS-reduction from 2-Threshold-Games/Change to Market-Sharing-Game/Change.
4018:
7120:
has been proven to be PLS-complete via a tight PLS-reduction from 2-Threshold-Games/Change to Asymmetric Undirected-Network-Congestion-Games/Change.
4121:
gains the highest possible weight, or loses the least possible weight. Note that no node is allowed to be swapped twice. This rule is based on the
7031:
has been proven to be PLS-complete for each k ≥ 2 via a tight PLS-reduction from (3, 2, r)-Max-Constraint-Assignment/Change to Set-Cover/k-change.
8374:
8153:
7807:
7133:
has been proven to be PLS-complete via a tight PLS-reduction from 2-Threshold-Games to Symmetric Distance-Bounded-Network-Congestion-Games.
4918:
7608:
2392:, that has no neighbor with better costs. In the implicit graph, a local optimum is a sink. A neighborhood where every local optimum is a
1942:
1832:
6911:
has been proven to be PLS-complete via a tight PLS-reduction from Min/Max-circuit/Flip to Positive-not-all-equal-max-3Sat/Kernighan-Lin.
1643:
7214:
has been proven to be PLS-complete via a tight PLS-reduction from Circuit/Flip to (2, 3, 6)-Max-Constraint-Assignment-2-partite/Change.
7208:
has been proven to be PLS-complete via a tight PLS-reduction from Circuit/Flip to (3, 2, 3)-Max-Constraint-Assignment-3-partite/Change.
8257:
8069:
7949:
7916:
7730:
7523:
7080:
has been proven PLS-complete via a tight PLS-reduction from Positive-not-all-equal-max-3Sat/Flip to General-Congestion-Game/Change.
2581:
7199:
20:
8201:
7010:
6924:
6885:
6789:
8290:
Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold (2008). "On the Impact of Combinatorial Structure on Congestion Games".
2462:
6968:
has been proven to be PLS-complete via a tight PLS-reduction from Max-Cut/Flip to Max-Uniform-Graph-partitioning/FM-Swap.
4735:
Unfortunately, it generally takes an exponential number of improvement steps to find a local optimum even if the problem
7220:
has been proven to be PLS-complete via a tight reduction from Circuit/Flip to (6,2, 2)-Max-Constraint-Assignment/Change.
7195:
is claimed to be PLS-complete because of PLS-reduction to Max-0-1-Integer Programming/k-Flip, but the proof is left out.
6987:
has been proven to be PLS-complete via a tight PLS-reduction from Positive-not-all-equal-max-3Sat/Flip to Max-Cut/Flip.
4122:
1029:
It is possible to find all neighbors of a solution in polynomial time, by taking the set of solutions that differ from
8599:
7044:
7035:
6950:
has been proven to be PLS-complete via a tight PLS-reduction from Max-Cut/Flip to Max-Uniform-Graph-partitioning/Swap.
1114:
7876:
Schäffer, Alejandro A.; Yannakakis, Mihalis (February 1991). "Simple Local Search Problems that are Hard to Solve".
7934:
Paradigms of Combinatorial Optimization: Problems and New Approaches - Local Search: Complexity and Approximation
7665:
1511:
1110:
4419:
7606:
Mulzer, Wolfgang; Stein, Yannik (14 March 2018). "Computational Aspects of the Colorful Caratheodory Theorem".
7234:
has been proven to be PLS-complete via a PLS-reduction from Max-2Sat/Flip to Nearest-Colorful-Polytope/Change.
4872:
662:
6935:(or CNF-SAT) has been proven to be PLS-complete via a PLS-reduction from Max-circuit/Flip to Max-4Sat-B/Flip.
7330:
7049:
has been proven to be PLS-complete via a tight PLS-reduction from Max-2Sat/Flip to Metric-TSP/Lin-Kernighan.
39:. The main characteristics of problems that lie in PLS are that the cost of a solution can be calculated in
8126:
Dumrauf, Dominic; Süß, Tim (2010). "On the Complexity of Local Search for Weighted Standard Set Problems".
8299:
8235:
8230:
Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (2004). "The complexity of pure Nash equilibria".
8131:
7978:
7460:
7248:
6894:
6491:
4803:
4768:
2413:
1023:
It is possible to find a solution to an instance in polynomial time, for example by setting all bits to 0.
7267:
4271:- This neighborhood structure is based on the Fiduccia-Mattheyses neighborhood structure. Each solution
2532:
2873:
8545:
7421:
7146:
has been proven to be PLS-complete via a tight reduction from Max-Cut/Flip to 2-Threshold-Game/Change.
6929:
has been proven to be PLS-complete via a tight PLS-reduction from Min-circuit/Flip to Min-4Sat-B/Flip.
4774:
The space the standard algorithm needs is only polynomial. It only needs to save the current solution
2805:
2672:
2269:
541:
8130:. Lecture Notes in Computer Science. Vol. 6158. Springer, Berlin, Heidelberg. pp. 132–140.
7627:
7261:
6843:
4274:
36:
8304:
8136:
7465:
6941:
has been proven to be PLS-complete via a PLS-reduction from Max-circuit/Flip to Max-4Sat-(B=3)/Flip.
6159:
5958:
5426:
5231:
4201:
4134:
3978:
3938:
3700:
3660:
821:
772:
723:
7983:
7190:
7177:
7053:
7040:
has been proven to be PLS-complete via a PLS-reduction from Max-4Sat-B/Flip to Metric-TSP/k-Change.
5623:
4377:
3838:
3792:
3746:
3614:
3568:
3522:
3476:
2412:
is the class containing all problems that can be reduced in polynomial time to the problem Sink-of-
1713:
1599:
1466:
1369:
942:
8240:
6808:
6443:
6384:
6258:
6208:
4624:
4494:
3424:
2863:
Example neighborhood structures for problems with boolean variables (or bit strings) as solution:
2752:
2322:
8557:
8526:
8500:
8352:
8344:
8325:
8263:
8207:
8159:
8075:
7813:
7759:
7643:
7617:
7448:
7401:
4757:
2978:
7790:
Daskalakis, Constantinos; Papadimitriou, Christos (23 January 2011). "Continuous Local Search".
6920:
has been proven to be PLS-complete via a tight PLS-reduction from Max-Cut/Flip to Max-2Sat/Flip.
2717:
2104:
1788:
1755:
1566:
1433:
6586:
8575:
8518:
8469:
8420:
8370:
8317:
8253:
8197:
8149:
8065:
8025:
7945:
7912:
7803:
7726:
7519:
7425:
7026:
6301:
5709:
5532:
5363:
5168:
5076:
4761:
4541:
Every local search problem can be solved using the following iterative improvement algorithm:
4323:
has only one neighbor, the partition obtained after the first swap of the Fiduccia-Mattheyses.
3023:
2393:
1159:
417:
6553:
1119:
113:
the best neighboring solution or if there is no such better neighboring solution, state that
8567:
8510:
8459:
8451:
8410:
8362:
8309:
8245:
8189:
8141:
8106:
8057:
8017:
7988:
7937:
7885:
7795:
7769:
7635:
7583:
7470:
7241:
7164:
7151:
7138:
7125:
7112:
7098:
7085:
7069:
6915:
6685:
6133:
3339:
3017:
911:
162:
28:
6640:
6357:
6106:
6057:
6007:
5911:
5884:
5853:
5826:
5794:
5642:
5595:
5568:
5502:
5475:
5399:
5336:
5307:
5280:
5204:
5141:
5112:
5049:
5022:
4845:
4818:
4597:
4548:
4241:
4174:
3911:
3884:
3248:
3221:
3174:
2931:
2232:
2157:
1085:
507:
480:
453:
390:
363:
337:
310:
274:{\displaystyle (x_{1}\vee x_{2})\wedge (\neg x_{1}\vee x_{3})\wedge (\neg x_{2}\vee x_{3})}
7075:
6972:
6963:
6954:
6945:
6681:
6677:
2457:
40:
7631:
4690:
3292:
is negated. Note that it is not allowed to flip a bit back, if it once has been flipped.
3147:
by a sequence of greedy flips, where no bit is flipped twice. This means, starting with
2036:
8464:
8439:
8186:
Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90
7747:
7411:
with K ≥ 2 was proven to be PLS-complete via a tight PLS-reduction from Max-2SAT/Flip.
6823:
6768:
6745:
6722:
6673:
6620:
6423:
6337:
6086:
6037:
5938:
5766:
5746:
5689:
5669:
4777:
4738:
4715:
4670:
4575:
4357:
4337:
3404:
3384:
3364:
3344:
3321:
3301:
3275:
3201:
3150:
3130:
3110:
3090:
3070:
2958:
2439:
2419:
2375:
2257:
2209:
2189:
2137:
2081:
2061:
1411:
1351:{\displaystyle R\subseteq D_{L}\times F_{L}(I):=\{(I,s)\mid I\in D_{L},s\in F_{L}(I)\}}
1215:
1195:
1139:
1065:
1032:
995:
891:
871:
642:
622:
602:
290:
144:
116:
96:
63:
8111:
8094:
8593:
8530:
7993:
7966:
7841:
7690:
7647:
7588:
7571:
5706:
is a directed graph. The nodes represent all elements of the finite set of solutions
2369:
281:. The aim is to find an assignment, that maximizes the sum of the satisfied clauses.
32:
8211:
8181:
8163:
8079:
8487:
Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (2022-12-19).
8329:
8267:
8049:
8008:
Krentel, M. (1 August 1990). "On Finding and Verifying Locally Optimal Solutions".
7817:
5592:, and to map all other solutions for example to the standard solution returned by
8571:
8366:
8145:
7792:
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms
7474:
8455:
6991:
6982:
6699:
4114:{\displaystyle ((P_{0}\setminus p_{0})\cup p1,(P_{1}\setminus p_{1})\cup p_{0})}
7941:
7799:
7773:
7420:
Fearnley, Goldberg, Hollender and Savani proved that a complexity class called
60:
The size of every solution is polynomially bounded in the size of the instance
8415:
8398:
7666:"The complexity class Polynomial Local Search (PLS) and PLS-complete problems"
7639:
83:
It is possible to find some solution of a problem instance in polynomial time.
8579:
8522:
8424:
8321:
8029:
7746:
Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul (December 2020).
56:
A local search problem is in PLS, if the following properties are satisfied:
8313:
8249:
8061:
7904:
7182:
has been proven to be PLS-complete via a tight PLS-reduction from Min-4Sat-B
7002:
has been proven to be PLS-complete via a tight PLS-reduction from Min-4Sat-B
8473:
8232:
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing
334:
the value 0 or 1. In this case, a solution consists of 3 bits, for example
8193:
6812:
Overview of PLS-complete problems and how they are reduced to each other.
6796:
neighborhood structure has been shown to be a first PLS-complete problem.
7570:
Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988).
7406:
89:
It is possible to find all neighbors of each solution in polynomial time.
86:
It is possible to calculate the cost of each solution in polynomial time.
8351:. Lecture Notes in Computer Science. Vol. 13584. pp. 311–328.
7695:
System Sciences, 2009. HICSS'09. 42nd Hawaii International Conference on
7936:(2 ed.). John Wiley & Sons, Inc., Hoboken. pp. 435–471.
7967:"On total functions, existence theorems and computational complexity"
7516:
Local search in combinatorial optimization - Computational complexity
5008:{\displaystyle g:D_{1}\times F_{2}(f(I_{1}))\rightarrow F_{1}(I_{1})}
4171:
with the most gain of cost, or the least loss of cost, is swapped to
8514:
8021:
7932:
Angel, Eric; Christopoulos, Petros; Zissimopoulos, Vassilis (2014).
7889:
2026:{\displaystyle C:D_{L}\times F_{L}(I)\rightarrow N(I,s)\cup \{OPT\}}
1929:{\displaystyle N:D_{L}\times F_{L}(I)\rightarrow Powerset(F_{L}(I))}
1012:
is a local optimum, because none of its neighbors has better costs.
8505:
8357:
7764:
8562:
8488:
7622:
6807:
6703:
1703:{\displaystyle B:D_{L}\times F_{L}(I)\rightarrow \mathbb {R} ^{+}}
888:, if we are looking for a solution with maximum cost. Even though
8440:"Computational Complexity as an Ultimate Constraint on Evolution"
7846:
Proceedings of the 5th Scandinavian Workshop on Algorithm Theory
6692:
2396:, which is a solution with the best possible cost, is called an
93:
With these properties, it is possible to find for each solution
6031:
can be chosen, so that the following properties are satisfied:
2928:
can be achieved by negating (flipping) one arbitrary input bit
1936:
that returns the set of neighbors for an instance-solution pair
908:
is not a global optimum (which for example would be a solution
8180:
Papadimitriou, C.H.; Schäffer, A. A.; Yannakakis, M. (1990).
7689:
Dumrauf, Dominic; Monien, Burkhard; Tiemann, Karsten (2009).
7451:(2009), "Equilibria, fixed points, and complexity classes",
4238:
with the most cost, or the least loss of cost is swapped to
3881:
can be obtained by a greedy sequence of swaps from nodes in
7437:
Equilibria, fixed points, and complexity classes: a survey.
7062:
Selfish-Multi-Processor-Scheduling/k-change-with-property-t
2662:{\displaystyle V:\{0,1\}^{n}\rightarrow \{0,1,..,2^{m}-1\}}
7905:"A Linear-time Heuristic for Improving Network Partitions"
8399:"On the PLS-complexity of Maximum Constraint Assignment"
8345:"On the Impact of Player Capability on Congestion Games"
8054:
30th Annual Symposium on Foundations of Computer Science
3466:
Example neighborhood structures for problems on graphs:
538:
of each solution is the number of satisfied clauses, so
2266:), the vertices being the solutions with two solutions
8489:"The Complexity of Gradient Descent: CLS = PPAD ∩ PLS"
7333:
7270:
7118:
Asymmetric Undirected-Network-Congestion-Games/Change
6889:
has been proven to be the first PLS-complete problem.
6846:
6826:
6771:
6748:
6725:
6643:
6623:
6589:
6556:
6494:
6446:
6426:
6387:
6360:
6340:
6304:
6261:
6211:
6162:
6136:
6109:
6089:
6060:
6054:
contains, among other solutions, all local optima of
6040:
6010:
5961:
5941:
5914:
5887:
5856:
5829:
5797:
5769:
5749:
5712:
5692:
5672:
5645:
5598:
5571:
5535:
5505:
5478:
5429:
5402:
5366:
5339:
5310:
5283:
5234:
5207:
5171:
5144:
5115:
5079:
5052:
5025:
4921:
4875:
4848:
4821:
4780:
4741:
4718:
4693:
4673:
4627:
4600:
4578:
4551:
4497:
4422:
4380:
4360:
4340:
4277:
4244:
4204:
4177:
4137:
4021:
3981:
3941:
3914:
3887:
3841:
3795:
3749:
3703:
3663:
3617:
3571:
3525:
3479:
3427:
3407:
3387:
3367:
3347:
3324:
3304:
3278:
3251:
3224:
3204:
3177:
3153:
3133:
3113:
3093:
3073:
3026:
2981:
2961:
2934:
2876:
2808:
2755:
2720:
2675:
2584:
2535:
2465:
2442:
2422:
2378:
2325:
2272:
2235:
2212:
2192:
2160:
2140:
2107:
2084:
2064:
2039:
1945:
1835:
1791:
1758:
1716:
1646:
1602:
1569:
1514:
1469:
1436:
1414:
1372:
1238:
1218:
1198:
1162:
1142:
1122:
1088:
1068:
1035:
998:
945:
914:
894:
874:
824:
775:
726:
665:
645:
625:
605:
544:
510:
483:
456:
420:
393:
366:
340:
313:
307:
for that instance is a bit string that assigns every
293:
171:
147:
119:
99:
66:
7909:
Proceedings of the 19th Design Automation Conference
7212:(2, 3, 6)-Max-Constraint-Assignment-2-partite/Change
7206:(3, 2, 3)-Max-Constraint-Assignment-3-partite/Change
2522:{\displaystyle S:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}
7965:Megiddo, Nimrod; Papadimitriou, Christos H (1991).
7842:"On the hardness of global and local approximation"
7131:
Symmetric Distance-Bounded-Network-Congestion-Games
7104:
Asymmetric Directed-Network-Congestion-Games/Change
592:because the second and third clause are satisfied.
8546:"Equilibria, fixed points, and complexity classes"
7389:
7319:
6864:
6832:
6777:
6754:
6731:
6656:
6629:
6609:
6575:
6542:
6480:
6432:
6412:
6373:
6346:
6326:
6290:
6245:
6197:
6148:
6122:
6095:
6073:
6046:
6023:
5996:
5947:
5927:
5900:
5869:
5842:
5815:
5775:
5755:
5734:
5698:
5678:
5658:
5611:
5584:
5557:
5518:
5491:
5464:
5415:
5388:
5352:
5323:
5296:
5269:
5220:
5193:
5157:
5128:
5101:
5065:
5038:
5007:
4907:
4861:
4834:
4786:
4747:
4724:
4704:
4679:
4659:
4613:
4584:
4564:
4529:
4483:
4408:
4366:
4346:
4315:
4257:
4230:
4190:
4163:
4113:
4007:
3967:
3927:
3900:
3873:
3827:
3781:
3729:
3689:
3649:
3603:
3557:
3511:
3454:
3413:
3393:
3373:
3353:
3330:
3310:
3284:
3264:
3237:
3210:
3190:
3159:
3139:
3119:
3099:
3079:
3053:
3008:
2967:
2947:
2920:
2847:
2794:
2741:
2706:
2661:
2570:
2521:
2448:
2428:
2384:
2357:
2311:
2248:
2218:
2198:
2178:
2146:
2126:
2090:
2070:
2050:
2025:
1928:
1819:
1777:
1744:
1702:
1630:
1588:
1555:
1497:
1455:
1420:
1400:
1350:
1224:
1204:
1184:
1148:
1128:
1101:
1074:
1041:
1004:
984:
931:
900:
880:
858:
809:
760:
710:
651:
631:
611:
584:
523:
496:
469:
442:
406:
379:
352:
326:
299:
273:
153:
125:
105:
72:
7022:Maximum-Weighted-Subgraph-with-property-P/Change.
7006:/Flip to Min-Independent-Dominating-Set-B/k-Flip.
5529:It is sufficient to only map the local optima of
3519:of nodes in a graph is a neighbor of a partition
619:is reached by flipping one bit of the bit string
7721:Michiels, Wil; Aarts, Emile; Korst, Jan (2010).
7019:Maximum-Weighted-Subgraph-with-property-P/Change
4771:in the number of different costs of a solution.
8343:Yang, Yichen; Jia, Kai; Rinard, Martin (2022).
6205:can be constructed in polynomial time, so that
1939:There is a polynomial time computable function
1829:There is a polynomial time computable function
1640:There is a polynomial time computable function
1508:There is a polynomial time computable function
1015:Intuitively it can be argued that this problem
7518:. Princeton University Press. pp. 19–55.
6816:Optimization-Problem/Neighborhood structure.
4332:Consider the following computational problem:
2416:(also called Local-Opt ): Given two integers
868:There are no neighbors with better costs than
7400:Finding a local fitness peak in a biological
6978:Max-Uniform-Graph-Partitioning/Kernighan-Lin.
6909:Positive-not-all-equal-max-3Sat/Kernighan-Lin
6420:, but all internal path vertices are outside
4794:, which is polynomial bounded by definition.
8:
7186:/Flip to Min-0-1-Integer Programming/k-Flip.
7015:is claimed to be PLS-complete without proof.
6996:is claimed to be PLS-complete without proof.
6672:PLS lies between the functional versions of
2695:
2682:
2656:
2616:
2604:
2591:
2510:
2497:
2485:
2472:
2020:
2008:
1345:
1280:
705:
687:
8397:Dumrauf, Dominic; Monien, Burkhard (2013).
8095:"Finding optimal subgraphs by local search"
7903:Fiduccia, C. M.; Mattheyses, R. M. (1982).
7691:"Multiprocessor Scheduling is PLS-Complete"
6959:is stated to be PLS-complete without proof.
6880:Notation: Problem / Neighborhood structure
6765:every problem in PLS can be PLS-reduced to
6698:It is also proven that if a PLS problem is
4869:if there are two polynomial time functions
4842:is PLS-reducible to a local search problem
4123:Kernighan–Lin heuristic for graph partition
1556:{\displaystyle A:D_{L}\rightarrow F_{L}(I)}
7224:(4, 3, 3)-Max-Constraint-Assignment/Change
7218:(6, 2, 2)-Max-Constraint-Assignment/Change
4767:The run time of the standard algorithm is
4484:{\displaystyle c_{L}(I,s')\geq c_{L}(I,s)}
450:is the set of all possible assignments of
8561:
8504:
8463:
8414:
8356:
8303:
8239:
8135:
8110:
7992:
7982:
7763:
7725:. Springer Science & Business Media.
7621:
7587:
7464:
7381:
7356:
7332:
7293:
7269:
7107:Directed-Network-Congestion-Games/Change.
6845:
6825:
6770:
6747:
6724:
6648:
6642:
6622:
6599:
6594:
6588:
6567:
6555:
6531:
6518:
6499:
6493:
6463:
6445:
6425:
6398:
6386:
6365:
6359:
6339:
6315:
6303:
6277:
6266:
6260:
6222:
6210:
6186:
6167:
6161:
6135:
6114:
6108:
6088:
6065:
6059:
6039:
6015:
6009:
5985:
5966:
5960:
5940:
5919:
5913:
5892:
5886:
5861:
5855:
5834:
5828:
5796:
5768:
5748:
5717:
5711:
5691:
5671:
5650:
5644:
5603:
5597:
5576:
5570:
5546:
5534:
5510:
5504:
5483:
5477:
5453:
5440:
5428:
5407:
5401:
5377:
5365:
5344:
5338:
5315:
5309:
5288:
5282:
5258:
5245:
5233:
5212:
5206:
5182:
5170:
5149:
5143:
5120:
5114:
5090:
5078:
5057:
5051:
5030:
5024:
4996:
4983:
4964:
4945:
4932:
4920:
4899:
4886:
4874:
4853:
4847:
4826:
4820:
4779:
4740:
4717:
4692:
4672:
4626:
4605:
4599:
4577:
4556:
4550:
4496:
4460:
4427:
4421:
4391:
4379:
4359:
4339:
4304:
4291:
4276:
4249:
4243:
4222:
4209:
4203:
4182:
4176:
4155:
4142:
4136:
4102:
4086:
4073:
4045:
4032:
4020:
3999:
3986:
3980:
3959:
3946:
3940:
3919:
3913:
3892:
3886:
3862:
3849:
3840:
3816:
3803:
3794:
3770:
3757:
3748:
3721:
3708:
3702:
3681:
3668:
3662:
3638:
3625:
3616:
3592:
3579:
3570:
3546:
3533:
3524:
3500:
3487:
3478:
3426:
3406:
3386:
3366:
3346:
3323:
3303:
3277:
3256:
3250:
3229:
3223:
3203:
3182:
3176:
3152:
3132:
3112:
3092:
3072:
3025:
2980:
2960:
2939:
2933:
2912:
2887:
2875:
2807:
2754:
2719:
2698:
2674:
2644:
2607:
2583:
2562:
2546:
2534:
2513:
2488:
2464:
2441:
2421:
2377:
2324:
2294:
2271:
2240:
2234:
2211:
2191:
2159:
2139:
2118:
2106:
2083:
2063:
2038:
1969:
1956:
1944:
1908:
1859:
1846:
1834:
1796:
1790:
1769:
1757:
1727:
1715:
1694:
1690:
1689:
1670:
1657:
1645:
1613:
1601:
1580:
1568:
1538:
1525:
1513:
1480:
1468:
1447:
1435:
1413:
1383:
1371:
1330:
1311:
1262:
1249:
1237:
1217:
1197:
1167:
1161:
1141:
1121:
1093:
1087:
1067:
1034:
997:
950:
944:
913:
893:
873:
829:
823:
780:
774:
731:
725:
664:
644:
624:
604:
549:
543:
515:
509:
488:
482:
461:
455:
425:
419:
398:
392:
371:
365:
339:
318:
312:
292:
262:
249:
227:
214:
192:
179:
170:
146:
118:
98:
65:
8285:
8283:
8281:
8279:
8277:
8225:
8223:
8221:
8175:
8173:
8050:"Structure in locally optimal solutions"
8043:
8041:
8039:
7565:
7563:
7561:
7559:
7557:
7555:
7509:
7507:
7091:Symmetric General-Congestion-Game/Change
6668:Relationship to other complexity classes
5763:is the length of the shortest path from
4908:{\displaystyle f:D_{1}\rightarrow D_{2}}
711:{\displaystyle N(I,000)=\{100,010,001\}}
31:that models the difficulty of finding a
8392:
8390:
8388:
8386:
7871:
7869:
7867:
7865:
7863:
7861:
7859:
7857:
7855:
7835:
7833:
7831:
7829:
7827:
7752:Journal of Computer and System Sciences
7716:
7714:
7712:
7710:
7708:
7706:
7704:
7684:
7682:
7680:
7678:
7659:
7657:
7576:Journal of Computer and System Sciences
7553:
7551:
7549:
7547:
7545:
7543:
7541:
7539:
7537:
7535:
7505:
7503:
7501:
7499:
7497:
7495:
7493:
7491:
7489:
7487:
7483:
7000:Min-Independent-Dominating-Set-B/k-Flip
6440:, then for the corresponding solutions
5472:has to be a local optimum for instance
4079:
4038:
414:with the value 0. The set of solutions
7785:
7783:
7601:
7599:
7390:{\displaystyle S:^{3}\rightarrow ^{3}}
8128:CiE 2010: Programs, Proofs, Processes
7609:Discrete & Computational Geometry
7416:Relations to other complexity classes
4667:. If such a solution exists, replace
2262:
1408:is polynomial bounded in the size of
1109:of instances which are encoded using
360:, which stands for the assignment of
44:optimum instead of a global optimum.
7:
6902:Positive-not-all-equal-max-3Sat/Flip
6543:{\displaystyle p_{0}=g(I_{1},q_{0})}
2033:that returns a neighboring solution
8182:"On the complexity of local search"
7723:Theoretical aspects of local search
7200:(p, q, r)-Max-Constraint-Assignment
1156:there exists a finite solution set
939:that satisfies all clauses and has
8544:Yannakakis, Mihalis (2009-05-01).
7320:{\displaystyle V:^{3}\rightarrow }
7260:(finding the ɛ local optimum of a
4374:, find a locally optimal solution
2571:{\displaystyle S(0^{n})\neq 0^{n}}
1123:
242:
207:
14:
4015:are swapped, where the partition
3272:is a solution where every bit of
2921:{\displaystyle s=x_{1},...,x_{n}}
2870:- The neighborhood of a solution
7424:is equal to the intersection of
7232:Nearest-Colorful-Polytope/Change
7054:Local-Multi-Processor-Scheduling
6788:The optimization version of the
5360:is a local optimum for instance
2848:{\displaystyle V(S(x))\leq V(x)}
2707:{\displaystyle x\in \{0,1\}^{n}}
2319:connected by a directed arc iff
2312:{\displaystyle s,s'\in F_{L}(I)}
585:{\displaystyle c_{L}(I,s=000)=2}
141:Consider the following instance
6865:{\displaystyle Q:L\leftarrow Q}
4712:and repeat step 2, else return
4316:{\displaystyle s=(P_{0},P_{1})}
2859:Example neighborhood structures
2206:is a local optimal solution of
2058:with better cost than solution
1710:that returns for each solution
1563:that returns for each instance
21:computational complexity theory
7748:"Unique end of potential line"
7378:
7365:
7362:
7353:
7340:
7314:
7302:
7299:
7290:
7277:
7249:Weighted-3Dimensional-Matching
6973:Max-Uniform-Graph-Partitioning
6964:Max-Uniform-Graph-Partitioning
6955:Max-Uniform-Graph-Partitioning
6946:Max-Uniform-Graph-Partitioning
6856:
6537:
6511:
6475:
6456:
6321:
6308:
6283:
6270:
6234:
6215:
6198:{\displaystyle I_{2}=f(I_{1})}
6192:
6179:
5997:{\displaystyle I_{2}=f(I_{1})}
5991:
5978:
5810:
5798:
5787:Definition Tight PLS-reduction
5729:
5723:
5552:
5539:
5465:{\displaystyle g(I_{1},s_{2})}
5459:
5433:
5383:
5370:
5270:{\displaystyle g(I_{1},s_{2})}
5264:
5238:
5188:
5175:
5096:
5083:
5002:
4989:
4976:
4973:
4970:
4957:
4951:
4892:
4654:
4642:
4524:
4512:
4478:
4466:
4450:
4433:
4403:
4397:
4310:
4284:
4231:{\displaystyle p_{1}\in P_{1}}
4164:{\displaystyle p_{0}\in P_{0}}
4108:
4092:
4066:
4051:
4025:
4022:
4008:{\displaystyle p_{1}\in P_{1}}
3968:{\displaystyle p_{0}\in P_{0}}
3868:
3842:
3822:
3796:
3776:
3750:
3730:{\displaystyle p_{1}\in P_{1}}
3690:{\displaystyle p_{0}\in P_{0}}
3644:
3618:
3598:
3572:
3552:
3526:
3506:
3480:
3443:
3431:
3042:
3030:
3003:
2991:
2842:
2836:
2827:
2824:
2818:
2812:
2789:
2783:
2774:
2771:
2765:
2759:
2730:
2724:
2613:
2552:
2539:
2494:
2352:
2340:
2306:
2300:
2173:
2161:
2002:
1990:
1984:
1981:
1975:
1923:
1920:
1914:
1901:
1874:
1871:
1865:
1814:
1802:
1739:
1733:
1685:
1682:
1676:
1625:
1619:
1550:
1544:
1531:
1505:are polynomial time verifiable
1492:
1486:
1395:
1389:
1342:
1336:
1295:
1283:
1274:
1268:
1179:
1173:
1054:becomes PLS-complete (below).
973:
956:
859:{\displaystyle c_{L}(I,001)=2}
847:
835:
810:{\displaystyle c_{L}(I,010)=2}
798:
786:
761:{\displaystyle c_{L}(I,100)=2}
749:
737:
681:
669:
573:
555:
437:
431:
268:
239:
233:
204:
198:
172:
1:
8112:10.1016/S0304-3975(96)00135-1
7170:Overlay-Network-Design/Change
6820:PLS-reduction from a problem
6800:List of PLS-complete Problems
4409:{\displaystyle s\in F_{L}(I)}
3874:{\displaystyle (P_{2},P_{3})}
3828:{\displaystyle (P_{0},P_{1})}
3782:{\displaystyle (P_{2},P_{3})}
3650:{\displaystyle (P_{0},P_{1})}
3604:{\displaystyle (P_{2},P_{3})}
3558:{\displaystyle (P_{0},P_{1})}
3512:{\displaystyle (P_{2},P_{3})}
1745:{\displaystyle s\in F_{L}(I)}
1631:{\displaystyle s\in F_{L}(I)}
1498:{\displaystyle s\in F_{L}(I)}
1401:{\displaystyle s\in F_{L}(I)}
985:{\displaystyle c_{L}(I,s')=3}
8572:10.1016/j.cosrev.2009.03.004
8367:10.1007/978-3-031-15714-1_18
8146:10.1007/978-3-642-13962-8_15
8099:Theoretical Computer Science
8093:Shimozono, Shinichi (1997).
7994:10.1016/0304-3975(91)90200-L
7971:Theoretical Computer Science
7589:10.1016/0022-0000(88)90046-3
7514:Yannakakis, Mihalis (2003).
7475:10.1016/j.cosrev.2009.03.004
7327:and a neighborhood function
6481:{\displaystyle p=g(I_{1},q)}
6413:{\displaystyle q,q_{0}\in R}
6334:contains a direct path from
6291:{\displaystyle T_{f(I_{1})}}
6246:{\displaystyle g(I_{1},q)=p}
5823:from a local search problem
4660:{\displaystyle s'\in N(I,s)}
4572:to find an initial solution
4530:{\displaystyle s'\in N(I,s)}
3455:{\displaystyle H(s,r)\leq k}
2795:{\displaystyle S(S(x))=S(x)}
2358:{\displaystyle s'\in N(I,s)}
1212:be the relation that models
8456:10.1534/genetics.119.302000
8438:Kaznatcheev, Artem (2019).
7572:"How easy is local search?"
7191:Max-0-1-Integer Programming
7178:Min-0-1-Integer Programming
5635:Definition Transition graph
3935:. This means the two nodes
3009:{\displaystyle r\in N(I,s)}
2154:exactly contains the pairs
1366:The size of every solution
23:, Polynomial Local Search (
8616:
7942:10.1002/9781119005353.ch14
7800:10.1137/1.9781611973082.62
7774:10.1016/j.jcss.2020.05.007
7157:Market-Sharing-Game/Change
6898:is complete by definition.
6691:PLS also is a subclass of
5850:to a local search problem
4621:to find a better solution
3318:is a neighbor of solution
3087:is a neighbor of solution
2742:{\displaystyle S(x)\neq x}
2127:{\displaystyle I\in D_{L}}
1820:{\displaystyle c_{L}(I,s)}
1778:{\displaystyle I\in D_{L}}
1589:{\displaystyle I\in D_{L}}
1456:{\displaystyle I\in D_{L}}
718:with the following costs:
8416:10.1016/j.tcs.2012.10.044
8234:. ACM. pp. 604–612.
8048:Krentel, Mark W. (1989).
8010:SIAM Journal on Computing
7878:SIAM Journal on Computing
7640:10.1007/s00454-018-9979-y
7238:Stable-Configuration/Flip
6610:{\displaystyle T_{I_{1}}}
5955:of solutions of instance
7840:Klauck, Hartmut (1996).
7664:Borzechowski, Michaela.
7011:Weighted-Independent-Set
6327:{\displaystyle f(I_{1})}
6255:If the transition graph
5735:{\displaystyle F_{L}(I)}
5558:{\displaystyle f(I_{1})}
5389:{\displaystyle f(I_{1})}
5194:{\displaystyle f(I_{1})}
5102:{\displaystyle f(I_{1})}
3054:{\displaystyle H(s,r)=1}
2256:has the structure of an
1185:{\displaystyle F_{L}(I)}
443:{\displaystyle F_{L}(I)}
8550:Computer Science Review
8349:Algorithmic Game Theory
8314:10.1145/1455248.1455249
8250:10.1145/1007352.1007445
8062:10.1109/SFCS.1989.63481
7453:Computer Science Review
7144:2-Threshold-Game/Change
7076:General-Congestion-Game
6719:A local search problem
6576:{\displaystyle p=p_{0}}
5565:to the local optima of
4815:A local search problem
1129:{\displaystyle \Sigma }
1062:A local search problem
7391:
7321:
7262:λ-Lipschitz continuous
6877:
6866:
6834:
6779:
6756:
6733:
6658:
6631:
6617:contains an edge from
6611:
6577:
6544:
6482:
6434:
6414:
6375:
6348:
6328:
6292:
6247:
6199:
6150:
6149:{\displaystyle q\in R}
6124:
6097:
6075:
6048:
6025:
5998:
5949:
5929:
5902:
5871:
5844:
5817:
5777:
5757:
5736:
5700:
5680:
5660:
5613:
5586:
5559:
5520:
5493:
5466:
5417:
5390:
5354:
5325:
5298:
5271:
5222:
5195:
5159:
5130:
5103:
5067:
5040:
5009:
4909:
4863:
4836:
4788:
4749:
4726:
4706:
4681:
4661:
4615:
4586:
4566:
4531:
4485:
4410:
4368:
4348:
4328:The standard Algorithm
4317:
4259:
4232:
4192:
4165:
4115:
4009:
3969:
3929:
3902:
3875:
3829:
3783:
3731:
3691:
3651:
3605:
3559:
3513:
3456:
3415:
3395:
3375:
3355:
3332:
3312:
3286:
3266:
3239:
3212:
3192:
3161:
3141:
3121:
3101:
3081:
3055:
3010:
2975:and all its neighbors
2969:
2949:
2922:
2849:
2796:
2743:
2708:
2663:
2572:
2523:
2450:
2430:
2404:Alternative Definition
2386:
2359:
2313:
2250:
2220:
2200:
2180:
2148:
2128:
2092:
2072:
2052:
2027:
1930:
1821:
1779:
1746:
1704:
1632:
1590:
1557:
1499:
1457:
1422:
1402:
1352:
1226:
1206:
1186:
1150:
1130:
1103:
1076:
1043:
1006:
986:
933:
932:{\displaystyle s'=111}
902:
882:
860:
811:
762:
712:
653:
639:, so the neighbors of
633:
613:
586:
525:
498:
471:
444:
408:
381:
354:
328:
301:
275:
155:
127:
107:
74:
8194:10.1145/100216.100274
7392:
7322:
7165:pure Nash Equilibrium
7152:pure Nash Equilibrium
7139:pure Nash Equilibrium
7126:pure Nash Equilibrium
7113:pure Nash Equilibrium
7099:pure Nash Equilibrium
7086:pure Nash Equilibrium
7070:pure Nash Equilibrium
6867:
6835:
6811:
6780:
6757:
6734:
6659:
6657:{\displaystyle p_{0}}
6632:
6612:
6578:
6545:
6483:
6435:
6415:
6376:
6374:{\displaystyle q_{0}}
6349:
6329:
6293:
6248:
6200:
6151:
6125:
6123:{\displaystyle I_{1}}
6098:
6076:
6074:{\displaystyle I_{2}}
6049:
6026:
6024:{\displaystyle L_{2}}
5999:
5950:
5930:
5928:{\displaystyle L_{1}}
5903:
5901:{\displaystyle I_{1}}
5872:
5870:{\displaystyle L_{2}}
5845:
5843:{\displaystyle L_{1}}
5818:
5816:{\displaystyle (f,g)}
5778:
5758:
5737:
5701:
5681:
5661:
5659:{\displaystyle T_{I}}
5639:The transition graph
5614:
5612:{\displaystyle A_{1}}
5587:
5585:{\displaystyle I_{1}}
5560:
5521:
5519:{\displaystyle L_{1}}
5494:
5492:{\displaystyle I_{1}}
5467:
5418:
5416:{\displaystyle L_{2}}
5391:
5355:
5353:{\displaystyle s_{2}}
5326:
5324:{\displaystyle L_{1}}
5299:
5297:{\displaystyle I_{1}}
5272:
5223:
5221:{\displaystyle L_{2}}
5196:
5160:
5158:{\displaystyle s_{2}}
5131:
5129:{\displaystyle L_{2}}
5104:
5068:
5066:{\displaystyle L_{1}}
5041:
5039:{\displaystyle I_{1}}
5010:
4910:
4864:
4862:{\displaystyle L_{2}}
4837:
4835:{\displaystyle L_{1}}
4789:
4750:
4727:
4707:
4682:
4662:
4616:
4614:{\displaystyle C_{L}}
4587:
4567:
4565:{\displaystyle A_{L}}
4532:
4486:
4411:
4369:
4349:
4318:
4260:
4258:{\displaystyle P_{0}}
4233:
4193:
4191:{\displaystyle P_{1}}
4166:
4116:
4010:
3970:
3930:
3928:{\displaystyle P_{1}}
3903:
3901:{\displaystyle P_{0}}
3876:
3830:
3784:
3732:
3692:
3657:by swapping one node
3652:
3611:can be obtained from
3606:
3560:
3514:
3457:
3416:
3396:
3376:
3356:
3333:
3313:
3287:
3267:
3265:{\displaystyle s_{i}}
3240:
3238:{\displaystyle s_{1}}
3213:
3193:
3191:{\displaystyle s_{1}}
3162:
3142:
3127:can be obtained from
3122:
3102:
3082:
3056:
3011:
2970:
2950:
2948:{\displaystyle x_{i}}
2923:
2850:
2797:
2744:
2709:
2664:
2573:
2524:
2451:
2431:
2387:
2360:
2314:
2251:
2249:{\displaystyle D_{L}}
2221:
2201:
2181:
2179:{\displaystyle (I,s)}
2149:
2129:
2093:
2073:
2053:
2028:
1931:
1822:
1780:
1747:
1705:
1633:
1591:
1558:
1500:
1458:
1423:
1403:
1353:
1227:
1207:
1187:
1151:
1131:
1104:
1102:{\displaystyle D_{L}}
1077:
1044:
1007:
987:
934:
903:
883:
861:
812:
763:
713:
654:
634:
614:
587:
526:
524:{\displaystyle x_{3}}
499:
497:{\displaystyle x_{2}}
472:
470:{\displaystyle x_{1}}
445:
409:
407:{\displaystyle x_{3}}
382:
380:{\displaystyle x_{1}}
355:
353:{\displaystyle s=000}
329:
327:{\displaystyle x_{i}}
302:
276:
156:
128:
108:
75:
8188:. pp. 438–445.
8056:. pp. 216–221.
7331:
7268:
6886:Min/Max-circuit/Flip
6876:Tight PLS-reduction.
6844:
6824:
6769:
6746:
6739:is PLS-complete, if
6723:
6641:
6621:
6587:
6554:
6492:
6444:
6424:
6385:
6358:
6338:
6302:
6259:
6209:
6160:
6134:
6107:
6087:
6058:
6038:
6008:
5959:
5939:
5912:
5885:
5881:if for any instance
5854:
5827:
5795:
5767:
5747:
5710:
5690:
5670:
5643:
5596:
5569:
5533:
5503:
5476:
5427:
5400:
5364:
5337:
5308:
5281:
5232:
5205:
5169:
5142:
5113:
5077:
5050:
5023:
4919:
4873:
4846:
4819:
4778:
4739:
4716:
4691:
4671:
4625:
4598:
4576:
4549:
4495:
4420:
4378:
4358:
4338:
4334:Given some instance
4275:
4242:
4202:
4175:
4135:
4019:
3979:
3939:
3912:
3885:
3839:
3793:
3747:
3701:
3661:
3615:
3569:
3523:
3477:
3425:
3405:
3385:
3365:
3345:
3322:
3302:
3276:
3249:
3222:
3202:
3175:
3151:
3131:
3111:
3091:
3071:
3024:
2979:
2959:
2932:
2874:
2806:
2753:
2718:
2673:
2582:
2533:
2463:
2440:
2420:
2376:
2323:
2270:
2233:
2210:
2190:
2158:
2138:
2105:
2082:
2062:
2037:
1943:
1833:
1789:
1756:
1714:
1644:
1600:
1567:
1512:
1467:
1434:
1412:
1370:
1236:
1216:
1196:
1160:
1140:
1136:. For each instance
1120:
1086:
1066:
1033:
996:
943:
912:
892:
872:
822:
773:
724:
663:
643:
623:
603:
542:
508:
481:
454:
418:
391:
364:
338:
311:
291:
169:
145:
133:is a local optimum.
117:
97:
64:
37:optimization problem
7632:2014arXiv1412.3347M
7449:Yannakakis, Mihalis
7264:objective function
6957:/Fiduccia-Matheyses
6939:Max-4Sat-(B=3)/Flip
6083:For every solution
5879:tight PLS-reduction
5630:Tight PLS-reduction
5622:PLS-reductions are
3245:, and so on, until
2101:For every instance
1049:in exactly one bit.
8600:Complexity classes
8493:Journal of the ACM
8403:Theor. Comput. Sci
7402:fitness landscapes
7397:) is PLS-complete.
7387:
7317:
6878:
6862:
6830:
6792:problem under the
6775:
6752:
6729:
6654:
6627:
6607:
6573:
6540:
6478:
6430:
6410:
6371:
6344:
6324:
6288:
6243:
6195:
6146:
6120:
6093:
6071:
6044:
6021:
5994:
5945:
5925:
5898:
5867:
5840:
5813:
5773:
5753:
5732:
5696:
5676:
5656:
5609:
5582:
5555:
5516:
5489:
5462:
5413:
5386:
5350:
5321:
5294:
5277:is a solution for
5267:
5218:
5191:
5165:is a solution for
5155:
5126:
5109:is an instance of
5099:
5063:
5046:is an instance of
5036:
5005:
4905:
4859:
4832:
4784:
4758:Linear programming
4745:
4722:
4705:{\displaystyle s'}
4702:
4677:
4657:
4611:
4582:
4562:
4527:
4481:
4406:
4364:
4344:
4313:
4255:
4228:
4188:
4161:
4129:Fiduccia-Matheyses
4111:
4005:
3965:
3925:
3898:
3871:
3825:
3779:
3727:
3687:
3647:
3601:
3555:
3509:
3452:
3411:
3391:
3371:
3351:
3328:
3308:
3282:
3262:
3235:
3208:
3188:
3157:
3137:
3117:
3097:
3077:
3051:
3006:
2965:
2955:. So one solution
2945:
2918:
2845:
2792:
2739:
2704:
2659:
2568:
2519:
2446:
2426:
2398:exact neighborhood
2382:
2355:
2309:
2246:
2216:
2196:
2176:
2144:
2124:
2098:is locally optimal
2088:
2068:
2051:{\displaystyle s'}
2048:
2023:
1926:
1817:
1775:
1742:
1700:
1628:
1586:
1553:
1495:
1453:
1430:Problem instances
1418:
1398:
1348:
1222:
1202:
1182:
1146:
1126:
1099:
1072:
1039:
1002:
982:
929:
898:
878:
856:
807:
758:
708:
649:
629:
609:
582:
521:
494:
467:
440:
404:
377:
350:
324:
297:
271:
151:
123:
103:
70:
8376:978-3-031-15713-4
8298:(6): 25:1–25:22.
8155:978-3-642-13961-1
7809:978-0-89871-993-2
7404:specified by the
6833:{\displaystyle L}
6778:{\displaystyle L}
6755:{\displaystyle L}
6732:{\displaystyle L}
6630:{\displaystyle p}
6433:{\displaystyle R}
6347:{\displaystyle q}
6096:{\displaystyle p}
6047:{\displaystyle R}
5948:{\displaystyle R}
5776:{\displaystyle v}
5756:{\displaystyle v}
5699:{\displaystyle L}
5679:{\displaystyle I}
4787:{\displaystyle s}
4769:pseudo-polynomial
4762:Simplex algorithm
4748:{\displaystyle L}
4725:{\displaystyle s}
4680:{\displaystyle s}
4585:{\displaystyle s}
4367:{\displaystyle L}
4354:of a PLS problem
4347:{\displaystyle I}
3789:is a neighbor of
3414:{\displaystyle k}
3394:{\displaystyle r}
3374:{\displaystyle s}
3354:{\displaystyle H}
3331:{\displaystyle s}
3311:{\displaystyle r}
3285:{\displaystyle s}
3211:{\displaystyle s}
3160:{\displaystyle s}
3140:{\displaystyle s}
3120:{\displaystyle r}
3100:{\displaystyle s}
3080:{\displaystyle r}
2968:{\displaystyle s}
2449:{\displaystyle m}
2429:{\displaystyle n}
2385:{\displaystyle s}
2219:{\displaystyle I}
2199:{\displaystyle s}
2147:{\displaystyle R}
2091:{\displaystyle s}
2078:, or states that
2071:{\displaystyle s}
1421:{\displaystyle I}
1225:{\displaystyle L}
1205:{\displaystyle R}
1149:{\displaystyle I}
1075:{\displaystyle L}
1058:Formal Definition
1042:{\displaystyle s}
1005:{\displaystyle s}
901:{\displaystyle s}
881:{\displaystyle s}
652:{\displaystyle s}
632:{\displaystyle s}
612:{\displaystyle s}
300:{\displaystyle s}
154:{\displaystyle I}
126:{\displaystyle s}
106:{\displaystyle s}
73:{\displaystyle I}
8607:
8584:
8583:
8565:
8541:
8535:
8534:
8508:
8484:
8478:
8477:
8467:
8435:
8429:
8428:
8418:
8394:
8381:
8380:
8360:
8340:
8334:
8333:
8307:
8287:
8272:
8271:
8243:
8227:
8216:
8215:
8177:
8168:
8167:
8139:
8123:
8117:
8116:
8114:
8090:
8084:
8083:
8045:
8034:
8033:
8005:
7999:
7998:
7996:
7986:
7962:
7956:
7955:
7929:
7923:
7922:
7900:
7894:
7893:
7873:
7850:
7849:
7837:
7822:
7821:
7787:
7778:
7777:
7767:
7743:
7737:
7736:
7718:
7699:
7698:
7686:
7673:
7672:
7670:
7661:
7652:
7651:
7625:
7603:
7594:
7593:
7591:
7567:
7530:
7529:
7511:
7477:
7468:
7396:
7394:
7393:
7388:
7386:
7385:
7361:
7360:
7326:
7324:
7323:
7318:
7298:
7297:
7242:Hopfield network
7185:
7005:
6871:
6869:
6868:
6863:
6839:
6837:
6836:
6831:
6784:
6782:
6781:
6776:
6761:
6759:
6758:
6753:
6738:
6736:
6735:
6730:
6710:PLS-completeness
6663:
6661:
6660:
6655:
6653:
6652:
6636:
6634:
6633:
6628:
6616:
6614:
6613:
6608:
6606:
6605:
6604:
6603:
6582:
6580:
6579:
6574:
6572:
6571:
6549:
6547:
6546:
6541:
6536:
6535:
6523:
6522:
6504:
6503:
6487:
6485:
6484:
6479:
6468:
6467:
6439:
6437:
6436:
6431:
6419:
6417:
6416:
6411:
6403:
6402:
6380:
6378:
6377:
6372:
6370:
6369:
6353:
6351:
6350:
6345:
6333:
6331:
6330:
6325:
6320:
6319:
6297:
6295:
6294:
6289:
6287:
6286:
6282:
6281:
6252:
6250:
6249:
6244:
6227:
6226:
6204:
6202:
6201:
6196:
6191:
6190:
6172:
6171:
6155:
6153:
6152:
6147:
6129:
6127:
6126:
6121:
6119:
6118:
6102:
6100:
6099:
6094:
6080:
6078:
6077:
6072:
6070:
6069:
6053:
6051:
6050:
6045:
6030:
6028:
6027:
6022:
6020:
6019:
6003:
6001:
6000:
5995:
5990:
5989:
5971:
5970:
5954:
5952:
5951:
5946:
5934:
5932:
5931:
5926:
5924:
5923:
5907:
5905:
5904:
5899:
5897:
5896:
5876:
5874:
5873:
5868:
5866:
5865:
5849:
5847:
5846:
5841:
5839:
5838:
5822:
5820:
5819:
5814:
5791:A PLS-reduction
5782:
5780:
5779:
5774:
5762:
5760:
5759:
5754:
5741:
5739:
5738:
5733:
5722:
5721:
5705:
5703:
5702:
5697:
5685:
5683:
5682:
5677:
5665:
5663:
5662:
5657:
5655:
5654:
5618:
5616:
5615:
5610:
5608:
5607:
5591:
5589:
5588:
5583:
5581:
5580:
5564:
5562:
5561:
5556:
5551:
5550:
5525:
5523:
5522:
5517:
5515:
5514:
5498:
5496:
5495:
5490:
5488:
5487:
5471:
5469:
5468:
5463:
5458:
5457:
5445:
5444:
5422:
5420:
5419:
5414:
5412:
5411:
5395:
5393:
5392:
5387:
5382:
5381:
5359:
5357:
5356:
5351:
5349:
5348:
5330:
5328:
5327:
5322:
5320:
5319:
5303:
5301:
5300:
5295:
5293:
5292:
5276:
5274:
5273:
5268:
5263:
5262:
5250:
5249:
5227:
5225:
5224:
5219:
5217:
5216:
5200:
5198:
5197:
5192:
5187:
5186:
5164:
5162:
5161:
5156:
5154:
5153:
5135:
5133:
5132:
5127:
5125:
5124:
5108:
5106:
5105:
5100:
5095:
5094:
5072:
5070:
5069:
5064:
5062:
5061:
5045:
5043:
5042:
5037:
5035:
5034:
5014:
5012:
5011:
5006:
5001:
5000:
4988:
4987:
4969:
4968:
4950:
4949:
4937:
4936:
4914:
4912:
4911:
4906:
4904:
4903:
4891:
4890:
4868:
4866:
4865:
4860:
4858:
4857:
4841:
4839:
4838:
4833:
4831:
4830:
4793:
4791:
4790:
4785:
4754:
4752:
4751:
4746:
4731:
4729:
4728:
4723:
4711:
4709:
4708:
4703:
4701:
4686:
4684:
4683:
4678:
4666:
4664:
4663:
4658:
4635:
4620:
4618:
4617:
4612:
4610:
4609:
4591:
4589:
4588:
4583:
4571:
4569:
4568:
4563:
4561:
4560:
4536:
4534:
4533:
4528:
4505:
4490:
4488:
4487:
4482:
4465:
4464:
4449:
4432:
4431:
4415:
4413:
4412:
4407:
4396:
4395:
4373:
4371:
4370:
4365:
4353:
4351:
4350:
4345:
4322:
4320:
4319:
4314:
4309:
4308:
4296:
4295:
4264:
4262:
4261:
4256:
4254:
4253:
4237:
4235:
4234:
4229:
4227:
4226:
4214:
4213:
4198:, then the node
4197:
4195:
4194:
4189:
4187:
4186:
4170:
4168:
4167:
4162:
4160:
4159:
4147:
4146:
4120:
4118:
4117:
4112:
4107:
4106:
4091:
4090:
4078:
4077:
4050:
4049:
4037:
4036:
4014:
4012:
4011:
4006:
4004:
4003:
3991:
3990:
3974:
3972:
3971:
3966:
3964:
3963:
3951:
3950:
3934:
3932:
3931:
3926:
3924:
3923:
3907:
3905:
3904:
3899:
3897:
3896:
3880:
3878:
3877:
3872:
3867:
3866:
3854:
3853:
3834:
3832:
3831:
3826:
3821:
3820:
3808:
3807:
3788:
3786:
3785:
3780:
3775:
3774:
3762:
3761:
3736:
3734:
3733:
3728:
3726:
3725:
3713:
3712:
3696:
3694:
3693:
3688:
3686:
3685:
3673:
3672:
3656:
3654:
3653:
3648:
3643:
3642:
3630:
3629:
3610:
3608:
3607:
3602:
3597:
3596:
3584:
3583:
3564:
3562:
3561:
3556:
3551:
3550:
3538:
3537:
3518:
3516:
3515:
3510:
3505:
3504:
3492:
3491:
3461:
3459:
3458:
3453:
3420:
3418:
3417:
3412:
3400:
3398:
3397:
3392:
3380:
3378:
3377:
3372:
3360:
3358:
3357:
3352:
3340:Hamming distance
3337:
3335:
3334:
3329:
3317:
3315:
3314:
3309:
3291:
3289:
3288:
3283:
3271:
3269:
3268:
3263:
3261:
3260:
3244:
3242:
3241:
3236:
3234:
3233:
3217:
3215:
3214:
3209:
3197:
3195:
3194:
3189:
3187:
3186:
3166:
3164:
3163:
3158:
3146:
3144:
3143:
3138:
3126:
3124:
3123:
3118:
3106:
3104:
3103:
3098:
3086:
3084:
3083:
3078:
3060:
3058:
3057:
3052:
3018:Hamming distance
3015:
3013:
3012:
3007:
2974:
2972:
2971:
2966:
2954:
2952:
2951:
2946:
2944:
2943:
2927:
2925:
2924:
2919:
2917:
2916:
2892:
2891:
2854:
2852:
2851:
2846:
2801:
2799:
2798:
2793:
2748:
2746:
2745:
2740:
2713:
2711:
2710:
2705:
2703:
2702:
2669:, find a vertex
2668:
2666:
2665:
2660:
2649:
2648:
2612:
2611:
2577:
2575:
2574:
2569:
2567:
2566:
2551:
2550:
2528:
2526:
2525:
2520:
2518:
2517:
2493:
2492:
2458:Boolean circuits
2455:
2453:
2452:
2447:
2435:
2433:
2432:
2427:
2391:
2389:
2388:
2383:
2364:
2362:
2361:
2356:
2333:
2318:
2316:
2315:
2310:
2299:
2298:
2286:
2263:Transition graph
2255:
2253:
2252:
2247:
2245:
2244:
2225:
2223:
2222:
2217:
2205:
2203:
2202:
2197:
2185:
2183:
2182:
2177:
2153:
2151:
2150:
2145:
2133:
2131:
2130:
2125:
2123:
2122:
2097:
2095:
2094:
2089:
2077:
2075:
2074:
2069:
2057:
2055:
2054:
2049:
2047:
2032:
2030:
2029:
2024:
1974:
1973:
1961:
1960:
1935:
1933:
1932:
1927:
1913:
1912:
1864:
1863:
1851:
1850:
1826:
1824:
1823:
1818:
1801:
1800:
1784:
1782:
1781:
1776:
1774:
1773:
1751:
1749:
1748:
1743:
1732:
1731:
1709:
1707:
1706:
1701:
1699:
1698:
1693:
1675:
1674:
1662:
1661:
1637:
1635:
1634:
1629:
1618:
1617:
1595:
1593:
1592:
1587:
1585:
1584:
1562:
1560:
1559:
1554:
1543:
1542:
1530:
1529:
1504:
1502:
1501:
1496:
1485:
1484:
1462:
1460:
1459:
1454:
1452:
1451:
1427:
1425:
1424:
1419:
1407:
1405:
1404:
1399:
1388:
1387:
1357:
1355:
1354:
1349:
1335:
1334:
1316:
1315:
1267:
1266:
1254:
1253:
1231:
1229:
1228:
1223:
1211:
1209:
1208:
1203:
1191:
1189:
1188:
1183:
1172:
1171:
1155:
1153:
1152:
1147:
1135:
1133:
1132:
1127:
1108:
1106:
1105:
1100:
1098:
1097:
1081:
1079:
1078:
1073:
1048:
1046:
1045:
1040:
1011:
1009:
1008:
1003:
991:
989:
988:
983:
972:
955:
954:
938:
936:
935:
930:
922:
907:
905:
904:
899:
887:
885:
884:
879:
865:
863:
862:
857:
834:
833:
816:
814:
813:
808:
785:
784:
767:
765:
764:
759:
736:
735:
717:
715:
714:
709:
658:
656:
655:
650:
638:
636:
635:
630:
618:
616:
615:
610:
591:
589:
588:
583:
554:
553:
530:
528:
527:
522:
520:
519:
503:
501:
500:
495:
493:
492:
476:
474:
473:
468:
466:
465:
449:
447:
446:
441:
430:
429:
413:
411:
410:
405:
403:
402:
386:
384:
383:
378:
376:
375:
359:
357:
356:
351:
333:
331:
330:
325:
323:
322:
306:
304:
303:
298:
280:
278:
277:
272:
267:
266:
254:
253:
232:
231:
219:
218:
197:
196:
184:
183:
160:
158:
157:
152:
132:
130:
129:
124:
112:
110:
109:
104:
79:
77:
76:
71:
29:complexity class
16:Complexity class
8615:
8614:
8610:
8609:
8608:
8606:
8605:
8604:
8590:
8589:
8588:
8587:
8543:
8542:
8538:
8515:10.1145/3568163
8499:(1): 7:1–7:74.
8486:
8485:
8481:
8437:
8436:
8432:
8396:
8395:
8384:
8377:
8342:
8341:
8337:
8305:10.1.1.634.4913
8289:
8288:
8275:
8260:
8229:
8228:
8219:
8204:
8179:
8178:
8171:
8156:
8137:10.1.1.762.6801
8125:
8124:
8120:
8092:
8091:
8087:
8072:
8047:
8046:
8037:
8022:10.1137/0219052
8007:
8006:
8002:
7964:
7963:
7959:
7952:
7931:
7930:
7926:
7919:
7902:
7901:
7897:
7890:10.1137/0220004
7875:
7874:
7853:
7839:
7838:
7825:
7810:
7789:
7788:
7781:
7745:
7744:
7740:
7733:
7720:
7719:
7702:
7688:
7687:
7676:
7668:
7663:
7662:
7655:
7605:
7604:
7597:
7569:
7568:
7533:
7526:
7513:
7512:
7485:
7466:10.1.1.371.5034
7447:
7444:
7434:
7432:Further reading
7418:
7409:/Point-mutation
7377:
7352:
7329:
7328:
7289:
7266:
7265:
7183:
7003:
6933:Max-4Sat-B/Flip
6842:
6841:
6822:
6821:
6802:
6767:
6766:
6744:
6743:
6721:
6720:
6717:
6712:
6670:
6644:
6639:
6638:
6619:
6618:
6595:
6590:
6585:
6584:
6563:
6552:
6551:
6527:
6514:
6495:
6490:
6489:
6459:
6442:
6441:
6422:
6421:
6394:
6383:
6382:
6361:
6356:
6355:
6336:
6335:
6311:
6300:
6299:
6273:
6262:
6257:
6256:
6218:
6207:
6206:
6182:
6163:
6158:
6157:
6132:
6131:
6110:
6105:
6104:
6085:
6084:
6061:
6056:
6055:
6036:
6035:
6011:
6006:
6005:
5981:
5962:
5957:
5956:
5937:
5936:
5915:
5910:
5909:
5888:
5883:
5882:
5857:
5852:
5851:
5830:
5825:
5824:
5793:
5792:
5789:
5765:
5764:
5745:
5744:
5713:
5708:
5707:
5688:
5687:
5668:
5667:
5666:of an instance
5646:
5641:
5640:
5637:
5632:
5599:
5594:
5593:
5572:
5567:
5566:
5542:
5531:
5530:
5506:
5501:
5500:
5479:
5474:
5473:
5449:
5436:
5425:
5424:
5403:
5398:
5397:
5373:
5362:
5361:
5340:
5335:
5334:
5311:
5306:
5305:
5284:
5279:
5278:
5254:
5241:
5230:
5229:
5208:
5203:
5202:
5178:
5167:
5166:
5145:
5140:
5139:
5116:
5111:
5110:
5086:
5075:
5074:
5053:
5048:
5047:
5026:
5021:
5020:
4992:
4979:
4960:
4941:
4928:
4917:
4916:
4895:
4882:
4871:
4870:
4849:
4844:
4843:
4822:
4817:
4816:
4813:
4800:
4776:
4775:
4737:
4736:
4714:
4713:
4694:
4689:
4688:
4669:
4668:
4628:
4623:
4622:
4601:
4596:
4595:
4574:
4573:
4552:
4547:
4546:
4498:
4493:
4492:
4456:
4442:
4423:
4418:
4417:
4387:
4376:
4375:
4356:
4355:
4336:
4335:
4330:
4300:
4287:
4273:
4272:
4245:
4240:
4239:
4218:
4205:
4200:
4199:
4178:
4173:
4172:
4151:
4138:
4133:
4132:
4098:
4082:
4069:
4041:
4028:
4017:
4016:
3995:
3982:
3977:
3976:
3955:
3942:
3937:
3936:
3915:
3910:
3909:
3888:
3883:
3882:
3858:
3845:
3837:
3836:
3812:
3799:
3791:
3790:
3766:
3753:
3745:
3744:
3717:
3704:
3699:
3698:
3677:
3664:
3659:
3658:
3634:
3621:
3613:
3612:
3588:
3575:
3567:
3566:
3542:
3529:
3521:
3520:
3496:
3483:
3475:
3474:
3423:
3422:
3403:
3402:
3383:
3382:
3363:
3362:
3343:
3342:
3320:
3319:
3300:
3299:
3274:
3273:
3252:
3247:
3246:
3225:
3220:
3219:
3200:
3199:
3178:
3173:
3172:
3149:
3148:
3129:
3128:
3109:
3108:
3089:
3088:
3069:
3068:
3022:
3021:
2977:
2976:
2957:
2956:
2935:
2930:
2929:
2908:
2883:
2872:
2871:
2861:
2804:
2803:
2751:
2750:
2716:
2715:
2694:
2671:
2670:
2640:
2603:
2580:
2579:
2558:
2542:
2531:
2530:
2509:
2484:
2461:
2460:
2438:
2437:
2418:
2417:
2406:
2374:
2373:
2326:
2321:
2320:
2290:
2279:
2268:
2267:
2236:
2231:
2230:
2208:
2207:
2188:
2187:
2156:
2155:
2136:
2135:
2114:
2103:
2102:
2080:
2079:
2060:
2059:
2040:
2035:
2034:
1965:
1952:
1941:
1940:
1904:
1855:
1842:
1831:
1830:
1792:
1787:
1786:
1765:
1754:
1753:
1752:of an instance
1723:
1712:
1711:
1688:
1666:
1653:
1642:
1641:
1609:
1598:
1597:
1576:
1565:
1564:
1534:
1521:
1510:
1509:
1476:
1465:
1464:
1443:
1432:
1431:
1410:
1409:
1379:
1368:
1367:
1326:
1307:
1258:
1245:
1234:
1233:
1232:. The relation
1214:
1213:
1194:
1193:
1163:
1158:
1157:
1138:
1137:
1118:
1117:
1089:
1084:
1083:
1064:
1063:
1060:
1031:
1030:
994:
993:
965:
946:
941:
940:
915:
910:
909:
890:
889:
870:
869:
825:
820:
819:
776:
771:
770:
727:
722:
721:
661:
660:
641:
640:
621:
620:
601:
600:
545:
540:
539:
511:
506:
505:
484:
479:
478:
457:
452:
451:
421:
416:
415:
394:
389:
388:
367:
362:
361:
336:
335:
314:
309:
308:
289:
288:
258:
245:
223:
210:
188:
175:
167:
166:
143:
142:
139:
115:
114:
95:
94:
62:
61:
50:
41:polynomial time
35:solution to an
33:locally optimal
17:
12:
11:
5:
8613:
8611:
8603:
8602:
8592:
8591:
8586:
8585:
8536:
8479:
8450:(1): 245–265.
8430:
8382:
8375:
8335:
8273:
8259:978-1581138528
8258:
8217:
8202:
8169:
8154:
8118:
8105:(1): 265–271.
8085:
8070:
8035:
8016:(4): 742–749.
8000:
7984:10.1.1.75.4797
7977:(2): 317–324.
7957:
7950:
7924:
7917:
7895:
7851:
7823:
7808:
7779:
7738:
7731:
7700:
7674:
7653:
7616:(3): 720–755.
7595:
7531:
7524:
7482:
7481:
7480:
7479:
7443:
7440:
7439:
7438:
7433:
7430:
7417:
7414:
7413:
7412:
7398:
7384:
7380:
7376:
7373:
7370:
7367:
7364:
7359:
7355:
7351:
7348:
7345:
7342:
7339:
7336:
7316:
7313:
7310:
7307:
7304:
7301:
7296:
7292:
7288:
7285:
7282:
7279:
7276:
7273:
7258:Real-Local-Opt
7254:
7245:
7235:
7229:
7228:
7227:
7221:
7215:
7209:
7196:
7187:
7174:
7160:
7147:
7134:
7121:
7108:
7094:
7081:
7065:
7059:
7050:
7047:/Lin-Kernighan
7041:
7032:
7023:
7016:
7007:
6997:
6994:/Kernighan-Lin
6988:
6979:
6975:/Kernighan-Lin
6969:
6960:
6951:
6942:
6936:
6930:
6921:
6912:
6906:
6899:
6890:
6861:
6858:
6855:
6852:
6849:
6829:
6801:
6798:
6786:
6785:
6774:
6763:
6751:
6728:
6716:
6713:
6711:
6708:
6669:
6666:
6665:
6664:
6651:
6647:
6626:
6602:
6598:
6593:
6570:
6566:
6562:
6559:
6539:
6534:
6530:
6526:
6521:
6517:
6513:
6510:
6507:
6502:
6498:
6477:
6474:
6471:
6466:
6462:
6458:
6455:
6452:
6449:
6429:
6409:
6406:
6401:
6397:
6393:
6390:
6368:
6364:
6343:
6323:
6318:
6314:
6310:
6307:
6285:
6280:
6276:
6272:
6269:
6265:
6253:
6242:
6239:
6236:
6233:
6230:
6225:
6221:
6217:
6214:
6194:
6189:
6185:
6181:
6178:
6175:
6170:
6166:
6145:
6142:
6139:
6117:
6113:
6092:
6081:
6068:
6064:
6043:
6018:
6014:
5993:
5988:
5984:
5980:
5977:
5974:
5969:
5965:
5944:
5922:
5918:
5895:
5891:
5864:
5860:
5837:
5833:
5812:
5809:
5806:
5803:
5800:
5788:
5785:
5772:
5752:
5731:
5728:
5725:
5720:
5716:
5695:
5675:
5653:
5649:
5636:
5633:
5631:
5628:
5606:
5602:
5579:
5575:
5554:
5549:
5545:
5541:
5538:
5527:
5526:
5513:
5509:
5486:
5482:
5461:
5456:
5452:
5448:
5443:
5439:
5435:
5432:
5410:
5406:
5385:
5380:
5376:
5372:
5369:
5347:
5343:
5331:
5318:
5314:
5291:
5287:
5266:
5261:
5257:
5253:
5248:
5244:
5240:
5237:
5215:
5211:
5190:
5185:
5181:
5177:
5174:
5152:
5148:
5136:
5123:
5119:
5098:
5093:
5089:
5085:
5082:
5060:
5056:
5033:
5029:
5004:
4999:
4995:
4991:
4986:
4982:
4978:
4975:
4972:
4967:
4963:
4959:
4956:
4953:
4948:
4944:
4940:
4935:
4931:
4927:
4924:
4902:
4898:
4894:
4889:
4885:
4881:
4878:
4856:
4852:
4829:
4825:
4812:
4809:
4807:PLS-complete.
4799:
4796:
4783:
4744:
4733:
4732:
4721:
4700:
4697:
4676:
4656:
4653:
4650:
4647:
4644:
4641:
4638:
4634:
4631:
4608:
4604:
4594:Use algorithm
4592:
4581:
4559:
4555:
4526:
4523:
4520:
4517:
4514:
4511:
4508:
4504:
4501:
4480:
4477:
4474:
4471:
4468:
4463:
4459:
4455:
4452:
4448:
4445:
4441:
4438:
4435:
4430:
4426:
4405:
4402:
4399:
4394:
4390:
4386:
4383:
4363:
4343:
4329:
4326:
4325:
4324:
4312:
4307:
4303:
4299:
4294:
4290:
4286:
4283:
4280:
4266:
4252:
4248:
4225:
4221:
4217:
4212:
4208:
4185:
4181:
4158:
4154:
4150:
4145:
4141:
4126:
4110:
4105:
4101:
4097:
4094:
4089:
4085:
4081:
4076:
4072:
4068:
4065:
4062:
4059:
4056:
4053:
4048:
4044:
4040:
4035:
4031:
4027:
4024:
4002:
3998:
3994:
3989:
3985:
3962:
3958:
3954:
3949:
3945:
3922:
3918:
3908:with nodes in
3895:
3891:
3870:
3865:
3861:
3857:
3852:
3848:
3844:
3824:
3819:
3815:
3811:
3806:
3802:
3798:
3778:
3773:
3769:
3765:
3760:
3756:
3752:
3743:- A partition
3738:
3724:
3720:
3716:
3711:
3707:
3684:
3680:
3676:
3671:
3667:
3646:
3641:
3637:
3633:
3628:
3624:
3620:
3600:
3595:
3591:
3587:
3582:
3578:
3574:
3554:
3549:
3545:
3541:
3536:
3532:
3528:
3508:
3503:
3499:
3495:
3490:
3486:
3482:
3473:- A partition
3464:
3463:
3451:
3448:
3445:
3442:
3439:
3436:
3433:
3430:
3410:
3390:
3370:
3350:
3327:
3307:
3293:
3281:
3259:
3255:
3232:
3228:
3207:
3185:
3181:
3156:
3136:
3116:
3096:
3076:
3062:
3050:
3047:
3044:
3041:
3038:
3035:
3032:
3029:
3005:
3002:
2999:
2996:
2993:
2990:
2987:
2984:
2964:
2942:
2938:
2915:
2911:
2907:
2904:
2901:
2898:
2895:
2890:
2886:
2882:
2879:
2860:
2857:
2844:
2841:
2838:
2835:
2832:
2829:
2826:
2823:
2820:
2817:
2814:
2811:
2791:
2788:
2785:
2782:
2779:
2776:
2773:
2770:
2767:
2764:
2761:
2758:
2738:
2735:
2732:
2729:
2726:
2723:
2701:
2697:
2693:
2690:
2687:
2684:
2681:
2678:
2658:
2655:
2652:
2647:
2643:
2639:
2636:
2633:
2630:
2627:
2624:
2621:
2618:
2615:
2610:
2606:
2602:
2599:
2596:
2593:
2590:
2587:
2565:
2561:
2557:
2554:
2549:
2545:
2541:
2538:
2516:
2512:
2508:
2505:
2502:
2499:
2496:
2491:
2487:
2483:
2480:
2477:
2474:
2471:
2468:
2445:
2425:
2405:
2402:
2394:global optimum
2381:
2372:is a solution
2354:
2351:
2348:
2345:
2342:
2339:
2336:
2332:
2329:
2308:
2305:
2302:
2297:
2293:
2289:
2285:
2282:
2278:
2275:
2258:implicit graph
2243:
2239:
2227:
2226:
2215:
2195:
2175:
2172:
2169:
2166:
2163:
2143:
2121:
2117:
2113:
2110:
2099:
2087:
2067:
2046:
2043:
2022:
2019:
2016:
2013:
2010:
2007:
2004:
2001:
1998:
1995:
1992:
1989:
1986:
1983:
1980:
1977:
1972:
1968:
1964:
1959:
1955:
1951:
1948:
1937:
1925:
1922:
1919:
1916:
1911:
1907:
1903:
1900:
1897:
1894:
1891:
1888:
1885:
1882:
1879:
1876:
1873:
1870:
1867:
1862:
1858:
1854:
1849:
1845:
1841:
1838:
1827:
1816:
1813:
1810:
1807:
1804:
1799:
1795:
1772:
1768:
1764:
1761:
1741:
1738:
1735:
1730:
1726:
1722:
1719:
1697:
1692:
1687:
1684:
1681:
1678:
1673:
1669:
1665:
1660:
1656:
1652:
1649:
1638:
1627:
1624:
1621:
1616:
1612:
1608:
1605:
1596:some solution
1583:
1579:
1575:
1572:
1552:
1549:
1546:
1541:
1537:
1533:
1528:
1524:
1520:
1517:
1506:
1494:
1491:
1488:
1483:
1479:
1475:
1472:
1463:and solutions
1450:
1446:
1442:
1439:
1428:
1417:
1397:
1394:
1391:
1386:
1382:
1378:
1375:
1347:
1344:
1341:
1338:
1333:
1329:
1325:
1322:
1319:
1314:
1310:
1306:
1303:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1273:
1270:
1265:
1261:
1257:
1252:
1248:
1244:
1241:
1221:
1201:
1181:
1178:
1175:
1170:
1166:
1145:
1125:
1113:over a finite
1096:
1092:
1071:
1059:
1056:
1051:
1050:
1038:
1027:
1024:
1001:
981:
978:
975:
971:
968:
964:
961:
958:
953:
949:
928:
925:
921:
918:
897:
877:
855:
852:
849:
846:
843:
840:
837:
832:
828:
806:
803:
800:
797:
794:
791:
788:
783:
779:
757:
754:
751:
748:
745:
742:
739:
734:
730:
707:
704:
701:
698:
695:
692:
689:
686:
683:
680:
677:
674:
671:
668:
648:
628:
608:
599:of a solution
581:
578:
575:
572:
569:
566:
563:
560:
557:
552:
548:
518:
514:
491:
487:
464:
460:
439:
436:
433:
428:
424:
401:
397:
374:
370:
349:
346:
343:
321:
317:
296:
270:
265:
261:
257:
252:
248:
244:
241:
238:
235:
230:
226:
222:
217:
213:
209:
206:
203:
200:
195:
191:
187:
182:
178:
174:
150:
138:
135:
122:
102:
91:
90:
87:
84:
81:
69:
49:
46:
15:
13:
10:
9:
6:
4:
3:
2:
8612:
8601:
8598:
8597:
8595:
8581:
8577:
8573:
8569:
8564:
8559:
8555:
8551:
8547:
8540:
8537:
8532:
8528:
8524:
8520:
8516:
8512:
8507:
8502:
8498:
8494:
8490:
8483:
8480:
8475:
8471:
8466:
8461:
8457:
8453:
8449:
8445:
8441:
8434:
8431:
8426:
8422:
8417:
8412:
8408:
8404:
8400:
8393:
8391:
8389:
8387:
8383:
8378:
8372:
8368:
8364:
8359:
8354:
8350:
8346:
8339:
8336:
8331:
8327:
8323:
8319:
8315:
8311:
8306:
8301:
8297:
8293:
8286:
8284:
8282:
8280:
8278:
8274:
8269:
8265:
8261:
8255:
8251:
8247:
8242:
8241:10.1.1.3.7861
8237:
8233:
8226:
8224:
8222:
8218:
8213:
8209:
8205:
8199:
8195:
8191:
8187:
8183:
8176:
8174:
8170:
8165:
8161:
8157:
8151:
8147:
8143:
8138:
8133:
8129:
8122:
8119:
8113:
8108:
8104:
8100:
8096:
8089:
8086:
8081:
8077:
8073:
8071:0-8186-1982-1
8067:
8063:
8059:
8055:
8051:
8044:
8042:
8040:
8036:
8031:
8027:
8023:
8019:
8015:
8011:
8004:
8001:
7995:
7990:
7985:
7980:
7976:
7972:
7968:
7961:
7958:
7953:
7951:9781119005353
7947:
7943:
7939:
7935:
7928:
7925:
7920:
7918:9780897910200
7914:
7910:
7906:
7899:
7896:
7891:
7887:
7883:
7879:
7872:
7870:
7868:
7866:
7864:
7862:
7860:
7858:
7856:
7852:
7847:
7843:
7836:
7834:
7832:
7830:
7828:
7824:
7819:
7815:
7811:
7805:
7801:
7797:
7793:
7786:
7784:
7780:
7775:
7771:
7766:
7761:
7757:
7753:
7749:
7742:
7739:
7734:
7732:9783642071485
7728:
7724:
7717:
7715:
7713:
7711:
7709:
7707:
7705:
7701:
7696:
7692:
7685:
7683:
7681:
7679:
7675:
7667:
7660:
7658:
7654:
7649:
7645:
7641:
7637:
7633:
7629:
7624:
7619:
7615:
7611:
7610:
7602:
7600:
7596:
7590:
7585:
7582:(1): 79–100.
7581:
7577:
7573:
7566:
7564:
7562:
7560:
7558:
7556:
7554:
7552:
7550:
7548:
7546:
7544:
7542:
7540:
7538:
7536:
7532:
7527:
7525:9780691115221
7521:
7517:
7510:
7508:
7506:
7504:
7502:
7500:
7498:
7496:
7494:
7492:
7490:
7488:
7484:
7476:
7472:
7467:
7462:
7458:
7454:
7450:
7446:
7445:
7441:
7436:
7435:
7431:
7429:
7427:
7423:
7415:
7410:
7408:
7403:
7399:
7382:
7374:
7371:
7368:
7357:
7349:
7346:
7343:
7337:
7334:
7311:
7308:
7305:
7294:
7286:
7283:
7280:
7274:
7271:
7263:
7259:
7255:
7252:
7250:
7246:
7243:
7239:
7236:
7233:
7230:
7225:
7222:
7219:
7216:
7213:
7210:
7207:
7204:
7203:
7202:
7201:
7197:
7194:
7192:
7188:
7181:
7179:
7175:
7171:
7167:
7166:
7161:
7158:
7154:
7153:
7148:
7145:
7141:
7140:
7135:
7132:
7128:
7127:
7122:
7119:
7115:
7114:
7109:
7105:
7101:
7100:
7095:
7092:
7088:
7087:
7082:
7079:
7077:
7072:
7071:
7066:
7063:
7060:
7057:
7055:
7051:
7048:
7046:
7042:
7039:
7037:
7033:
7030:
7028:
7024:
7020:
7017:
7014:
7012:
7008:
7001:
6998:
6995:
6993:
6989:
6986:
6984:
6980:
6976:
6974:
6970:
6967:
6965:
6961:
6958:
6956:
6952:
6949:
6947:
6943:
6940:
6937:
6934:
6931:
6928:
6926:
6922:
6919:
6917:
6913:
6910:
6907:
6903:
6900:
6897:
6896:
6891:
6888:
6887:
6883:
6882:
6881:
6875:
6859:
6853:
6850:
6847:
6840:to a problem
6827:
6819:
6818:Dotted arrow:
6815:
6810:
6806:
6799:
6797:
6795:
6791:
6772:
6764:
6749:
6742:
6741:
6740:
6726:
6714:
6709:
6707:
6705:
6701:
6696:
6694:
6689:
6687:
6683:
6679:
6675:
6667:
6649:
6645:
6624:
6600:
6596:
6591:
6568:
6564:
6560:
6557:
6550:holds either
6532:
6528:
6524:
6519:
6515:
6508:
6505:
6500:
6496:
6472:
6469:
6464:
6460:
6453:
6450:
6447:
6427:
6407:
6404:
6399:
6395:
6391:
6388:
6366:
6362:
6341:
6316:
6312:
6305:
6278:
6274:
6267:
6263:
6254:
6240:
6237:
6231:
6228:
6223:
6219:
6212:
6187:
6183:
6176:
6173:
6168:
6164:
6143:
6140:
6137:
6130:, a solution
6115:
6111:
6090:
6082:
6066:
6062:
6041:
6034:
6033:
6032:
6016:
6012:
5986:
5982:
5975:
5972:
5967:
5963:
5942:
5920:
5916:
5893:
5889:
5880:
5862:
5858:
5835:
5831:
5807:
5804:
5801:
5786:
5784:
5770:
5750:
5726:
5718:
5714:
5693:
5686:of a problem
5673:
5651:
5647:
5634:
5629:
5627:
5625:
5620:
5604:
5600:
5577:
5573:
5547:
5543:
5536:
5511:
5507:
5484:
5480:
5454:
5450:
5446:
5441:
5437:
5430:
5408:
5404:
5378:
5374:
5367:
5345:
5341:
5332:
5316:
5312:
5289:
5285:
5259:
5255:
5251:
5246:
5242:
5235:
5213:
5209:
5183:
5179:
5172:
5150:
5146:
5137:
5121:
5117:
5091:
5087:
5080:
5058:
5054:
5031:
5027:
5018:
5017:
5016:
4997:
4993:
4984:
4980:
4965:
4961:
4954:
4946:
4942:
4938:
4933:
4929:
4925:
4922:
4900:
4896:
4887:
4883:
4879:
4876:
4854:
4850:
4827:
4823:
4811:PLS-reduction
4810:
4808:
4805:
4797:
4795:
4781:
4772:
4770:
4765:
4763:
4759:
4742:
4719:
4698:
4695:
4674:
4651:
4648:
4645:
4639:
4636:
4632:
4629:
4606:
4602:
4593:
4579:
4557:
4553:
4544:
4543:
4542:
4539:
4537:
4521:
4518:
4515:
4509:
4506:
4502:
4499:
4475:
4472:
4469:
4461:
4457:
4453:
4446:
4443:
4439:
4436:
4428:
4424:
4400:
4392:
4388:
4384:
4381:
4361:
4341:
4327:
4305:
4301:
4297:
4292:
4288:
4281:
4278:
4270:
4267:
4250:
4246:
4223:
4219:
4215:
4210:
4206:
4183:
4179:
4156:
4152:
4148:
4143:
4139:
4130:
4127:
4124:
4103:
4099:
4095:
4087:
4083:
4074:
4070:
4063:
4060:
4057:
4054:
4046:
4042:
4033:
4029:
4000:
3996:
3992:
3987:
3983:
3960:
3956:
3952:
3947:
3943:
3920:
3916:
3893:
3889:
3863:
3859:
3855:
3850:
3846:
3817:
3813:
3809:
3804:
3800:
3771:
3767:
3763:
3758:
3754:
3742:
3741:Kernighan-Lin
3739:
3722:
3718:
3714:
3709:
3705:
3682:
3678:
3674:
3669:
3665:
3639:
3635:
3631:
3626:
3622:
3593:
3589:
3585:
3580:
3576:
3547:
3543:
3539:
3534:
3530:
3501:
3497:
3493:
3488:
3484:
3472:
3469:
3468:
3467:
3449:
3446:
3440:
3437:
3434:
3428:
3408:
3388:
3368:
3348:
3341:
3325:
3305:
3298:- A solution
3297:
3294:
3279:
3257:
3253:
3230:
3226:
3205:
3183:
3179:
3170:
3154:
3134:
3114:
3094:
3074:
3067:- A solution
3066:
3065:Kernighan-Lin
3063:
3048:
3045:
3039:
3036:
3033:
3027:
3019:
3000:
2997:
2994:
2988:
2985:
2982:
2962:
2940:
2936:
2913:
2909:
2905:
2902:
2899:
2896:
2893:
2888:
2884:
2880:
2877:
2869:
2866:
2865:
2864:
2858:
2856:
2839:
2833:
2830:
2821:
2815:
2809:
2786:
2780:
2777:
2768:
2762:
2756:
2736:
2733:
2727:
2721:
2699:
2691:
2688:
2685:
2679:
2676:
2653:
2650:
2645:
2641:
2637:
2634:
2631:
2628:
2625:
2622:
2619:
2608:
2600:
2597:
2594:
2588:
2585:
2563:
2559:
2555:
2547:
2543:
2536:
2514:
2506:
2503:
2500:
2489:
2481:
2478:
2475:
2469:
2466:
2459:
2443:
2423:
2415:
2411:
2403:
2401:
2399:
2395:
2379:
2371:
2370:local optimum
2366:
2349:
2346:
2343:
2337:
2334:
2330:
2327:
2303:
2295:
2291:
2287:
2283:
2280:
2276:
2273:
2265:
2264:
2260:(also called
2259:
2241:
2237:
2213:
2193:
2170:
2167:
2164:
2141:
2119:
2115:
2111:
2108:
2100:
2085:
2065:
2044:
2041:
2017:
2014:
2011:
2005:
1999:
1996:
1993:
1987:
1978:
1970:
1966:
1962:
1957:
1953:
1949:
1946:
1938:
1917:
1909:
1905:
1898:
1895:
1892:
1889:
1886:
1883:
1880:
1877:
1868:
1860:
1856:
1852:
1847:
1843:
1839:
1836:
1828:
1811:
1808:
1805:
1797:
1793:
1770:
1766:
1762:
1759:
1736:
1728:
1724:
1720:
1717:
1695:
1679:
1671:
1667:
1663:
1658:
1654:
1650:
1647:
1639:
1622:
1614:
1610:
1606:
1603:
1581:
1577:
1573:
1570:
1547:
1539:
1535:
1526:
1522:
1518:
1515:
1507:
1489:
1481:
1477:
1473:
1470:
1448:
1444:
1440:
1437:
1429:
1415:
1392:
1384:
1380:
1376:
1373:
1365:
1364:
1363:
1361:
1339:
1331:
1327:
1323:
1320:
1317:
1312:
1308:
1304:
1301:
1298:
1292:
1289:
1286:
1277:
1271:
1263:
1259:
1255:
1250:
1246:
1242:
1239:
1219:
1199:
1176:
1168:
1164:
1143:
1116:
1112:
1094:
1090:
1069:
1057:
1055:
1036:
1028:
1025:
1022:
1021:
1020:
1018:
1013:
999:
979:
976:
969:
966:
962:
959:
951:
947:
926:
923:
919:
916:
895:
875:
866:
853:
850:
844:
841:
838:
830:
826:
817:
804:
801:
795:
792:
789:
781:
777:
768:
755:
752:
746:
743:
740:
732:
728:
719:
702:
699:
696:
693:
690:
684:
678:
675:
672:
666:
646:
626:
606:
598:
593:
579:
576:
570:
567:
564:
561:
558:
550:
546:
537:
532:
516:
512:
489:
485:
462:
458:
434:
426:
422:
399:
395:
372:
368:
347:
344:
341:
319:
315:
294:
287:
282:
263:
259:
255:
250:
246:
236:
228:
224:
220:
215:
211:
201:
193:
189:
185:
180:
176:
164:
148:
136:
134:
120:
100:
88:
85:
82:
67:
59:
58:
57:
54:
47:
45:
42:
38:
34:
30:
26:
22:
8556:(2): 71–85.
8553:
8549:
8539:
8496:
8492:
8482:
8447:
8443:
8433:
8406:
8402:
8348:
8338:
8295:
8291:
8231:
8185:
8127:
8121:
8102:
8098:
8088:
8053:
8013:
8009:
8003:
7974:
7970:
7960:
7933:
7927:
7908:
7898:
7884:(1): 56–87.
7881:
7877:
7845:
7791:
7755:
7751:
7741:
7722:
7694:
7613:
7607:
7579:
7575:
7515:
7459:(2): 71–85,
7456:
7452:
7419:
7405:
7257:
7256:The problem
7251:/(p, q)-Swap
7247:
7237:
7231:
7223:
7217:
7211:
7205:
7198:
7189:
7176:
7169:
7163:
7156:
7150:
7143:
7137:
7130:
7124:
7117:
7111:
7103:
7097:
7090:
7084:
7074:
7068:
7061:
7052:
7043:
7034:
7025:
7018:
7009:
6999:
6990:
6981:
6971:
6962:
6953:
6944:
6938:
6932:
6923:
6914:
6908:
6901:
6892:
6884:
6879:
6874:Black arrow:
6873:
6817:
6813:
6803:
6793:
6787:
6718:
6702:, then NP =
6697:
6690:
6671:
5878:
5790:
5638:
5621:
5528:
4814:
4801:
4773:
4766:
4734:
4540:
4333:
4331:
4268:
4128:
3740:
3697:with a node
3470:
3465:
3295:
3168:
3064:
2867:
2862:
2409:
2407:
2397:
2367:
2261:
2229:An instance
2228:
1359:
1061:
1052:
1016:
1014:
867:
818:
769:
720:
596:
594:
535:
533:
285:
283:
140:
92:
55:
51:
24:
18:
7911:: 175–181.
7794:: 790–804.
5935:, a subset
5015:such that:
3401:is at most
2749:and either
1019:, because:
1017:lies in PLS
48:Description
8506:2011.01929
8358:2205.09905
8203:0897913612
7765:1811.03841
7442:References
7162:Finding a
7149:Finding a
7136:Finding a
7123:Finding a
7110:Finding a
7096:Finding a
7083:Finding a
7067:Finding a
7045:Metric-TSP
7036:Metric-TSP
6925:Min-4Sat-B
6715:Definition
5624:transitive
4798:Reductions
4416:such that
3171:-neighbor
2714:such that
2529:such that
2408:The class
1082:has a set
8580:1574-0137
8563:0802.2831
8531:263706261
8523:0004-5411
8425:0304-3975
8409:: 24–52.
8322:0004-5411
8300:CiteSeerX
8236:CiteSeerX
8132:CiteSeerX
8030:0097-5397
7979:CiteSeerX
7648:254024141
7623:1412.3347
7461:CiteSeerX
7428:and PLS.
7363:→
7300:→
7056:/k-change
7038:/k-Change
7029:/k-change
7027:Set-Cover
6857:←
6762:is in PLS
6405:∈
6141:∈
4977:→
4939:×
4893:→
4804:Reduction
4637:∈
4507:∈
4454:≥
4385:∈
4216:∈
4149:∈
4096:∪
4080:∖
4055:∪
4039:∖
3993:∈
3953:∈
3715:∈
3675:∈
3447:≤
2986:∈
2831:≤
2734:≠
2680:∈
2651:−
2614:→
2556:≠
2495:→
2335:∈
2288:∈
2112:∈
2006:∪
1985:→
1963:×
1875:→
1853:×
1785:the cost
1763:∈
1721:∈
1686:→
1664:×
1607:∈
1574:∈
1532:→
1474:∈
1441:∈
1377:∈
1324:∈
1305:∈
1299:∣
1256:×
1243:⊆
1124:Σ
595:The Flip-
256:∨
243:¬
237:∧
221:∨
208:¬
202:∧
186:∨
165:Problem:
8594:Category
8474:30833289
8444:Genetics
8212:16877206
8164:14099014
8080:32686790
7848:: 88–99.
7758:: 1–35.
7407:NK-model
6966:/FM-Swap
6916:Max-2Sat
6893:Sink-of-
6684:⊆ PLS ⊆
4699:′
4633:′
4503:′
4491:for all
4447:′
3361:between
2456:and two
2331:′
2284:′
2045:′
1115:alphabet
970:′
920:′
597:neighbor
286:solution
163:Max-2Sat
8465:6499524
8330:3070710
8268:1037326
7818:2056144
7697:: 1–10.
7628:Bibcode
7193:/k-Flip
7180:/k-Flip
7078:/Change
7013:/Change
6992:Max-Cut
6983:Max-Cut
6814:Syntax:
6790:circuit
6700:NP-hard
5423:, then
5228:, then
5073:, then
4760:is the
4269:FM-Swap
3338:if the
1111:strings
161:of the
137:Example
27:) is a
8578:
8529:
8521:
8472:
8462:
8423:
8373:
8328:
8320:
8302:
8292:J. ACM
8266:
8256:
8238:
8210:
8200:
8162:
8152:
8134:
8078:
8068:
8028:
7981:
7948:
7915:
7816:
7806:
7729:
7646:
7522:
7463:
7173:tight.
7168:in an
7116:in an
7102:in an
6381:, and
3296:k-Flip
3167:, the
2186:where
1358:is in
1192:. Let
8558:arXiv
8527:S2CID
8501:arXiv
8353:arXiv
8326:S2CID
8264:S2CID
8208:S2CID
8160:S2CID
8076:S2CID
7814:S2CID
7760:arXiv
7669:(PDF)
7644:S2CID
7618:arXiv
7240:in a
7142:in a
7129:in a
7089:in a
7073:in a
6985:/Flip
6948:/Swap
6927:/Flip
6918:/Flip
6704:co-NP
5877:is a
3421:, so
3020:one:
3016:have
8576:ISSN
8519:ISSN
8470:PMID
8421:ISSN
8371:ISBN
8318:ISSN
8254:ISBN
8198:ISBN
8150:ISBN
8066:ISBN
8026:ISSN
7946:ISBN
7913:ISBN
7804:ISBN
7727:ISBN
7520:ISBN
7426:PPAD
6905:too.
6794:Flip
6693:TFNP
6676:and
6488:and
4915:and
4545:Use
3975:and
3471:Swap
3381:and
3169:Flip
2868:Flip
2578:and
2436:and
1362:if:
659:are
536:cost
534:The
504:and
8568:doi
8511:doi
8460:PMC
8452:doi
8448:212
8411:doi
8407:469
8363:doi
8310:doi
8246:doi
8190:doi
8142:doi
8107:doi
8103:172
8058:doi
8018:doi
7989:doi
7938:doi
7886:doi
7796:doi
7770:doi
7756:114
7636:doi
7584:doi
7471:doi
7422:CLS
7155:in
6895:DAG
6872:.
6686:FNP
6637:to
6583:or
6354:to
6298:of
6156:of
6103:of
6004:of
5908:of
5499:of
5396:of
5333:if
5304:of
5201:of
5138:if
5019:if
4687:by
3835:if
3565:if
3198:of
3107:if
2802:or
2414:DAG
2410:PLS
1360:PLS
992:),
927:111
845:001
796:010
747:100
703:001
697:010
691:100
679:000
571:000
387:to
348:000
25:PLS
19:In
8596::
8574:.
8566:.
8552:.
8548:.
8525:.
8517:.
8509:.
8497:70
8495:.
8491:.
8468:.
8458:.
8446:.
8442:.
8419:.
8405:.
8401:.
8385:^
8369:.
8361:.
8347:.
8324:.
8316:.
8308:.
8296:55
8294:.
8276:^
8262:.
8252:.
8244:.
8220:^
8206:.
8196:.
8184:.
8172:^
8158:.
8148:.
8140:.
8101:.
8097:.
8074:.
8064:.
8052:.
8038:^
8024:.
8014:19
8012:.
7987:.
7975:81
7973:.
7969:.
7944:.
7907:.
7882:20
7880:.
7854:^
7844:.
7826:^
7812:.
7802:.
7782:^
7768:.
7754:.
7750:.
7703:^
7693:.
7677:^
7656:^
7642:.
7634:.
7626:.
7614:60
7612:.
7598:^
7580:37
7578:.
7574:.
7534:^
7486:^
7469:,
7455:,
6706:.
6688:.
6682:FP
6680::
6678:NP
5626:.
5619:.
4802:A
4764:.
4538:.
2855:.
2400:.
2368:A
2365:.
2134:,
1278::=
531:.
477:,
284:A
8582:.
8570::
8560::
8554:3
8533:.
8513::
8503::
8476:.
8454::
8427:.
8413::
8379:.
8365::
8355::
8332:.
8312::
8270:.
8248::
8214:.
8192::
8166:.
8144::
8115:.
8109::
8082:.
8060::
8032:.
8020::
7997:.
7991::
7954:.
7940::
7921:.
7892:.
7888::
7820:.
7798::
7776:.
7772::
7762::
7735:.
7671:.
7650:.
7638::
7630::
7620::
7592:.
7586::
7528:.
7478:.
7473::
7457:3
7383:3
7379:]
7375:1
7372:,
7369:0
7366:[
7358:3
7354:]
7350:1
7347:,
7344:0
7341:[
7338::
7335:S
7315:]
7312:1
7309:,
7306:0
7303:[
7295:3
7291:]
7287:1
7284:,
7281:0
7278:[
7275::
7272:V
7184:′
7004:′
6860:Q
6854:L
6851::
6848:Q
6828:L
6773:L
6750:L
6727:L
6674:P
6650:0
6646:p
6625:p
6601:1
6597:I
6592:T
6569:0
6565:p
6561:=
6558:p
6538:)
6533:0
6529:q
6525:,
6520:1
6516:I
6512:(
6509:g
6506:=
6501:0
6497:p
6476:)
6473:q
6470:,
6465:1
6461:I
6457:(
6454:g
6451:=
6448:p
6428:R
6408:R
6400:0
6396:q
6392:,
6389:q
6367:0
6363:q
6342:q
6322:)
6317:1
6313:I
6309:(
6306:f
6284:)
6279:1
6275:I
6271:(
6268:f
6264:T
6241:p
6238:=
6235:)
6232:q
6229:,
6224:1
6220:I
6216:(
6213:g
6193:)
6188:1
6184:I
6180:(
6177:f
6174:=
6169:2
6165:I
6144:R
6138:q
6116:1
6112:I
6091:p
6067:2
6063:I
6042:R
6017:2
6013:L
5992:)
5987:1
5983:I
5979:(
5976:f
5973:=
5968:2
5964:I
5943:R
5921:1
5917:L
5894:1
5890:I
5863:2
5859:L
5836:1
5832:L
5811:)
5808:g
5805:,
5802:f
5799:(
5771:v
5751:v
5730:)
5727:I
5724:(
5719:L
5715:F
5694:L
5674:I
5652:I
5648:T
5605:1
5601:A
5578:1
5574:I
5553:)
5548:1
5544:I
5540:(
5537:f
5512:1
5508:L
5485:1
5481:I
5460:)
5455:2
5451:s
5447:,
5442:1
5438:I
5434:(
5431:g
5409:2
5405:L
5384:)
5379:1
5375:I
5371:(
5368:f
5346:2
5342:s
5317:1
5313:L
5290:1
5286:I
5265:)
5260:2
5256:s
5252:,
5247:1
5243:I
5239:(
5236:g
5214:2
5210:L
5189:)
5184:1
5180:I
5176:(
5173:f
5151:2
5147:s
5122:2
5118:L
5097:)
5092:1
5088:I
5084:(
5081:f
5059:1
5055:L
5032:1
5028:I
5003:)
4998:1
4994:I
4990:(
4985:1
4981:F
4974:)
4971:)
4966:1
4962:I
4958:(
4955:f
4952:(
4947:2
4943:F
4934:1
4930:D
4926::
4923:g
4901:2
4897:D
4888:1
4884:D
4880::
4877:f
4855:2
4851:L
4828:1
4824:L
4782:s
4743:L
4720:s
4696:s
4675:s
4655:)
4652:s
4649:,
4646:I
4643:(
4640:N
4630:s
4607:L
4603:C
4580:s
4558:L
4554:A
4525:)
4522:s
4519:,
4516:I
4513:(
4510:N
4500:s
4479:)
4476:s
4473:,
4470:I
4467:(
4462:L
4458:c
4451:)
4444:s
4440:,
4437:I
4434:(
4429:L
4425:c
4404:)
4401:I
4398:(
4393:L
4389:F
4382:s
4362:L
4342:I
4311:)
4306:1
4302:P
4298:,
4293:0
4289:P
4285:(
4282:=
4279:s
4251:0
4247:P
4224:1
4220:P
4211:1
4207:p
4184:1
4180:P
4157:0
4153:P
4144:0
4140:p
4125:.
4109:)
4104:0
4100:p
4093:)
4088:1
4084:p
4075:1
4071:P
4067:(
4064:,
4061:1
4058:p
4052:)
4047:0
4043:p
4034:0
4030:P
4026:(
4023:(
4001:1
3997:P
3988:1
3984:p
3961:0
3957:P
3948:0
3944:p
3921:1
3917:P
3894:0
3890:P
3869:)
3864:3
3860:P
3856:,
3851:2
3847:P
3843:(
3823:)
3818:1
3814:P
3810:,
3805:0
3801:P
3797:(
3777:)
3772:3
3768:P
3764:,
3759:2
3755:P
3751:(
3737:.
3723:1
3719:P
3710:1
3706:p
3683:0
3679:P
3670:0
3666:p
3645:)
3640:1
3636:P
3632:,
3627:0
3623:P
3619:(
3599:)
3594:3
3590:P
3586:,
3581:2
3577:P
3573:(
3553:)
3548:1
3544:P
3540:,
3535:0
3531:P
3527:(
3507:)
3502:3
3498:P
3494:,
3489:2
3485:P
3481:(
3462:.
3450:k
3444:)
3441:r
3438:,
3435:s
3432:(
3429:H
3409:k
3389:r
3369:s
3349:H
3326:s
3306:r
3280:s
3258:i
3254:s
3231:1
3227:s
3206:s
3184:1
3180:s
3155:s
3135:s
3115:r
3095:s
3075:r
3061:.
3049:1
3046:=
3043:)
3040:r
3037:,
3034:s
3031:(
3028:H
3004:)
3001:s
2998:,
2995:I
2992:(
2989:N
2983:r
2963:s
2941:i
2937:x
2914:n
2910:x
2906:,
2903:.
2900:.
2897:.
2894:,
2889:1
2885:x
2881:=
2878:s
2843:)
2840:x
2837:(
2834:V
2828:)
2825:)
2822:x
2819:(
2816:S
2813:(
2810:V
2790:)
2787:x
2784:(
2781:S
2778:=
2775:)
2772:)
2769:x
2766:(
2763:S
2760:(
2757:S
2737:x
2731:)
2728:x
2725:(
2722:S
2700:n
2696:}
2692:1
2689:,
2686:0
2683:{
2677:x
2657:}
2654:1
2646:m
2642:2
2638:,
2635:.
2632:.
2629:,
2626:1
2623:,
2620:0
2617:{
2609:n
2605:}
2601:1
2598:,
2595:0
2592:{
2589::
2586:V
2564:n
2560:0
2553:)
2548:n
2544:0
2540:(
2537:S
2515:n
2511:}
2507:1
2504:,
2501:0
2498:{
2490:n
2486:}
2482:1
2479:,
2476:0
2473:{
2470::
2467:S
2444:m
2424:n
2380:s
2353:)
2350:s
2347:,
2344:I
2341:(
2338:N
2328:s
2307:)
2304:I
2301:(
2296:L
2292:F
2281:s
2277:,
2274:s
2242:L
2238:D
2214:I
2194:s
2174:)
2171:s
2168:,
2165:I
2162:(
2142:R
2120:L
2116:D
2109:I
2086:s
2066:s
2042:s
2021:}
2018:T
2015:P
2012:O
2009:{
2003:)
2000:s
1997:,
1994:I
1991:(
1988:N
1982:)
1979:I
1976:(
1971:L
1967:F
1958:L
1954:D
1950::
1947:C
1924:)
1921:)
1918:I
1915:(
1910:L
1906:F
1902:(
1899:t
1896:e
1893:s
1890:r
1887:e
1884:w
1881:o
1878:P
1872:)
1869:I
1866:(
1861:L
1857:F
1848:L
1844:D
1840::
1837:N
1815:)
1812:s
1809:,
1806:I
1803:(
1798:L
1794:c
1771:L
1767:D
1760:I
1740:)
1737:I
1734:(
1729:L
1725:F
1718:s
1696:+
1691:R
1683:)
1680:I
1677:(
1672:L
1668:F
1659:L
1655:D
1651::
1648:B
1626:)
1623:I
1620:(
1615:L
1611:F
1604:s
1582:L
1578:D
1571:I
1551:)
1548:I
1545:(
1540:L
1536:F
1527:L
1523:D
1519::
1516:A
1493:)
1490:I
1487:(
1482:L
1478:F
1471:s
1449:L
1445:D
1438:I
1416:I
1396:)
1393:I
1390:(
1385:L
1381:F
1374:s
1346:}
1343:)
1340:I
1337:(
1332:L
1328:F
1321:s
1318:,
1313:L
1309:D
1302:I
1296:)
1293:s
1290:,
1287:I
1284:(
1281:{
1275:)
1272:I
1269:(
1264:L
1260:F
1251:L
1247:D
1240:R
1220:L
1200:R
1180:)
1177:I
1174:(
1169:L
1165:F
1144:I
1095:L
1091:D
1070:L
1037:s
1000:s
980:3
977:=
974:)
967:s
963:,
960:I
957:(
952:L
948:c
924:=
917:s
896:s
876:s
854:2
851:=
848:)
842:,
839:I
836:(
831:L
827:c
805:2
802:=
799:)
793:,
790:I
787:(
782:L
778:c
756:2
753:=
750:)
744:,
741:I
738:(
733:L
729:c
706:}
700:,
694:,
688:{
685:=
682:)
676:,
673:I
670:(
667:N
647:s
627:s
607:s
580:2
577:=
574:)
568:=
565:s
562:,
559:I
556:(
551:L
547:c
517:3
513:x
490:2
486:x
463:1
459:x
438:)
435:I
432:(
427:L
423:F
400:3
396:x
373:1
369:x
345:=
342:s
320:i
316:x
295:s
269:)
264:3
260:x
251:2
247:x
240:(
234:)
229:3
225:x
216:1
212:x
205:(
199:)
194:2
190:x
181:1
177:x
173:(
149:I
121:s
101:s
80:.
68:I
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.