- Allan Borodin, Department of Computer Science, University of Toronto:
The Power and Limitations of Simple Algorithms: A Partial Case Study of
Greedy Mechanism Design for Combinatorial Auctions
Given the diversity of computational problems, models of computation,
solution concepts, and algorithmic approaches, it often seems a challenge
to view computer science/informatik as a coherent discipline. Fortunately,
various unifying ideas (e.g. NP-completeness) have brought significant
perspective to a very complex and ever expanding field.
In a less ambitious program, I have been thinking about simple algorithmic
approaches that arise frequently in approximation algorithms for
combinatorial optimization. To be more specific, I am in interested in
"greedy-like" algorithms and recently I am trying to understand the use of
such algorithms in combinatorial auctions. I will discuss some precise
models for simple greedy-like algorithms and how such algorithms can and
cannot achieve desirable properties such a truthfulness, and convergence
to "good" equilibria.
The ideas in this talk are based on recent work with Brendan Lucier and
also relate to Yuli Ye's talk in ICALP.
- Erik Demaine (MIT), "Actuator Nets: Folding, Reconfiguring, and Deploying
What happens when sensors can move around or otherwise change their geometry?
When all sensors can move (a robot swarm), we would like to be able to
determine and manipulate high-level properties, such as the boundary
of the swarm or the connectivity of the communication network.
When only a few sensors can move, we would like the mobile sensors to be able
to deploy immobile sensors to improve or repair the network connectivity
When the sensors are attached to a connected substrate, and they can
manipulate the substrate, we would like to be able to reconfigure the
substrate into arbitrary shapes.
I will describe several algorithmic projects to address all of these problems.