120 citations · 268 across the 16 of their papers we have counts for
4 papers · 1 filter
The Shortest Connection Game
Andreas Darmann, Ulrich Pferschy, Joachim Schauer
We introduce Shortest Connection Game, a two-player game played on a directed graph with edge costs. Given two designated vertices in which they start, the players take turns in ch…
Generating subtour elimination constraints for the TSP from pure integer solutions
Ulrich Pferschy, Rostislav Stanek
The traveling salesman problem (TSP) is one of the most prominent combinatorial optimization problems. Given a complete graph G = (V, E) and non-negative distances d for every edge…
Price of Fairness for Allocating a Bounded Resource
Gaia Nicosia, Andrea Pacifici, Ulrich Pferschy
In this paper we study the problem of allocating a scarce resource among several players (or agents). A central decision maker wants to maximize the total utility of all agents. Ho…
On the shortest path game: extended version
Andreas Darmann, Ulrich Pferschy, Joachim Schauer
In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (players) move together along the edges of a graph from a given starting…