Abstract:
Most of us have an intuitive understanding of what a greedy-like algorithm is. Even though the concept has been studied in restricted scenarios, such as matroid theory, the concept, as it is used as an every-day algorithms or programming paradigm, has not been formally studied. Priority Algorithms is an attempt at modeling and capturing the power of these greedy-like algorithmic approaches to problem solving. Most of the work in the area has been targeted at establishing lower bounds on the ratios obtainable when approximating NP-hard problems using greedy-like approaches. We give a brief introduction to the topic. In the talk, we define priority algorithms, list problem scenarios that have been investigated so far, and discuss a few examples to give the flavor of the kind of argumentation which is used.This is joint work with Allan Borodin and Joan Boyar.
Abstract:
This talk will describe some methods for finding upper bounds on the expected length of two random strings of equal length, and investigate whether these methods produce bounds that are asymptotic to the true value.