5 ms·

> The average instance of most NP-hard problems [is] pretty tractable. I don't think the "average" and "most" in this claim make sense. If we could solve NP-co

by blt 4y ago

> The average instance of most NP-hard problems [is] pretty tractable. I don't think the "average" and "most" in this claim make sense. If we could solve NP-complete problems efficiently, we would suddenly want to solve a lot of NP-complete problem instances that we currently do not even attempt.

deanCommie 4y ago
The "prototypical" NP-complete problem - the travelling salesman problem - is "solved" every time you punch in navigation directions in Google Maps.
- imtringued 4y ago
  Google Maps is breadth first search at worst...
- NineStarPoint 4y ago
  Google Maps doesn’t need to solve the traveling salesman problem (shortest route between all nodes in a network). To find a route between two points on a graph is just a shortest path problem, solvable by Dijkstra's algorithm and very much in P. (They almost certainly use heuristic algorithms that are more efficient than Disjkstra’s of course, since the size of the graph of all roads is such that a V^2 algorithm is still fairly expensive to run)
  - eru 4y ago
    > Google Maps doesn’t need to solve the traveling salesman problem (shortest route between all nodes in a network). To be more precise, the traveling saleman problem asks for the shortest tour that visits all nodes in a directed, weighted graph. That's a general graph. If you do this on a map, your travel times have a lot of structure already. See https://en.wikipedia.org/wiki/Travelling_salesman_problem#Special_cases https://en.wikipedia.org/wiki/Travelling_salesman_problem#Sp... especially 'Metric' and 'Euclidean'. And, of course, when asked for directions Google Maps gives you just the shortest path between two nodes; or perhaps the shortest path that visits a given sequence of nodes in a fixed order. Google Maps doesn't (yet?) re-shuffle your stops for you. If it did that in general, it would indeed have to solve something at least as hard as the (metric) TSP. (Of course, they could also only support that feature for eg up to five stops. That would be comfortably in P.)
  - boloust 4y ago
    > They almost certainly use heuristic algorithms that are more efficient than Disjkstra’s of course There are techniques like contraction hierarchies[1] that can efficiently compute exact shortest paths on extremely large road network graphs. [1]: https://en.m.wikipedia.org/wiki/Contraction_hierarchies https://en.m.wikipedia.org/wiki/Contraction_hierarchies
- Lio 4y ago
  Aren't those two different problems? I was under the impression that Travelling Salesman was about efficiently visiting multiple points in any order, where as navigation directions are ordered point-to-point, even if you add multiple waypoints. As such Travelling Salesman would be much, much more complex. I'm probably way out on current best solutions[1] but you could do one with Djikstra's Algorithm or A* but the other would require something probabilistic like Simulated Annealing. 1. Sorry, I'm almost certain that these are not optimal algorithms but I'm just using them as illustration for "small" graphs. I'd be very happy to be enlightened on what's more current.
  - eru 4y ago
    If you want an exact solution, and are willing to wait for it, you can use an integer linear programming solver to work on your Traveling Salesman Problem for you. If you abort them early, these solvers can give you an approximate solution and *crucially* also a guarantee how far away they are from the optimal solution. Eg at most 3.7% longer than the optimal solution.
    - bumby 4y ago
      Relating to the article on construction, I think this may be an instance where the theory breaks down in practice. Construction jobs aren’t just optimal linear programming because the order often impacts both the costs and duration of subsequent work, making much of it nonlinear.
      - eru 4y ago
        Linear integer programming can model these kinds of dependencies.
        bumby 4y ago
        Can you elaborate? My understanding is they can in an iterative fashion, but the dependencies I’m talking about are not constraints but nonlinear dependencies between decision variables. As an example, the decision variables may be integers denoting schedule blocks, but the cost is a nonlinear function of time and the other variables. Meaning each time block can be solved with linear programming iteratively, but to solve across all time blocks requires nonlinear optimization
nine_k 4y ago
Very often it's enough to obtain an exact solution. 95% on the way to the optimal solution is usually good enough. Approximate solutions are much easier to reach. Methods like simulated annealing can even approach them stochastically.
- nine_k 4y ago
  s/an exact/inexact/ but cannot edit already.

by blt 4y ago

deanCommie 4y ago

The "prototypical" NP-complete problem - the travelling salesman problem - is "solved" every time you punch in navigation directions in Google Maps.

imtringued 4y ago
Google Maps is breadth first search at worst...
NineStarPoint 4y ago
Google Maps doesn’t need to solve the traveling salesman problem (shortest route between all nodes in a network). To find a route between two points on a graph is just a shortest path problem, solvable by Dijkstra's algorithm and very much in P. (They almost certainly use heuristic algorithms that are more efficient than Disjkstra’s of course, since the size of the graph of all roads is such that a V^2 algorithm is still fairly expensive to run)
- eru 4y ago
  > Google Maps doesn’t need to solve the traveling salesman problem (shortest route between all nodes in a network). To be more precise, the traveling saleman problem asks for the shortest tour that visits all nodes in a directed, weighted graph. That's a general graph. If you do this on a map, your travel times have a lot of structure already. See https://en.wikipedia.org/wiki/Travelling_salesman_problem#Special_cases https://en.wikipedia.org/wiki/Travelling_salesman_problem#Sp... especially 'Metric' and 'Euclidean'. And, of course, when asked for directions Google Maps gives you just the shortest path between two nodes; or perhaps the shortest path that visits a given sequence of nodes in a fixed order. Google Maps doesn't (yet?) re-shuffle your stops for you. If it did that in general, it would indeed have to solve something at least as hard as the (metric) TSP. (Of course, they could also only support that feature for eg up to five stops. That would be comfortably in P.)
- boloust 4y ago
  > They almost certainly use heuristic algorithms that are more efficient than Disjkstra’s of course There are techniques like contraction hierarchies[1] that can efficiently compute exact shortest paths on extremely large road network graphs. [1]: https://en.m.wikipedia.org/wiki/Contraction_hierarchies https://en.m.wikipedia.org/wiki/Contraction_hierarchies
Lio 4y ago
Aren't those two different problems? I was under the impression that Travelling Salesman was about efficiently visiting multiple points in any order, where as navigation directions are ordered point-to-point, even if you add multiple waypoints. As such Travelling Salesman would be much, much more complex. I'm probably way out on current best solutions[1] but you could do one with Djikstra's Algorithm or A* but the other would require something probabilistic like Simulated Annealing. 1. Sorry, I'm almost certain that these are not optimal algorithms but I'm just using them as illustration for "small" graphs. I'd be very happy to be enlightened on what's more current.
- eru 4y ago
  If you want an exact solution, and are willing to wait for it, you can use an integer linear programming solver to work on your Traveling Salesman Problem for you. If you abort them early, these solvers can give you an approximate solution and *crucially* also a guarantee how far away they are from the optimal solution. Eg at most 3.7% longer than the optimal solution.
  - bumby 4y ago
    Relating to the article on construction, I think this may be an instance where the theory breaks down in practice. Construction jobs aren’t just optimal linear programming because the order often impacts both the costs and duration of subsequent work, making much of it nonlinear.
    - eru 4y ago
      Linear integer programming can model these kinds of dependencies.
      - bumby 4y ago
        Can you elaborate? My understanding is they can in an iterative fashion, but the dependencies I’m talking about are not constraints but nonlinear dependencies between decision variables. As an example, the decision variables may be integers denoting schedule blocks, but the cost is a nonlinear function of time and the other variables. Meaning each time block can be solved with linear programming iteratively, but to solve across all time blocks requires nonlinear optimization

nine_k 4y ago

Very often it's enough to obtain an exact solution. 95% on the way to the optimal solution is usually good enough. Approximate solutions are much easier to reach. Methods like simulated annealing can even approach them stochastically.

nine_k 4y ago
s/an exact/inexact/ but cannot edit already.