The list of SODA accepted papers is up.
For both my own curiosity, and probably Claire Mathieu's, does anyone have any ideas or suggestions on how to schedule parallel sessions? It seems like a nasty problem, particularly since you have limited information on what conflicts are, other than very general categories for papers.
Subscribe to:
Post Comments (Atom)
6 comments:
You surely know this
On a Theory of Computing Symposia
by Avrim Blum, Prabhakar Raghavan
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.3834
One possible source of information about conflicts is to use the info from the PC bids already stored in EasyChair. For example, you could consider the graph with papers as nodes. If a PC member bid "yes" for two papers, then a "2" is added to the weight on the edge between those two papers. If a PC member bid "maybe" for two papers, then another smaller weight such as "1" is added to the weight on the edge between the papers. Probably there are clusters in this graph (say a cluster is a dense subgraph). I wonder if there is more info in this graph than the obvious, e.g. computational geometry is a separate cluster from game theory. If there are clusters that are sparsely connected to each other, maybe they could be scheduled in parallel.
two comments...
first, i've talked with people in my own field about the following model. when people register for the conference, have them select a list of papers they'd really like to see. then apply some CSP algorithm or what not to that data. then, if someone complains about scheduling, you can blame it on them (either for not bidding well, or for not bidding at all).
second, you can try to schedule by looking at the references in the accepted papers, figuring that papers with lots of similar citations should go together (if possible) and never oppose each other.
this second is actually a hidden capability of WhatToSee. if you go to the what to see page, then click on a conference (eg., SODA 2007) -- click on the (i), not on the year... this will give you WhatToSee's list of the papers that year. now, edit the url so that instead of task=viewindex it has task=schedindex. this will automatically schedule into a multitrack conference (with four tracks) and five papers per track. (be warned: it takes quite a while.) if you want to change the number of tracks, add "&numTracks=2" to the url. if you want to change the number of papers per track, add "&perSession=15" to the url. it does some balancing -- add "&lambda=0.9" to make it care more about having similar stuff in the same session, or "&lambda=0.1" to make it care more about avoiding potential conflicts.
I like the ICML approach to it -- have many parallel sessions, and then have a poster session where all papers are showcased. That way, even if you missed a talk because of conflicts, you can always go see the poster.
Let us assume that we have affinity scores between each pair of papers. How should we schedule then? If the committee an any way trusts its judgement about the quality of papers then they should set a schedule so that an attendee can see all the best talks:
Let's be more specific using the SODA parameters: 3 concurrent sessions x 5 papers per session x 12 session time slots (up to 180 papers). Group the top 60 papers into groups of 5 base on some heuristic tryig to maximize affinity (this is the hardest part). Then the next 60, etc. All the top groups will be put in the A session, the next in the B session and finally the last in the C session. For each of the triples of groups - one from A, one from B, one from C compute the ordering of the B group and C group relative to A that minimizes the cross group total affinity score and record that optimal score as the penalty for that triple. Finally, try all possible of the 12! x 12! orderings of groups and take the one that minimizes the total penalty. (One could reduce the computation time significantly by first optimizing session B alone relative to A and then optimizing C after the first pairing of sessions between A and B has been fixed - the C papers are lower priority anyway.) Then nobody will have to miss any of the top papers
What the last anonymous suggests raises some issues as it will reveal information about the relative scores of the papers.
Usually, besides the "special issue" and "best paper" awards, such information is not made public.
Post a Comment