Báo cáo toán học: On the Approximability of Max-Cut

Chúng tôi giới thiệu tỷ lệ hiệu suất gần như chắc chắn của một thuật toán xấp xỉ cho một vấn đề tối ưu hóa rời rạc và xem xét vấn đề MAX-CUT. Được biết rằng MAX-CUT không thể được giải quyết bởi một thuật toán xấp xỉ thời gian đa thức...
Nội dung trích xuất từ tài liệu:
Báo cáo toán học: " On the Approximability of Max-Cut"Vietnam Journal of Mathematics 34:4 (2006) 389–395 9LHWQD P -RXUQDO RI 0$ 7+ (0$ 7, &6 ‹ 9$67 On the Approximability of Max-Cut Le Cong Thanh Institute of Mathematics, 18 Hoang Quoc Viet Road, 10307 Hanoi, Vietnam Dedicated to Professor Do Long Van on the occasion of his 65th birthday Received December 15, 2005Abstract. We introduce the almost sure performance ratio of an approximation algo-rithm for a discrete optimization problem and consider it for the MAX-CUT problem.It is known that MAX-CUT cannot be solved by a polynomial time approximation algo-rithm with the ratio less than 1.0625 for all instances of the problem unless P = N P .The aim of this note is to show that MAX-CUT can be solved by a linear time ap-proximation algorithm with the ratio less than 1 + ε (for any ε > 0) for almost everyinstance, and hence with the almost sure performance ratio 1.2000 Mathematics Subject Classification: 68Q17.Keywords: Approximation algorithm, absolute performance ratio, almost sure perfor-mance ratio.1. Introduction, Terminology, Main ResultIn certain problems called optimization problems we seek to find the optimalsolution among a collection of candidate (feasible) solutions. If the optimizationproblem is NP-hard, then we have known that a polynomial time optimizationalgorithm cannot be found unless P = N P . A more reasonable goal is that offinding an approximation algorithm that runs in a polynomial time and thatfinds a solution that is “nearly” optimal may be good enough. To formalize this approach, we settled on a general form for our guarantees,in terms of ratios, which was useful for comparison purpose and which seemsto express nearness to optimality in a reasonable way. The terminology followsthat in [1]. Let Π be an optimization problem with instance set DΠ . We will use OP T (I )to denote the value of an optimal solution for an instance I ∈ DΠ . And let A be390 Le Cong Thanhan approximation algorithm for Π. The value of the candidate solution foundby A when applied to I will be denoted by A(I ). If Π is a minimization problem (resp., maximization problem), and I is anyinstance in DΠ , then the ratio RA (I ) of an approximation algorithm A on aninstance I is defined by A(I ) OP T (I ) RA (I ) = resp., RA(I ) = . OP T (I ) A(I )The absolute performance ratio RA of an approximation algorithm A for a prob-lem Π is given by RA = inf {r ≥ 1 : RA (I ) ≤ r for all instances I ∈ DΠ }. Notice that the absolute performance ratio is always a number greater thanor equal to 1 and is as close to 1 as the candidate solution found by the approx-imation algorithm is close to the optimal solution. An approximation algorithmwith the absolute performance ratio not greater than some positive integer α iscalled α−approximation algorithm. Notice also that performance guarantees for approximation algorithms are intheir nature works-case bounds, and algorithms often behave significantly betterin practice than their performance guarantees would suggest. As an alternative to the“works-case” performance guarantee approach, onemight therefore attempt to do performance analysis from an “average-case” pointof view. Indeed, such analysis has a long history and has been performed pri-mality through empirical studies. Rather practically, we are interested in performance analysis from an “al-most every-case” point of view, i.e., the analysis for “almost every instance” ofthe considered problem. We now present this conception for only optimization nproblems Π, whose instances with discrete structure, and for which the set DΠ nof instances of size n (n = 1, 2, . . . ) is finite and |DΠ | → ∞ as n → ∞. For nexample, if instances of Π are finite graphs then as DΠ one can choose the setof graphs with n vertices. Given a property Q, we shall say that almost every instance of Π has propertyQ if n lim (dQ (n)/|DΠ |) = 1, n→∞ nwhere dQ(n) is the number of instances I ∈ DΠ having property Q. ...