We're excited to announce a new online seminar on Frontiers of Parameterized
Complexity with talks scheduled weekly on Thursdays at at 17.00, Bergen time
(GMT+2).
Please save the date for the following up-coming Virtual Seminar on Frontiers
of Parameterized Complexity. Individuals and viewing party groups
from around the world can "attend" these online talks and interact
with the speaker and other attendees remotely via Zoom.
More details can be found here:
https://frontpc.blogspot.com/2020/04/talks-schedule.html
The first talk will be held on 23rd April 2020.
https://uib.zoom.us/j/4231169675
Meeting ID: 423 116 9675
Password: name of the W[1]-complete problem, 6 letters, all capital.
Also known as a set of pairwise adjacent vertices.
April 23, 2020
Jesper Nederlof, Utrecht University
Title: Bipartite TSP in O(1.9999^n) Time, Assuming Quadratic Time
Matrix Multiplication
Abstract:
The symmetric traveling salesman problem (TSP) is the problem of
finding the shortest Hamiltonian cycle in an edge-weighted undirected
graph. In 1962 Bellman, and independently Held and Karp, showed that
TSP instances with n cities can be solved in O(n^2*2^n) time. Since
then it has been a notorious problem to improve the runtime to
O((2-eps)^n) for some constant eps >0. In this work we establish the
following progress: If (s x s)-matrices can be multiplied in
s^{2+o(1)} time, than all instances of TSP in bipartite graphs can be
solved in O(1.9999^n) time by a randomized algorithm with constant
error probability. We also indicate how our methods may be useful to
solve TSP in non-bipartite graphs.
On a high level, our approach is via a new problem called the
MINHAMPAIR problem: Given two families of weighted perfect matchings,
find a combination of minimum weight that forms a Hamiltonian cycle.
As our main technical contribution, we give a fast algorithm for
MINHAMPAIR based on a new sparse cut-based factorization of the
`matchings connectivity matrix', introduced by Cygan et al. [JACM'18].
Other upcoming talks include:
April 30 2020:
Daniel Lokshtanov, UCSB
Title: A Parameterized Approximation Scheme for Min k-Cut
May 07 2020:
Jason Li, CMU
Title: To be announced
May 14 2020:
Vincent Cohen-Addad, Google Zürich
Title: On the Parameterized Complexity of Various Clustering Problems
For more details contact one the following.
Roohani Sharma: roohani.sharma90@gmail.com
Saket Saurabh: saket@imsc.res.in
Fedor Fomin: Fedor.Fomin@uib.no
----------------------
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
