Browse Prior Art Database

Probabilistic Methods: Algorithmic Aspects

IP.com Disclosure Number: IPCOM000149426D
Original Publication Date: 1989-Feb-28
Included in the Prior Art Database: 2007-Apr-01
Document File: 20 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Tetali, P.: AUTHOR [+2]

Abstract

P. Tetali Technical Report 444 February 1989 Probabilistic Methods : algorithmic aspects Prasad Tetali February 14, 1989 1 Introduction Let Al, . . , A, be events in a probability space. The basic probabilistic method says: If Pr[Aij 1, then Pr[hA;] 0 Explained more basically, this method proves the existence of a configuration, first by cre- ating a probability space whose points are configurations and second, by showing a positive probability that the "random7? configuration meets the desired criteria. So the Ai are typ- ically "bad" events, and the probabilistic method guarantees the existence of a "good" configuration. The method was first introduced by Paul Erdos in proving lower bounds for Ramsey numbers. Since then it has been a useful tool in graph theory and combinatorics. Spencer [14] provides, with an algorithmic flavor, an excellent treatment of different tech- niques similar in spirit to the basic probabilistic method. In this paper, we discuss algorithmic aspects of some of the (basic and non-basic) prob- abilistic methods. First we describe the power of the basic method by showing instances wherein the probabilistic proof can be converted to an eficient deterministic construction. We survey, in addition, two techniques useful when the basic method fails; i,e. when the "random configuration'' fails to meet the desired criteria. The first is a collection of meth- ods with an element of linear algebra. These methods are very constructive in nature; i.e. whenever we can prove the existence of solutions, it is also the case that there is an "effi- cient" way of computing the solution. As we shall see these provide useful approximation algorithms for some "hard" problems destined to belong to the NP-complete class. The situation, however, is quite different with the second technique, the well known Lovhz Lo- cal Lemma. The local lemma is used to prove various combinatorial results for which there exists no other known way of proving. Moreover, there are no known efficient algorithms to construct any of these results, and the problem of filnding more effective versions of these proofs remains an open and intriguing challenge.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 20

Probabilistic Methods: Algorithmic Aspects

P. Tetali

Technical Report 444

February 1989

[This page contains 1 picture or other non-text object]

Page 2 of 20

[This page contains 1 picture or other non-text object]

Page 3 of 20

Probabilistic Methods : algorithmic aspects

Prasad Tetali

February 14, 1989

Let Al, - . . , A, be events in a probability space. The basic probabilistic method says:

If Pr[Aij

0

Explained more basically, this method proves the existence of a configuration, first by cre- ating a probability space whose points are configurations and second, by showing a positive probability that the "random7? configuration meets the desired criteria. So the Ai are typ- ically "bad" events, and the probabilistic method guarantees the existence of a "good" configuration. The method was first introduced by Paul Erdos in proving lower bounds for Ramsey numbers. Since then it has been a useful tool in graph theory and combinatorics. Spencer [14]
provides, with an algorithmic flavor, an excellent treatment of different tech- niques similar in spirit to the basic probabilistic method.

  In this paper, we discuss algorithmic aspects of some of the (basic and non-basic) prob- abilistic methods. First we describe the power of the basic method by showing instances wherein the probabilistic proof can be converted to an eficient deterministic construction. We survey, in addition, two techniques useful when the basic method fails; i,e. when the "random configuration'' fails to meet the desired criteria. The first is a collection of meth- ods with an element of linear algebra. These methods are very constructive in nature; i.e. whenever we can prove the existence of solutions, it is also the case that there is an "effi- cient" way of computing the solution. As we shall see these provide useful approximation algorithms for some "hard" problems destined to belong to the NP-complete class. The situation, however, is quite different with the second technique, the well known Lovhz Lo- cal Lemma. The local lemma is used to prove various combinatorial results for which there exists no other known way of proving. Moreover, there are no known efficient algorithms to construct any of these results, and the problem of filnding more effective versions of these proofs remains an open and intriguing challenge.

1 Introduction

[This page contains 1 picture or other non-text object]

Page 4 of 20

2 The Probabilistic Method

Consider tournaments of n players in which every player plays a game and there are no draws. By directing an edge from i to j when player i beats player j, we can represent a tournament as a complete directed graph on n vertices. A tournament Tn has property Sk

if for every k players XI,

           . . . , xk there is some other player y who beats them all. The basic probabilistic method shows

Theorem 2.1 For every k there is a finite...