Problems

Question 1

What is the Travelling salesman problem?

Answer 1

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.

Question 2

What is the Knapsack problem?

Answer 2

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.

Question 3

What is the Maximum independent set problem?

Answer 3

Find the largest subset of elements from a superset,
so that there is no edge that connects two vertexes in the subset