Category Archives: events

Invitation to Award Ceremony of the ESA Test-of-Time Award 2016

Posted on by
Reply

____________________________________________________________
On behalf of the Steering Committee of ESA and the Program Committee of ESA 2017,
I would like to invite you to attend the ESA conference and the ESA Test-of-Time 2016 Award Ceremony. The ceremony will take place on the afternoon of 5th of September during ESA 2017 in Vienna and it will include the presentation by the awardees of the recognized paper.
_____________________________________________________
Announcement of the ESA Test-of-Time Award 2016

European Symposium on Algorithms (ESA)
http://esa-symposium.org/
____________________________________________________________

The ESA Test-of-Time Award (ESA ToTA) recognizes excellent papers in algorithms research that were published in the ESA proceedings 19-21 years ago and which are still influential and stimulating for the field today. In this second year in which the award is given, papers from ESA'95 to ESA'97 were considered.

The committee nominates the following paper for the ESA ToTA 2016. The paper stands out as a classic in the algorithms field and by its excellent citation
record still relevant today.

From ESA 95-97:

Boris V. Cherkassky, Andrew V. Goldberg
Negative-cycle detection algorithms
Proceedings ESA'96, also in: Mathematical Programming 85:2 (1999) 277-311

Laudation:
The paper by Cherkassky and Goldberg deals with the problem of finding a
negative-length cycle in a network or proving that there is none. Algorithms
for this are a combination of a shortest-path algorithm and a negative-cycle
detection strategy. The authors analyse known algorithms and some new ones
and determine the best combinations. Novel instance generators are used in
this study. The paper is a model experimental paper in algorithms.

ESA ToTA 2016 Award Committee:
Kurt Mehlhorn (Saarbrucken)
Mike Paterson (Warwick)
Jan van Leeuwen (Utrecht)
____________________________________________________________

Workshop on Kernelization 2013

Posted on by
Reply

Last week we organized Workshop on Kernelization (WorKer 2013) in Warsaw. The programmee included

  • an update meeting on graph cut problems,
  • two tutorials (Matroid theory and kernelization by Saket Saurabh, Stefan Kratsch and Magnus Wahlström and Kernel-size lower bounds: the evidence from complexity theory by Andrew Drucker),
  • two invited talks on techniques used outside the kernelization area which might turn out useful in kernelization (on planar graphs by Piotr Sankowski and on spanners by Seth Pettie)
  • a few short contributed talks

We hope it was fun! Below you can see some pictures.

5th Workshop on Flexible Network Design

Posted on by
Reply

Last week we have hosted the 5th Workshop on Flexible Network Design. There have been a great number of interesting talks: http://fnd2012.mimuw.edu.pl/?q=node/4, and huge number of open problems. The open problems can be posted and discussed here: http://fnd2012.mimuw.edu.pl/qa.

Below there are some photos from the workshop.

Polish ICALP ;)

Posted on by
Reply

This blog is maintained by members of Algorithmic group at University of Warsaw:

  • Krzysztof Ciebiera
  • Marek Cygan
  • Łukasz Kowalik
  • Jakub ??cki
  • Marcin Mucha
  • Marcin Pilipczuk
  • Piotr Sankowski

Finally, were able to show how to find minimum weight perfect matchings in non-bipartite graph using matrix multiplication. This was some years of trying after my paper from ICALP 2006, where the bipartite case was solved. However, with big help of Marek Cygan and Hal Gabow we have found rather elegant solution. The algorithm is very simple and given blow. Nevertheless, the proof of it correctness is not straight forward and requires some nontrivial structural properties.

Minimum weight perfect matching algorithm:

  • Remove non-allowed edges from the graph, i.e., edges that do not belong to any minimum weight perfect matching,
  • Compute M(v) minimum weight almost perfect matching that misses the vertex v,
  • Define new weights of edges w’(uv) = w(uv) + w(M(u)) + w(M(v)),
  • Connected components of E = {uv : w’(uv)<a}, for all a, encode the family of blossoms,
  • Using algorithm for maximum cardinality matchings find a matching that crosses each blossom once.

This gives an algorithm working in time, where W is the maximal edge weight and ? is the matrix multiplication exponent. In the case of dense graphs with small integral weights our algorithm is faster than the O(n(m+n log n)) time algorithm of Gabow from 90 and the time algorithm of Gabow and Tarjan from 91. Previously known algorithms for this problem were using augmenting paths. This algorithm is very different and is based on structural properties that give combinatorial relation between matchings weights and the dual solution. In particular, we show that there exists a canonical dual solution that is unique.

During the work we realized that the tools developed in the paper, i.e., usage of Baur-Strassen’s theorem for the computation of allowed edges, can be used to solve other problems as well. The framework appeared to be very powerful and we were able to solve the shortest cycle problem and the diameter problem in their full generality. Previous solutions for these problems that used matrix multiplication did not handle the case of undirected graphs with negative weights. Observe that in such case even detecting whether a graph has negative length cycle is nontrivial. The Bellman-Ford algorithm does not work here as it works only in the case of directed graphs. However, the problem can be solved by a reduction to the minimum weight perfect matching problem.

After the submission we realized that some other problems can be solved using this framework. One can compute the radius of the graph, as well as solve the single source shortest path problem in undirected graph with negative weights, but without negative weight cycles. Previously known algorithm for shortest paths worked only in the case of directed graphs with negative weights.
This was a rather interesting ICALP in Warwick. Actually, some people called it Polish ICALP ;). There was a visible number of participants who were from Poland as well as the ones who graduated from our universities. This includes the main organizer Artur Czumaj. During the event we realized to be the only university that had a PC member in every track:

  • in Track A - Piotr Sankowski,
  • in Track B - Bartek Klin and Andrzej Tarlecki,
  • in Track C - Stefan Dziembowski.