Miniworkshop on 03.03.2016

On 03.03.2016 as a part of our logo FNPFoundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Krzystof Sormat. He will give a talk on his recent result on “PTAS for Minimax Approval Voting”. The abstract is given below.

We plan to have a group discussion and joint lunch after his talk.

Abstract:

J. Byrka, K. Sornat. PTAS for Minimax Approval Voting. WINE 2014.
http://arxiv.org/abs/1407.7216

We consider Approval Voting systems where each voter decides on a subset to candidates he/she approves. We focus on the optimization problem of finding the committee of fixed size k minimizing the maximal Hamming distance from a vote. In this paper we give a PTAS for this problem and hence resolve the open question raised by Carragianis et al. [AAAI’10]. The result is obtained by adapting the techniques developed by Li et al. [JACM’02] originally used for the less constrained Closest String problem. The technique relies on extracting information and structural properties of constant size subsets of votes.

Miniworkshop on 21.01.2016

On 21.01logo FNP.2016 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Tomasz Kociumaka. He will give a talk on his recent result on “Optimal Dynamic Strings”. The abstract is given below.

We plan to have a group discussion and joint lunch after his talk.

Abstract:

We study the fundamental problem of maintaining a dynamic collection
of strings under the following operations: concatenate two strings,
split a string into two at a given position, determine the
lexicographical order (smaller, equal, greater) between two strings,
calculate the longest common prefix of two strings. We present a data
structure for this problem, in which updates require only O(log n)
worst-case time with high probability, with n being the total length
of all strings in the collection, and queries take constant worst-case
time. On the lower bound side, we prove that even if the only possible
query is checking equality of two strings, either updates or queries
must take amortized Ω(log n) time; hence our implementation is
optimal. Our data structure can be used as a basic building block to
solve other string problems, such as pattern matching in dynamic
string collections, pattern matching in a history is an edited text,
and processing grammar-compressed strings.

Joint work with Paweł Gawrychowski, Jakub Łącki, Adam Karczmarz, and Piotr Sankowski

Miniworkshop on 10.12.2015

logo FNPOn 10.12.2015 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Paweł Gawrychowski. He will give a talk on his recent result on “Approximating LZ77 via Small-Space Multiple-Pattern Matching”. The abstract is given below.

We plan to have a group discussion and joint lunch after his talk.

Abstract:

We generalize the well-known Karp-Rabin string matching to handle
multiple patterns in O(nlogn+m) time and O(s) space, where n is the
length of the text and m is the total length of the s patterns,
returning correct answers with high probability. As a prime
application of our algorithm, we show how to approximate the LZ77
parse of a string of length n. If the optimal parse consists of z
phrases, using only O(z) working space we can return a parse
consisting of at most (1+ε)z phrases in O(1/ε n logn) time, for any
ε∈(0,1].

Joint work with Johannes Fischer, Travis Gagie, and Tomasz Kociumaka.

Miniworkshop on 12.11.2015

Onlogo FNP 12.11.2015 as a part of our Foundation for Polish Science  Algorithmic Miniworkshop series we will host Ariel Gabizon from Technion. He will give a talk on his recent result on “Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints”. The abstract is given below.

We plan to have a group discussion and joint lunch after his talk.

Abstract:

We consider generalized versions of well-studied problems in parameterized complexity and exact exponential time algorithms. The generalizations are obtained by introducing a relaxation parameter, which relaxes the constraints on feasible solutions. For example, one can generalize Hamiltonian path to the problem of finding a spanning tree where all degrees are at most some integer d. Or one can generalize k-Path to the task of finding a walk of length k where any vertex is visited at most r times. This problem was first considered by Abasi et. al who showed a randomized algorithm where the running time improves with the parameter r. We derandomize their algorithm. We also obtain an algorithm for Bounded-Degree Spanning Tree, where the running time improves with the degree bound d, improving an algorithm of Fomin et al. with running time 2^{n+o(n)} for any d.On the way to obtain our results we generalize the notion of representative sets to multisets, and give an efficient algorithm to compute such representative sets. Both the generalization of representative sets to multisets and the algorithm to compute them may be of independent interest.Joint work with Daniel Lokshtanov and Michał Pilipcuzk

 

Miniworkshop on 18.06.2015

On 18.06.2015 as a part of our logo FNP Foundation for Polish Science Algorithmic Miniworkshop series we will host Evangelos Kranakis from Carleton University. He will give a talk on his recent result on “Robot Evacuation”. The abstract is given below.

We plan to have a group discussion and joint lunch after his talk.

Abstract:

Consider k mobile robots inside a circular disk of unit radius. The robots are required to evacuate the disk through an unknown exit point situated on its boundary. We assume all robots having the same (unit) maximal speed and  starting at the centre of the disk. The robots may communicate in order to inform themselves about the presence (and its position) or the absence of an exit. The goal is for all the robots to evacuate
through the exit in minimum time.
We consider two  models of communication between the robots: in non-wireless (or local) communication model robots exchange information only when simultaneously located at the same point, and wireless communication in which robots can communicate one another at any time.
We study the following question what is the optimal evacuation time for k robots?

 

Miniworkshop on 28.05.2015

On 28.05.2015 as a part logo FNPof our Foundation for Polish Science Algorithmic Miniworkshop series we will host Giuseppe F. Italiano from  University of Rome “Tor Vergata”. He will give a talk on his recent result on “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching”. The abstract is given below.

We plan to have a group discussion and joint hamburger lunch after his talk.

Abstract:

We present the first deterministic data structures for maintaining
approximate  minimum vertex cover and maximum matching in a fully
dynamic graph in $o(\sqrt{m}\,)$ time per update. In particular, for
minimum vertex cover we provide deterministic data structures for
maintaining a $(2+\eps)$ approximation in $O(\log n/\eps^2)$ amortized
time per update. For maximum matching, we  show how to  maintain a
$(3+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em amortized} time
per update, and a $(4+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em
worst-case} time per update. Our data structure for fully dynamic
minimum vertex cover is essentially near-optimal and settles an open
problem by Onak and Rubinfeld~\cite{OnakR10}.

Joint work with Sayan Bhattacharya and Monika Henzinger.

 

Topics of the next few lectures

The lectures were based on the following papers:
8. Lecture by Erik Demaine on Van Emde Boas trees: http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf
9. Lecture by Erik Demaine on Ordered List Maintenance: http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L14/lecture14.pdf
11. Paper on pattern matching in dynamic texts: http://www.cs.au.dk/~gerth/papers/diku-98-27.pdf

Miniworkshop on 14.05.2015

Ologo FNPn 14.05.2015 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will host Artur Czumaj from University of Warwick. He will give a talk on his recent result on “Random permutations using switching networks”. The abstract is given below.

We plan to have a group discussion and joint hamburger lunch after his talk.

Abstract:

We consider the problem of designing a simple, oblivious scheme to generate (almost) random permutations. We use the concept of switching networks and show that almost every switching network of logarithmic depth can be used to almost randomly permute any set of (1-epsilon)n elements with any epsilon>0 (that is, gives an almost (1-epsilon)n-wise independent permutation). Furthermore, we show that the result still holds for every switching network of logarithmic depth that has some special expansion properties, leading to an explicit construction of such networks. Our result can be also extended to an explicit construction of a switching network of depth O(log^2n) and with O(n log n) switches that almost randomly permutes any set of n elements. We also briefly discuss basic applications of these results in cryptography.

Our results are obtained using a non-trivial coupling approach to study mixing times of Markov chains which allows us to reduce the problem to some random walk-like problem on expanders.

Topics for the first few lectures

The lectures were based on the following papers:
1. A data structure for dynamic trees by Sleator and Tarjan 1982,  https://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf
2. Lecture on dynamic graph connectivity by Virginia V. Williams http://theory.stanford.edu/~virgi/cs267/lecture10.pdf
3. Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications by Frederickson 1984, https://csclub.uwaterloo.ca/~gzsong/papers/Data%20Structures%20for%20On-Line%20Updating%20of%20Minimum%20Spanning%20Trees,%20with%20Applications.pdf
4. Dynamic Transtive Closure via Dynamic Matrix Inverse by Sankowski 2004, www.mimuw.edu.pl/~sank/pub/sankowski_focs04.ps
5. Subquadratic Algorithm for Dynamic Shortest Distances by Sankowski 2005, http:///chapter/10.1007%2F11533719_47
6. A New Approach to Dynamic All Pairs Shortest Paths by Demetrescu and Italiano 2003, www.dis.uniroma1.it/~demetres/docs/dapsp-full.pdf
7. Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles by Thorup 2004, http://link.springer.com/chapter/10.1007%2F978-3-540-27810-8_33

Miniworkshop on 09.04.2015

logo FNPOn 09.04.2015 during our Foundation for Polish Science Algorithmic Miniworkshops we will host Mikkel Thorup from University of Copenhagen. He will give a talk on his recent result on “Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time”. The abstract is given below.

We plan to have a group discussion and joint pierogi lunch after his talk (sponsored by FNP).


 

Ken-ichi Kawarabayashi, National Institute of Informatics, Tokyo, Japan

Mikkel Thorup, University of Copenhagen, Denmark

Abstract

We present a deterministic near-linear time algorithm that computes the edge-connectivity and finds a minimum cut for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem.  In near-linear time we can also construct the classic cactus representation of all minimum cuts.

The previous fastest deterministic algorithm by Gabow from STOC’91 took ~O(m+k^2 n), where k is the edge connectivity, but k could be Omega(n).

At STOC’96 Karger presented a randomized near linear time Monte Carlo algorithm for the minimum cut problem.  As he points out, there is no better way of certifying the minimality of the returned cut than to use Gabow’s slower deterministic algorithm and compare sizes.

Our main technical contribution is a near-linear time algorithm that contract vertex sets of a simple input graph G with minimum degree d, producing a multigraph with ~O(m/d) edges which preserves all minimum cuts of G with at least 2 vertices on each side.

In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS’06. Normally such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.