|
Recent Issues |
||||
| Volume 37 | 1 | 2 | 3 | 4 |
| Volume 36 | 1 | 2 | 3 | 4 |
| Volume 35 | 1 | 2 | 3 | 4 |
| Volume 34 | 1 | 2 | 3 | 4 |
| Volume 33 | 1 | 2 | 3 | 4 |
|
The Journal |
||||
|
Related Links |
||||
|
Vietnam Journal of Mathematics 36:3(2008) 327-336 |
Performance Analysis of Greedy Algorithms for Max-IS and Min-Maxl-Match |
|
Le Cong Thanh |
|
Abstract. We consider the approximating behaviour of greedy algorithms, in terms of performance ratios, for the maximum independent set and minimum maximal matching problems, two classical NP-hard problems. The main results tend to confirm our observation that the performance of algorithms in almost every-case is generally much better than worst-case performance. In particular, we show that for almost every instance of the minimum maximal matching problem the greedy algorithm finds a feasible solution that is near-optimal. |
|
|
|
2000 Mathematics Subject Classification: 68Q17. |
|
Keywords: Independent set, matching, greedy algorithm, performance ratio. |
|
Vietnam Academy of Science and Technology
& Vietnamese Mathematical Society © Copyright 2009 Vietnam Journal of Mathematics. All rights reserved. |