Date: Thu, 7 Mar 85 17:57:17 est
From:: Walter Hamscher
To: *mac@mc
Subject: Graduate Student Lunch *SEMINAR*

Place: *THIRD FLOOR THEORY PLAYROOM*
Date: Friday

	       COMPUTER AIDED CONCEPTUAL ART
		  REVOLTING SEMINAR SERIES
			  presents

	 GREEDY ALGORITHMS FOR REALLY HARD PROBLEMS

		       Mike Generous
			Penny Weise
		       Dahlia Fulisch

Perhaps the best known greedy algorithm is Kruskal's Minimum
Spanning Tree algorithm.  The concept of "greedy algorithm"
is here generalized to provide a framework in which any
problem can be solved with bounded error in constant time.
The simplest such algorithm is a stupefyingly
straightforward algorithm for finding the maximum of a list
of numbers: take the maximum of the first two elements of
the list.  The bounded error arises from the provability of
the correctness criterion "We could have done worse!".  The
Satisfiability problem for the predicate calculus is solved
trivially, because we have shown conclusively elsewhere that
we are Satisfied with predicate calculus.  The framework
applies also to meta-problem solving (i.e. "What problem
should we sic the greedy algorithm on next"), as we will
demonstrate by applying it to the problem of generating
grant proposals.  If there is time, we will give other
examples involving Single-State Automata (Moronotrons) and
Extremist Graph Theory.