Content deleted Content added
Piyush Sriva (talk | contribs) approximation factors for maximization problems are usually written so as to be less than 1 |
Piyush Sriva (talk | contribs) approximation factors for maximization problems are usually written so as to be less than 1 |
||
Line 51:
::<math>x_i \in \{0,1\}</math> (if <math>x_i=1</math> then <math>S_i</math> is selected for the cover).
A greedy algorithm will no longer produce solutions with a performance guarantee. Namely, the worst case behavior of this algorithm might be very far from the optimal solution. The approximation algorithm is extended by the following way. First, after finding a solution using the greedy algorithm, return the better of the greedy algorithm's solution and the set of largest weight. Call this algorithm the modified greedy algorithm. Second, starting with all possible families of sets of sizes from one to (at least) three, augment these solutions with the modified greedy algorithm. Third, return the best out of all augmented solutions. This algorithm achieves an approximation ratio of <math>
== Generalized maximum coverage ==
Line 70:
The algorithm uses the concept of residual cost/weight. The residual cost/weight is measured against a tentative solution and its the difference of the cost/weight from the cost/weight gained by a tentative solution.
The algorithm has several stages. First, find a solution using greedy algorithm. In each iteration of the greedy algorithm the tentative solution is added the set which contains the maximum residual weight of elements divided by the residual cost of these elements along with the residual cost of the set. Second, compare the solution gained by the first step to the best solution which uses a small number of sets. Third, return the best out of all examined solutions. This algorithm achieves an approximation ratio of <math>
== Related problems ==
| |||