SoCG 2009 will take place on the 8-10 of June in Aarhus, Denmark. I'm sure it will be a lot of fun to visit Aarhus and Lars, especially since Sweden is playing against Denmark in the football world cup qualification on the 6th of June!
Here's the CFP.
Btw, why is Århus the city spelt with an `Å' while Aarhus University is spelt with `Aa’?
Monday, September 29, 2008
Wednesday, September 10, 2008
Algoritmics in NZ
The algorithmic activities in New Zealand continues. At the 7th Australia – New Zealand Mathematics Convention in Christchurch there will be a special algoritmics session. This special session is part of the thematic programme on Algorithmics funded by the New Zealand Institute for Mathematics and its Applications (NZIMA).
Also, Bernard Chazelle will give a series of public lectures in the period 13-22 March 2009.
Also, Bernard Chazelle will give a series of public lectures in the period 13-22 March 2009.
Sunday, September 7, 2008
Clustering trajectories
Late last year I attended a (great) workshop in the Netherlands organised by Marc van Kreveld. From that workshop a few (!) papers came out. One of them was just accepted to ISAAC - "Detecting Commuting Patterns by Clustering Subtrajectories" by Kevin Buchin, Maike Buchin, Jun Luo, Maarten Löffler and me.
The problem of clustering trajectories is surprisingly hard. In the data mining/database community there are several papers on this problem that are fairly fast but not very accurate (useful?).
In the paper we focus on finding subtrajectories of a single trajectory that forms a cluster (can easily be extended to the general clustering problem). This is useful for detecting, e.g., commuting patterns or seasonal migration behaviour. Our approach builds on the Frechet distance and heavily makes use of the freespace diagram. This gives an accurate definition of a trajectory cluster (imho) but it is very costly to compute (both in time and space). The running time is roughly quadratic (for most settings) and a (non-optimised) implementation can handle 10K points in roughly 20 minutes.
The obvious open problem is: Is there an accurate definition of a trajectory cluster that would allow for a more efficient implementation?
The problem of clustering trajectories is surprisingly hard. In the data mining/database community there are several papers on this problem that are fairly fast but not very accurate (useful?).
In the paper we focus on finding subtrajectories of a single trajectory that forms a cluster (can easily be extended to the general clustering problem). This is useful for detecting, e.g., commuting patterns or seasonal migration behaviour. Our approach builds on the Frechet distance and heavily makes use of the freespace diagram. This gives an accurate definition of a trajectory cluster (imho) but it is very costly to compute (both in time and space). The running time is roughly quadratic (for most settings) and a (non-optimised) implementation can handle 10K points in roughly 20 minutes.
The obvious open problem is: Is there an accurate definition of a trajectory cluster that would allow for a more efficient implementation?
Monday, August 25, 2008
Friday, August 1, 2008
Pay to get published?
Recently I was kindly offered to become an editor for a new open access journal called ALGORITHMS published by MDPI. At first sight it looked as a great idea, and the editorial board contains some very impressive researchers. However, when I started to read the instructions for call for papers more closely I realised that the authors of an accepted paper have to pay roughly 1000 CHF (roughly the same in Australian/US dollars).
So instead of letting the readers pay for the journal the authors have to pay for their articles to get published. In the theory community we don't have the tradition of paying for our publications. On one hand this approach is much cheaper for the community but can you guarantee quality in this system? It's not obvious that one system is better than the other but personally I rather pay to read a paper than to publish it. However, I'm very curious to hear what other researchers think about this.
So instead of letting the readers pay for the journal the authors have to pay for their articles to get published. In the theory community we don't have the tradition of paying for our publications. On one hand this approach is much cheaper for the community but can you guarantee quality in this system? It's not obvious that one system is better than the other but personally I rather pay to read a paper than to publish it. However, I'm very curious to hear what other researchers think about this.
Thursday, July 24, 2008
SWAT - Day 2
I wrote this entry about two weeks ago but haven't had a chance to post it. Better late than never...
Today's highlight was definitely the invited talk by Michael Mitzenmacher on deletion channels (his talk, and a survey, is available). Again a topic that I didn't know much about, but Michael's presentation gave me a good understanding of the basic problem and the questions that are important in this area. A deletion channel is a channel where n bits are sent, but each bit is independently deleted with fixed probability p. (Different from the erasure channel where each bit can be replaced by a `?', or the symmetric channel where each bit can be flipped). The main question is to decide the capacity of the channel. Michael showed that the lower bound (which is really an upper bound) is at least (1-p)/9. However, he also stated several interesting fundamental problems during his talk. For example, how do random subsequences of random sequences behave?
The conference dinner (I, & II) was held in a beautiful location just to the south of Gothenburg looking out on the archipelago. While the sun was setting we had good food and tried to come up with a new name for SWAT (I, II & III). The local organisers did a great job finding the place and arranging a historic tram trip to the venue.
Today's highlight was definitely the invited talk by Michael Mitzenmacher on deletion channels (his talk, and a survey, is available). Again a topic that I didn't know much about, but Michael's presentation gave me a good understanding of the basic problem and the questions that are important in this area. A deletion channel is a channel where n bits are sent, but each bit is independently deleted with fixed probability p. (Different from the erasure channel where each bit can be replaced by a `?', or the symmetric channel where each bit can be flipped). The main question is to decide the capacity of the channel. Michael showed that the lower bound (which is really an upper bound) is at least (1-p)/9. However, he also stated several interesting fundamental problems during his talk. For example, how do random subsequences of random sequences behave?
The conference dinner (I, & II) was held in a beautiful location just to the south of Gothenburg looking out on the archipelago. While the sun was setting we had good food and tried to come up with a new name for SWAT (I, II & III). The local organisers did a great job finding the place and arranging a historic tram trip to the venue.
Sunday, July 13, 2008
SWAT - Day 1
A bit late but here's a short summary of SWAT day 1:
I'm in Gothenburg attending SWAT 2008. I haven't been in Gothenburg since I was a kid but it's a beautiful city this time of the year. Due to the long and warm summer evening there are heaps of people everywhere. Apart from SWAT there's also the worlds largest youth handball tournament going on with 900 teams from all around the world.
The local organisers of SWAT seem to have everything under control. I don't have to worry about anything (except a nasty cold). The first day included some very nice talks. John Hershberger gave the first talk of the conference, "Simplified planar coresets for data streams" which gives a simple way of producing coresets for computing the extent of a point set in the plane. He (and Subhash Suri) combined several known techniques with a few nice ideas to obtain an optimal size coreset.
Another talk I enjoyed was on placing wireless devices in an internet cafe such that customers inside the cafe can be distinguished from people outside the cafe. The talk was given by Tobias Christ and they show that for a simple polygon with n vertices 3n/5 devices is sometimes necessary and that 4n/5 is always sufficient.
Vijay Vazirani gave a great invited talk on the relation between Nash bargaining and flexible markets. I don't know the area very well but Vijay gave a very good survey focussing on the fact that some of these problems can be stated as a convex program which can be shown to have a rational optimal solution which can be solved in polynomial time by using primal-dual techniques.
After the technical program there was a business meeting where various issues were discussed (more on that in an upcoming post), followed by a reception at the city hall (provided by the city of Gothenburg) and the PC dinner (for details of what was discussed see Michael's post).
I'm in Gothenburg attending SWAT 2008. I haven't been in Gothenburg since I was a kid but it's a beautiful city this time of the year. Due to the long and warm summer evening there are heaps of people everywhere. Apart from SWAT there's also the worlds largest youth handball tournament going on with 900 teams from all around the world.
The local organisers of SWAT seem to have everything under control. I don't have to worry about anything (except a nasty cold). The first day included some very nice talks. John Hershberger gave the first talk of the conference, "Simplified planar coresets for data streams" which gives a simple way of producing coresets for computing the extent of a point set in the plane. He (and Subhash Suri) combined several known techniques with a few nice ideas to obtain an optimal size coreset.
Another talk I enjoyed was on placing wireless devices in an internet cafe such that customers inside the cafe can be distinguished from people outside the cafe. The talk was given by Tobias Christ and they show that for a simple polygon with n vertices 3n/5 devices is sometimes necessary and that 4n/5 is always sufficient.
Vijay Vazirani gave a great invited talk on the relation between Nash bargaining and flexible markets. I don't know the area very well but Vijay gave a very good survey focussing on the fact that some of these problems can be stated as a convex program which can be shown to have a rational optimal solution which can be solved in polynomial time by using primal-dual techniques.
After the technical program there was a business meeting where various issues were discussed (more on that in an upcoming post), followed by a reception at the city hall (provided by the city of Gothenburg) and the PC dinner (for details of what was discussed see Michael's post).
Subscribe to:
Posts (Atom)
