12 Feb 10:15 Pekka Parviainen: A Space--Time Tradeoff for Permutation Problems

HIIT seminar, Friday Feb 12, 10:15 a.m. (coffee from 10), Exactum B222

Pekka Parviainen
Helsinki Institute for Information Technology HIIT Department of Computer Science University of Helsinki

A Space--Time Tradeoff for Permutation Problems

Abstract:
Many combinatorial problems—such as the traveling salesman, feedback arcset, cutwidth, and treewidth problem— can be formulated as finding a feasible permutation of n elements. Typically, such problems can be solved by dynamic programming in time and space O^*(2^n), by divide and conquer in time O^*(4^n) and polynomial space, or by a combination of the two in time O^*(4^n 2^−s) and space O^*(2^s) for s = n, n/2, n/4,... . Here, we show that one can improve the tradeoff to time O^*(T^n) and space O^*(S^n) with TS < 4 at any 2^(1/2) < S < 2. The idea is to find a small family of "thin" partial orders on the n elements such that every linear order is an extension of one member of the family. Our construction is optimal within a natural class of partial order families.

This is joint work with Mikko Koivisto.