Task: Text Categorization
Input (English): The first solution to a nontrivial instance of this problem was presented by Dantzig, Fulkerson, and Johnson in 1954 and employed linear programming technqiues to provide a solution for a graph of 42 nodes. An optimal solution to the "Sweden" instance of this problem, the largest one so far solved, was generated by the (*) Lin-Kernighan heuristic. Formally stated, the problem is to find the Hamiltonian cycle for a weighted graph with the minimum edge cost. For 10 points, identify this NP-hard problem in computer science, based on the task of visiting every city in a territory and returning to the start while driving a minimum distance.
Output (English): Science