Problems Flashcards
1
Q
What is the Travelling salesman problem?
A
Given a list of n cities and distances between those cities, find the shortest cycle which visits each city exactly once before returning to the city where it started.
2
Q
What is the Knapsack problem?
A
Given n items of known weights w1, w2… wn and values v1, v2, . . . vn and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.
3
Q
What is the Maximum independent set problem?
A
Find the largest subset of elements from a superset,
so that there is no edge that connects two vertexes in the subset
