10 citations · 21 across the 16 of their papers we have counts for
Showing 2014Show all
3 papers · 1 filter
cs.DS2014
Graph-TSP from Steiner Cycles
Satoru Iwata, Alantha Newman, R. Ravi
We present an approach for the traveling salesman problem with graph metric based on Steiner cycles. A Steiner cycle is a cycle that is required to contain some specified subset of…
cs.DS2014
An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs
Alantha Newman
Mömke and Svensson presented a beautiful new approach for the traveling salesman problem on a graph metric (graph-TSP), which yields a -approximation guarantee on subcubic gra…
cs.DS2014
On the Configuration LP for Maximum Budgeted Allocation
Christos Kalaitzis, Aleksander Mcadry, Alantha Newman +2
We study the Maximum Budgeted Allocation problem, i.e., the problem of selling a set of indivisible goods to players, each with a separate budget, such that we maximize the…