Is there an efficient solution to the travelling salesman problem with binary edge weights? ...

Book where humans were engineered with genes from animal species to survive hostile planets

Why are there no cargo aircraft with "flying wing" design?

When were vectors invented?

Is it fair for a professor to grade us on the possession of past papers?

Should I discuss the type of campaign with my players?

How to find out what spells would be useless to a blind NPC spellcaster?

Apollo command module space walk?

Can a non-EU citizen traveling with me come with me through the EU passport line?

Identify plant with long narrow paired leaves and reddish stems

How widely used is the term Treppenwitz? Is it something that most Germans know?

Is the Standard Deduction better than Itemized when both are the same amount?

What is a non-alternating simple group with big order, but relatively few conjugacy classes?

What would be the ideal power source for a cybernetic eye?

Why am I getting the error "non-boolean type specified in a context where a condition is expected" for this request?

What is Wonderstone and are there any references to it pre-1982?

Why did the rest of the Eastern Bloc not invade Yugoslavia?

How to tell that you are a giant?

What is the role of the transistor and diode in a soft start circuit?

What does this icon in iOS Stardew Valley mean?

What does the "x" in "x86" represent?

3 doors, three guards, one stone

How come Sam didn't become Lord of Horn Hill?

Using et al. for a last / senior author rather than for a first author

What to do with chalk when deepwater soloing?



Is there an efficient solution to the travelling salesman problem with binary edge weights?



Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?How can I verify a solution to Travelling Salesman Problem in polynomial time?Travelling salesman problem with detoursEvolutionary algorithm for the Physical Travelling Salesman ProblemTravelling Salesman Problem with unknown shortest paths between nodesWhat if the travelling salesman travelled by plane?Traveling salesman problem with disconnected cities / infinite length edgeTravelling salesman problem with small edge weightsWhy does Travelling Salesman Problem pose the restriction that each vertex can only be visited once?Travelling Salesman problem using Guided Local SearchIf I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?












3












$begingroup$


Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?










share|cite|improve this question











$endgroup$

















    3












    $begingroup$


    Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?










    share|cite|improve this question











    $endgroup$















      3












      3








      3


      2



      $begingroup$


      Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?










      share|cite|improve this question











      $endgroup$




      Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?







      traveling-salesman






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Mar 24 at 11:13









      Apass.Jack

      14.3k1940




      14.3k1940










      asked Mar 24 at 7:33









      WiccanKarnakWiccanKarnak

      1185




      1185






















          2 Answers
          2






          active

          oldest

          votes


















          7












          $begingroup$

          No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)






          share|cite|improve this answer









          $endgroup$









          • 3




            $begingroup$
            I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
            $endgroup$
            – John Dvorak
            Mar 24 at 11:16












          • $begingroup$
            @JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
            $endgroup$
            – WiccanKarnak
            Mar 24 at 14:43










          • $begingroup$
            Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
            $endgroup$
            – John Dvorak
            Mar 24 at 15:00












          • $begingroup$
            @WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
            $endgroup$
            – Eric Towers
            Mar 24 at 19:39










          • $begingroup$
            Aren't you allowed to use the same edge twice in TSP?
            $endgroup$
            – immibis
            Mar 24 at 22:00



















          2












          $begingroup$

          The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.



          However, it is simple to reduce HAMILTON-CYCLE to $0$$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$$1$ TSP is NP-complete.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
            $endgroup$
            – j_random_hacker
            Mar 25 at 11:24










          • $begingroup$
            @j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
            $endgroup$
            – David Richerby
            Mar 25 at 11:29














          Your Answer








          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "419"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105984%2fis-there-an-efficient-solution-to-the-travelling-salesman-problem-with-binary-ed%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          2 Answers
          2






          active

          oldest

          votes








          2 Answers
          2






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          7












          $begingroup$

          No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)






          share|cite|improve this answer









          $endgroup$









          • 3




            $begingroup$
            I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
            $endgroup$
            – John Dvorak
            Mar 24 at 11:16












          • $begingroup$
            @JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
            $endgroup$
            – WiccanKarnak
            Mar 24 at 14:43










          • $begingroup$
            Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
            $endgroup$
            – John Dvorak
            Mar 24 at 15:00












          • $begingroup$
            @WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
            $endgroup$
            – Eric Towers
            Mar 24 at 19:39










          • $begingroup$
            Aren't you allowed to use the same edge twice in TSP?
            $endgroup$
            – immibis
            Mar 24 at 22:00
















          7












          $begingroup$

          No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)






          share|cite|improve this answer









          $endgroup$









          • 3




            $begingroup$
            I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
            $endgroup$
            – John Dvorak
            Mar 24 at 11:16












          • $begingroup$
            @JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
            $endgroup$
            – WiccanKarnak
            Mar 24 at 14:43










          • $begingroup$
            Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
            $endgroup$
            – John Dvorak
            Mar 24 at 15:00












          • $begingroup$
            @WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
            $endgroup$
            – Eric Towers
            Mar 24 at 19:39










          • $begingroup$
            Aren't you allowed to use the same edge twice in TSP?
            $endgroup$
            – immibis
            Mar 24 at 22:00














          7












          7








          7





          $begingroup$

          No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)






          share|cite|improve this answer









          $endgroup$



          No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Mar 24 at 8:39









          j_random_hackerj_random_hacker

          3,02711016




          3,02711016








          • 3




            $begingroup$
            I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
            $endgroup$
            – John Dvorak
            Mar 24 at 11:16












          • $begingroup$
            @JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
            $endgroup$
            – WiccanKarnak
            Mar 24 at 14:43










          • $begingroup$
            Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
            $endgroup$
            – John Dvorak
            Mar 24 at 15:00












          • $begingroup$
            @WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
            $endgroup$
            – Eric Towers
            Mar 24 at 19:39










          • $begingroup$
            Aren't you allowed to use the same edge twice in TSP?
            $endgroup$
            – immibis
            Mar 24 at 22:00














          • 3




            $begingroup$
            I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
            $endgroup$
            – John Dvorak
            Mar 24 at 11:16












          • $begingroup$
            @JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
            $endgroup$
            – WiccanKarnak
            Mar 24 at 14:43










          • $begingroup$
            Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
            $endgroup$
            – John Dvorak
            Mar 24 at 15:00












          • $begingroup$
            @WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
            $endgroup$
            – Eric Towers
            Mar 24 at 19:39










          • $begingroup$
            Aren't you allowed to use the same edge twice in TSP?
            $endgroup$
            – immibis
            Mar 24 at 22:00








          3




          3




          $begingroup$
          I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
          $endgroup$
          – John Dvorak
          Mar 24 at 11:16






          $begingroup$
          I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
          $endgroup$
          – John Dvorak
          Mar 24 at 11:16














          $begingroup$
          @JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
          $endgroup$
          – WiccanKarnak
          Mar 24 at 14:43




          $begingroup$
          @JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
          $endgroup$
          – WiccanKarnak
          Mar 24 at 14:43












          $begingroup$
          Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
          $endgroup$
          – John Dvorak
          Mar 24 at 15:00






          $begingroup$
          Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
          $endgroup$
          – John Dvorak
          Mar 24 at 15:00














          $begingroup$
          @WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
          $endgroup$
          – Eric Towers
          Mar 24 at 19:39




          $begingroup$
          @WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
          $endgroup$
          – Eric Towers
          Mar 24 at 19:39












          $begingroup$
          Aren't you allowed to use the same edge twice in TSP?
          $endgroup$
          – immibis
          Mar 24 at 22:00




          $begingroup$
          Aren't you allowed to use the same edge twice in TSP?
          $endgroup$
          – immibis
          Mar 24 at 22:00











          2












          $begingroup$

          The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.



          However, it is simple to reduce HAMILTON-CYCLE to $0$$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$$1$ TSP is NP-complete.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
            $endgroup$
            – j_random_hacker
            Mar 25 at 11:24










          • $begingroup$
            @j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
            $endgroup$
            – David Richerby
            Mar 25 at 11:29


















          2












          $begingroup$

          The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.



          However, it is simple to reduce HAMILTON-CYCLE to $0$$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$$1$ TSP is NP-complete.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
            $endgroup$
            – j_random_hacker
            Mar 25 at 11:24










          • $begingroup$
            @j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
            $endgroup$
            – David Richerby
            Mar 25 at 11:29
















          2












          2








          2





          $begingroup$

          The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.



          However, it is simple to reduce HAMILTON-CYCLE to $0$$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$$1$ TSP is NP-complete.






          share|cite|improve this answer









          $endgroup$



          The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.



          However, it is simple to reduce HAMILTON-CYCLE to $0$$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$$1$ TSP is NP-complete.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Mar 24 at 20:20









          David RicherbyDavid Richerby

          70.4k16107196




          70.4k16107196












          • $begingroup$
            This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
            $endgroup$
            – j_random_hacker
            Mar 25 at 11:24










          • $begingroup$
            @j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
            $endgroup$
            – David Richerby
            Mar 25 at 11:29




















          • $begingroup$
            This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
            $endgroup$
            – j_random_hacker
            Mar 25 at 11:24










          • $begingroup$
            @j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
            $endgroup$
            – David Richerby
            Mar 25 at 11:29


















          $begingroup$
          This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
          $endgroup$
          – j_random_hacker
          Mar 25 at 11:24




          $begingroup$
          This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
          $endgroup$
          – j_random_hacker
          Mar 25 at 11:24












          $begingroup$
          @j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
          $endgroup$
          – David Richerby
          Mar 25 at 11:29






          $begingroup$
          @j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
          $endgroup$
          – David Richerby
          Mar 25 at 11:29




















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Computer Science Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105984%2fis-there-an-efficient-solution-to-the-travelling-salesman-problem-with-binary-ed%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          Nidaros erkebispedøme

          Birsay

          Where did Arya get these scars? Unicorn Meta Zoo #1: Why another podcast? Announcing the arrival of Valued Associate #679: Cesar Manara Favourite questions and answers from the 1st quarter of 2019Why did Arya refuse to end it?Has the pronunciation of Arya Stark's name changed?Has Arya forgiven people?Why did Arya Stark lose her vision?Why can Arya still use the faces?Has the Narrow Sea become narrower?Does Arya Stark know how to make poisons outside of the House of Black and White?Why did Nymeria leave Arya?Why did Arya not kill the Lannister soldiers she encountered in the Riverlands?What is the current canonical age of Sansa, Bran and Arya Stark?