Skip to main content
To KTH's start page

Counting Set Covers

Speaker: Andreas Björklund, Lund Institute Of Technology

Time: Mon 2006-11-20 13.15 - Wed 2013-10-23 13.00

Location: Room 1537

Export to calendar

Abstract:

In a Set Cover problem we are given a ground set U of size n and a family S of size m of subsets of U and we want to know if U can be covered by k of the sets from S. We give two related algorithms which are stronger than applying dynamic programming over all subsets of U.

  1. We demonstrate a simple technique solving the problem in space $\poly(n,\log m)$ and time $\poly(n,\log m)m2^n$ which actually counts the number of solutions.
  2. We show that with exponential space we can count the solutions in time $\poly(n,\log m)(m+2^n)$ which gives us the fastest algorithms for Chromatic Number and Domatic Number known to date.

Based on two recent papers with Thore Husfeldt announced at ICALP 2006 and FOCS 2006. The seminar will be roughly 45 minutes long.

To the calendar