Davide Frey

The Quadratic Shortest Path Problem: Complexity, Approximability, and Solution Methods

  • Christoph Buchheim
  • Marc Goerigk
  • Federico Malucelli
  • Borzou Rostami
  • AndrĂ© Chassein
  • Davide Frey
  • Michael Hopf
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags

    We consider the problem of finding a shortest path in a directed graph with a quadratic objective function (the QSPP). We show that the QSPP cannot be approximated unless P=NP. For the case of a convex objective function, an n-approximation algorithm is presented, where n is the number of nodes in the graph, and APX-hardness … Read more

    On the Quadratic Shortest Path Problem

  • Christoph Buchheim
  • Federico Malucelli
  • Borzou Rostami
  • Davide Frey
    • Categories Combinatorial Optimization, Quadratic Programming Tags , ,

    Finding the shortest path in a directed graph is one of the most important combinatorial optimization problems, having applications in a wide range of fields. In its basic version, however, the problem fails to represent situations in which the value of the objective function is determined not only by the choice of each single arc, … Read more