Sökning: id:"swepub:oai:lup.lub.lu.se:91a7594b-95d1-4741-a065-4c3470393e46" >
Algorithmic Bounds ...
Algorithmic Bounds for Presumably Hard Combinatorial Problems
-
- Björklund, Andreas (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
(creator_code:org_t)
- ISBN 9162870300
- 2007
- Engelska 71 s.
- Relaterad länk:
-
https://lup.lub.lu.s...
Abstract
Ämnesord
Stäng
- In this thesis we present new worst case computational bounds on algorithms for some of the most well-known NP-complete and #P-complete problems and their optimization variants. We consider graph problems like Longest Path, Maximum Cut, Number of Perfect Matchings, Chromatic and Domatic Number, as well as Maximum k-Satisfiability and Set Cover. Our results include I a) There is a polynomial--time algorithm always finding a path of length Omega((log n/ log log n)^2) in directed Hamiltonian graphs of constant bounded degree on n vertices. In undirected graphs on $n$ vertices with a long path of length L we give a polynomial--time algorithm finding Omega((log L/ log log L)^2) long paths. The technique used is a novel graph decomposition which inspired Hal Gabow to find the strongest approximation algorithm for Longest Path in undirected graphs known to date. I b) You cannot always in polynomial time find simple paths of length f(n) log^2 n or cycles of length f(n)log n for any non-decreasing function f(n) which is omega(1) and computable in subexponential time in directed Hamiltonian graphs of constant bounded degree on n vertices, unless there are 2^{o(n)} time deterministic algorithms for n-variable 3SAT. II a) There is a PTAS for MAXCUT on d-regular unweighted graphs on n vertices, containing O(d^4 log n) simple 4-cycles, for $d$ of omega(sqrt{n log n}). In particular, there is always a PTAS for d of Omega(n/log n) regardless of the number of 4-cycles. Moreover, MAXkSAT on n variables for constant k can be approximated in polynomial time with an absolute error of (epsilon+o(1))n^ksqrt{log log n/log n} for any fixed epsilon>0. The techniques used are low rank approximations, exhaustive search in few dimensions, and linear programming. II b) There is no PTAS for MAXCUT on unweighted graphs on n vertices of average degree delta for any delta less than n/(log n(log log n)^{omega(1)}), unless there are 2^{o(n)} time randomized algorithms for n-variable 3SAT. III) For any family S of subsets S_1,...,S_m of a ground set U of size n it is possible to count the number of covers of U in k pieces from S in time 2^nn^{O(1)} for any k as long as S is enumerable in that time bound. In particular the chromatic polynomial of a graph can be computed in time O(2^nn^3). The Chromatic Number in an n-vertex graph can be computed in time O(2.2461^n) using only polynomial space. The technique used is counting over an inclusion--exclusion formula.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- numerisk analys
- system
- control
- Datalogi
- numerical analysis
- systems
- Computer science
- Approximation algorithms
- Exact algorithms
- NP-hard problems
- Algorithm theory
- kontroll
Publikations- och innehållstyp
- dok (ämneskategori)
- vet (ämneskategori)
Hitta via bibliotek
Till lärosätets databas