Category Archives: Algorithmic Miniworkshops

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 Krzysztof 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 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 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.

Miniworkshop on 26.02.2015

On 26.02.2015 as a part of our logo FNPFoundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Archontia Giannopoulou. The title of the talk is “Uniform Kernelization Complexity of Hitting Forbidden Minors” and the abstract is given below.

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

Abstract:

The F-Minor-Free Deletion problem asks, for a fixed set F and an input consisting of a graph G and integer k, whether k vertices can be removed from G such that the resulting graph does not contain any member of F as a minor. It generalizes classic graph problems such as Vertex Cover and Feedback Vertex Set.  Fomin et al. (FOCS 2012) showed that the special case Planar-F-Minor-Free Deletion (when F contains at least one planar graph) has a kernel of polynomial size: instances (G,k) can efficiently be reduced to equivalent instances (G’,k) of size f(F)k^{g(F)} for some functions f and g. The degree g of the polynomial grows very quickly; it is not even known to be computable. Fomin et al. left open whether Planar-F-Minor-Free Deletion has kernels whose size is uniformly polynomial, i.e., of the form f(F) k^c$ for some universal constant c that does not depend on F.
In this talk we discuss to what extent provably effective and efficient preprocessing is possible for F-Minor-Free Deletion. In particular, we show that not all Planar-F-Minor-Free Deletion problems admit uniformly polynomial kernels but also that there exist problems that do admit uniformly polynomial kernels.