Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!uwm.edu!ux1.cso.uiuc.edu!cs433dk
From: cs433dk@ux1.cso.uiuc.edu (Donald Gillies)
Newsgroups: comp.theory
Subject: Re: Probabalistic algo. for matching problem.
Message-ID: <1991May15.045238.20344@ux1.cso.uiuc.edu>
Date: 15 May 91 04:52:38 GMT
References: <9498@idunno.Princeton.EDU>
Organization: University of Illinois at Urbana
Lines: 13


I am looking for any information on heuristics for the set-cover
problem (preferably multi-dimensional, but 2-dimensional would be
nice).  Has anyone analyzed heuristics that produce vertex covers with
less than 2*opt edges in 2 dimensions?  Are there heuristics that
cover using n-dimensional edges with a constant bound on performance?
Any help would be appreciated.

Don Gillies	     |  University of Illinois at Urbana-Champaign
gillies@cs.uiuc.edu  |  Digital Computer Lab, 1304 W. Springfield, Urbana IL
---------------------+------------------------------------------------------
"WAR!  UGH! ... What is it GOOD FOR?  ABSOLUTELY NOTHING!"  
	- the song "WAR" by Edwin Starr, circa 1971