I don't think so - MC Monte Carlo and Monte Carlo in general provide only
a statistical approximation whose convergence is guaranteed, but no
guaranteed bound. What I think is true is that convergence to within a
given confidence range is linear in problem size, but of course a 95%
confidence bound is only an estimate, not a guarantee.
-- Gordon
At 07:22 PM 5/12/01 -0700, Bob Welch wrote:
>Gordon:
>
>If that were true then wouldn't there be a counter example to the NP hard
>results for both exact and approximate solutions?
>
>Bob
>----- Original Message -----
>From: "Gordon Hazen" <[EMAIL PROTECTED]>
>To: <[EMAIL PROTECTED]>
>Sent: Friday, May 11, 2001 7:49 PM
>Subject: Re: [UAI] how to evaluate approximate algorithms when exact
>solution is not available?
>
>
> > Empirical studies would be interesting. Why not run an exact algorithm if
> > one has huge amounts of time available? Because, as I understand it,
> > peformance for Gibbs is linear in problem size, whereas performance for an
> > exact algorithm is exponential in problem size.
> >
> > -- Gordon
> >
Gordon Hazen
IE/MS Department, McCormick School of Engineering and Applied Science
Northwestern University, Evanston, IL. USA 60208-3119
Phone 847-491-5673 Fax 847-491-8005
Web: www.iems.nwu.edu/~hazen/
