Randomized Rounding
- PDF / 226,215 Bytes
- 4 Pages / 547.087 x 737.008 pts Page_size
- 10 Downloads / 158 Views
that the existence of an FNCAS for any of the problems considered is equivalent to the existence of an NC algorithm for perfect matching which is also still an open problem. Cross References Approximate Maximum Flow Construction Maximum Matching Paging Recommended Reading 1. Díaz, J., Serna, M., Spirakis, P.G., Torán, J.: Paradigms for fast parallel approximation. In: Cambridge International Series on Parallel Computation, vol 8, Cambridge University Press, Cambridge (1997) 2. Even, S.: Graph Algorithms. Computer Science Press, Potomac (1979) 3. Goldschlager, L.M., Shaw, R.A., Staples, J.: The maximum flow problem is log-space complete for P. Theor. Comput. Sci. 21, 105–111 (1982) 4. Johnson, D.B., Venkatesan, S.M.: Parallel algorithms for minimum cuts and maximum flows in planar networks. J. ACM 34, 950–967 (1987) 5. Karp, R.M., Upfal, E., Wigderson, A.: Constructing a perfect matching is in Random NC. Combin. 6, 35–48 (1986) 6. Korte, B., Schrader, R.: On the existence of fast approximation schemes. Nonlinear Program. 4, 415–437 (1980) 7. Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976) 8. Papadimitriou, C.: Computational Complexity. AddisonWesley, Reading (1994) 9. Peters, J.G., Rudolph, L.: Parallel aproximation schemes for subset sum and knapsack problems. Acta Inform. 24, 417–432 (1987) 10. Spirakis, P.: PRAM models and fundamental parallel algorithm techniques: Part II. In: Gibbons, A., Spirakis, P. (eds.) Lectures on Parallel Computation, pp. 41–66. Cambrige University Press, New York (1993)
Randomized Rounding 1987; Raghavan, Thompson RAJMOHAN RAJARAMAN Department of Computer Science, Northeastern University, Boston, MA, USA Problem Definition Randomized rounding is a technique for designing approximation algorithms for NP-hard optimization problems. Many combinatorial optimization problems can be represented as 0-1 integer linear programs; that is, integer linear programs in which variables take values in f0; 1g.
R
While 0-1 integer linear programming is NP-hard, the rational relaxations (also referred to as fractional relaxations) of these linear programs are solvable in polynomial time [12,13]. Randomized rounding is a technique to construct a provably good solution to a 0-1 integer linear program from an optimum solution to its rational relaxation by means of a randomized algorithm. Let ˘ be a 0-1 integer linear program with variables x i 2 f0; 1g, 1 i n. Let ˘ R be the rational relaxation of ˘ obtained by replacing the x i 2 f0; 1g constraints by x i 2 [0; 1]; 1 i n. The randomized rounding approach consists of two phases: 1. Solve ˘ R using an efficient linear program solver. Let the variable xi take on value x i 2 [0; 1], 1 i n. 2. Compute a solution to ˘ by setting the variables xi randomly to one or zero according to the following rule: Pr[x i = 1] = x i : For several fundamental combinatorial optimization problems, the randomized rounding technique yields simple randomized approximation algorithms that yield solution
Data Loading...
