|
|
|
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.
|
|
|
|
Established
by Vietnam Academy of Science and Technology & Vietnam Mathematical
Society
Published
by Springer since January 2013
|
|
