Subject: local search algorithms

From: Saleh Elmohamed <[email-masked]>
Date: Wed, 7 Apr 1999 14:43:01 -0400

Hi Jon,

I've recently come across a paper of yours "Storage
Managemet for Evolving Databases". 

The fragmented coloring problem introduced there may
have some relevance to my current work on scheduling
(multiprocessor scheduling, and timetabling). In terms
of timetabling, we have attempted at solving medium
to large scale problem by first transforming (mapping)
it into a graph coloring representation and then tackling
the latter. There is a great deal of limitaion on this approach
but it is one of the well-known approaches to these
kind of problems.

On the other hand, perhaps mapping it into a fragmented coloring
representation, may give us some flexibilty in dealing with
the constarints involved... That perhaps may help but
still not quite sure. 

We have also used local search methods to tackle these problems
and the results seem to be quite promising, and now beginning 
to look at some of issues involved in database performance and 
warehousing and how to tackle them using these methods.

Would it be possible if at some point within the next few days
if I could stop by and talk with you about these issues, etc. ??

We are only within a short driving distance from Ithaca so
it won't be any problem for me to stop by there.

Many thanks.

regards,
Saleh

---

From: Jon Kleinberg <[email-masked]>
Date: Thu, 8 Apr 1999 00:05:45 -0400 (EDT)

Dear Saleh,

The problems you describe sound interesting;
I'm not sure whether any of the coloring algorithms 
I've worked on would be useful to you, but I
would be interested in hearing more.

Unfortunately, I am out of town from the end of
this week until next Friday.  Perhaps we could
try arranging to meet at some point the week
of April 19?

Best regards,
Jon

---

From: Jon Kleinberg <[email-masked]>
Date: Wed, 28 Apr 1999 10:42:42 -0400 (EDT)

Dear Saleh,

Unfortunately, I've been out sick that last two days,
and so Thursday and Friday have filled up with re-scheduled meetings.
I'm out of town at the start of next week, but Thursday and
Friday of next week should be possible.

--Jon

---

From: Jon Kleinberg <[email-masked]>
Date: Thu, 6 May 1999 16:00:54 -0400 (EDT)

http://www.star-lab.com/goldberg/soft.html
(Network flow software)

The book is Surveys in Combinatorics, 1997, edited by R. A. Bailey, London Mathematical Society Lecture Note Series, 241, Cambridge
University Press, Cambridge, 1997. 338 pp. ISBN 0 521 59840 0. 
(This contains a survey on tree decompositions of graphs by Bruce Reed.
Sections 1 and 2 are most relevant.)

--Jon