Scribd
Upload
24 views1 page

Approximation Algorithms For NP - Hard Problems

The document discusses approximation algorithms for the Traveling Salesman Problem (TSP) and the Knapsack Problem, focusing on greedy algorithms. For TSP, it describes the nearest-neighbor algorithm as a simple approximation method. For the Knapsack Problem, it suggests selecting items based on their value-to-weight ratios to optimize the knapsack's capacity efficiently.

Uploaded by

lucas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
24 views1 page

Approximation Algorithms For NP - Hard Problems

The document discusses approximation algorithms for the Traveling Salesman Problem (TSP) and the Knapsack Problem, focusing on greedy algorithms. For TSP, it describes the nearest-neighbor algorithm as a simple approximation method. For the Knapsack Problem, it suggests selecting items based on their value-to-weight ratios to optimize the knapsack's capacity efficiently.

Uploaded by

lucas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Aproximation Algorithms for the Traveling Approximation Algorithms for the Knapsack

Salesman Problem Problem

Greedy Algorithms for the TSP The simplest Greedy Algorithms for the Knapsack
approximation algorithms for the traveling Problem We can think of several greedy
salesman problem are based on the greedy approaches to this problem. One is to select the
technique. We will discuss here one such items in decreasing order of their weights;
algorithm. however, heavier items may not be the most
valuable in the set.
Nearest-neighbor
Alternatively, if we pick up
algorithm
the items in decreasing
Approximation Algorithms for NP -Hard Problems order of their value, there
Step 1 Choose an
is no guarantee that the
arbitrary city as the start.
knapsack’s capacity will
Step 2 Repeat the
be used efficiently. Can
following operation until A polynomial-time approximation algorithm is said to be a c- we find a greedy strategy
all the cities have been
approximation algorithm, where c ≥ 1, if the accuracy ratio of the that takes into account
visited:
approximation it produces does not exceed c for any instance of the both the weights and
go to the unvisited city
values? Yes, we can, by
nearest the one visited problem in question: r(s a ) ≤ c.
computing the value-to-
last (ties can be broken
weight ratios v i /w i , i = 1,
arbitrarily).
2, . . . , n, and selecting
Step 3 Return to the
the items in decreasing
starting city.
order of these ratios.

You might also like