Bob, Rina:
I was speaking off the cuff - I don't immediately have any references to
give, so until I do, I can't back up my linearity assertions. I'll let you
know if I come across anything.
Gordon
At 10:20 PM 5/13/01 -0700, Rina Dechter wrote:
>Gordon,
>
>If you have referenice to this theoretical results or experiments
>it can be very useful.
>Thanks,
>------Rina.
>
>Gordon Hazen wrote:
> >
> > 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" <Hazen@iems.northwestern.edu>
> > >To: <uai@cs.orst.edu>
> > >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/
>
>--
>-----------------------------------------------------------------------------
>Rina Dechter dechter@ics.uci.edu
>Information and Computer Science Dept. (949) 824-6556
>University of California, Irvine fax: (949)-824-4056
>Irvine, CA 92717
>http://www.ics.uci.edu/~dechter
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/
This archive was generated by hypermail 2b29 : Mon May 14 2001 - 21:13:21 PDT