tag:blogger.com,1999:blog-3722233.post114502184076803672..comments2023-09-30T21:44:03.907-05:00Comments on Computational Complexity: The iCal EffectLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-1145166559332175842006-04-16T00:49:00.000-05:002006-04-16T00:49:00.000-05:00Funny that I learn about Brown's iCal feed from La...Funny that I learn about Brown's iCal feed from Lance's blog!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1145075082428381272006-04-14T23:24:00.000-05:002006-04-14T23:24:00.000-05:00Here at Brown CS we already have an iCal feed ava...Here at Brown CS we already have an <A HREF="http://cs.brown.edu/~cce/browncs.ics" REL="nofollow">iCal feed</A> available that is automatically updated for department events. It was originally conceived mainly for Mac users, but works nicely with Google calendar. It was pretty easy to write the script to generate the feed (from the department's <A HREF="http://cs.brown.edu/events/" REL="nofollow">events database</A>) using the Python <A HREF="http://codespeak.net/icalendar/" REL="nofollow">iCalendar</A> library (there's also support in Perl, etc). Now I can ignore all those emailed seminar announcements...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1145069125236266022006-04-14T21:45:00.000-05:002006-04-14T21:45:00.000-05:00Common graduate student mistake: Generalize the pr...Common graduate student mistake: Generalize the problem enough until it is NP-complete, and then claim that thus there is no efficient solution to the problem.<BR/><BR/>When I worked at Sun we all used dtcal and it had great coordination with emails and viewing other schedules. It's somewhat amazing to me that calendar programs haven't gotten much better yet. Including that very feature Lance desires.Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1145053177311405252006-04-14T17:19:00.000-05:002006-04-14T17:19:00.000-05:00need to schedule a meeting .... when2meet.comi'm n...need to schedule a meeting .... when2meet.com<BR/><BR/>i'm not associated with it but it's tightAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1145050643844649862006-04-14T16:37:00.000-05:002006-04-14T16:37:00.000-05:00This is an example where there is a difference bet...This is an example where there is a difference between the usual polynomial/exponential distinction in complexity theory and a practical application.<BR/><BR/>Chances are, there are fairly strict bounds on when people want to schedule meetings, e.g. they must occur in a particular week. There will also be bounds on the number of meeting participants, i.e. it is not useful to schedule incredibly frequent meetings between large groups of people.<BR/><BR/>There will therefore be quite tight limits on the graph size and number of colors, so an exhaustive search would probably work fine in practice.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1145044054957592992006-04-14T14:47:00.000-05:002006-04-14T14:47:00.000-05:00This is probably obvious, but it's NP-Complete to ...This is probably obvious, but it's NP-Complete to schedule a set of meetings for a minimal number of time slots even in the case where a person is in at most two meetings. Then each meeting can be seen as a vertex and each person can be seen as an edge, and it's equivalent to finding a minimal coloring for an arbitrary graph. On the other hand, simply finding an open timeslot for a single meeting is not hard.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1145037322486604382006-04-14T12:55:00.000-05:002006-04-14T12:55:00.000-05:00I have wasted much time trying to schedule meeting...<I><BR/>I have wasted much time trying to schedule meetings. Ideally I'd like a system that searches everyone's calendars and finds a common free time. <BR/></I><BR/>Isn't that an NP-Complete problem? :)Anonymousnoreply@blogger.com