Algorithms for NP-hard Problems

RemarkPlease note that even though the website language can be changed, the majority of course materials (slides, video) are available in Russian only.

General Info

Lecturer	A. S. Kulikov
Term	Fall 2009
Beginning date	Sunday, September 13, 2009
Number of pairs	12
Course language	Russian
Video	http://lektorium.tv/course/?id=22758

Abstract We will consider some interesting ideas of designing algorithms for NP–hard problems — from classical to recent ones. Preliminary program: exact algorithms (splitting, local search, clever enumeration, reduction to an easy problem), fixed parameter tractable algorithms (kernelization, color coding, algorithms based on matrix multiplication and inclusion–exclusion principle), approximation algorithms (algorithms based on linear and semidefinite programming).

Links

First lecture slides

View more presentations from Computer Science Club.

Lectures


1. Survey (Sunday, September 13, 2009 - 10:00) P и NP informally. Exact algorithms. $\sqrt{3}^n$ algorithm for SAT based on local search. $1.732^n$ algorithm for MAX-CUT based on fast matrix multiplication. 20090913_algorithmsfornphardproblems_kulikov_lecture01.pdf http://video.yandex.ru/users/pdmicsclub/view/1/?cauthor=pdmicsclub&cid=1
2. Survey (Sunday, September 13, 2009 - 10:15) FPT algorithms. Kernelization. $k(k+1)$ kernel for covering points by lines problem. $k(k+1)$ kernel for vertex cover based on simple reduction rules and $4k$ kernel based on crown decomposition lemma. Approximation algorithms. $2$ -optimal algorithm for vertex cover. $2$ -optimal algorithm for metric TSP. 20090913_algorithmsfornphardproblems_kulikov_lecture02.pdf http://video.yandex.ru/users/pdmicsclub/view/8/?cauthor=pdmicsclub&cid=1
3. NP-complete problems (Sunday, October 25, 2009 - 10:20) Search problems, NP-complete problems, reductions. 20091025_algorithmsfornphardproblems_kulikov_lecture03.pdf http://video.yandex.ru/users/pdmicsclub/view/29/
4. Randomized algorithms (Sunday, October 25, 2009 - 10:25) $1.5^n$ algorithm for the $3$ -coloring problem. $\log(2n)$ -optimal algorithm for the hitting set problem. FPT-algorithm for the $k$ -path problem. $2^{2n/3}$ -algorithm for $3$ -SAT. 20091025_algorithmsfornphardproblems_kulikov_lecture04.pdf http://video.yandex.ru/users/pdmicsclub/view/28/
5. Approximation algorithms (Sunday, November 1, 2009 - 10:30) $\log{n}$ -algorithm for the vertex cover problem, $2\log{n}$ -optimal algorithm for the shortest common superstring problem. 20091101_algorithmsfornphardproblems_kulikov_lecture05.pdf http://video.yandex.ru/users/pdmicsclub/view/32/
6. Approximation algorithms (Sunday, November 1, 2009 - 10:35) $3/2$ -optimal algorithm for the metric TSP, non-approximability of the general TSP, fully polynomial approximation scheme for the knapsack problem. 20091101_algorithmsfornphardproblems_kulikov_lecture06.pdf http://video.yandex.ru/users/pdmicsclub/view/30/
7. Approximation algorithms (Sunday, November 1, 2009 - 10:45) Semidefinite programming (SDP), SDP-based approximation algorithms, $0.87$ -optimal algorithm for the maximum cut problem, coloring $3$ -colorable graph into $O(d^{0.631})$ colors, where $d$ is the average degree. 20091115_algorithmsfornphardproblems_kulikov_lecture09.pdf http://video.yandex.ru/users/pdmicsclub/view/50/
8. Splitting algorithms (Sunday, November 8, 2009 - 10:35) Estimating the running time of splitting algorithms, reduction rules. Simple $1.415^K$ splitting algorithm for the satisfiability problem, where $K$ is the number of clauses. Automated complexity analysis of splitting algorithms. 20091108_algorithmsfornphardproblems_kulikov_lecture07.pdf http://video.yandex.ru/users/pdmicsclub/view/43/
9. Splitting algorithms (Sunday, November 8, 2009 - 10:40) Combined complexity measures (measure and conquer). Upper bound $2^{K/5.5}$ for the maximum $2$ -satisfiability problem. Solving SAT with constant clause density in less than $2^n$ steps. 20091108_algorithmsfornphardproblems_kulikov_lecture08.pdf http://video.yandex.ru/users/pdmicsclub/view/47/
10. Exact algorithms (Sunday, November 29, 2009 - 10:45) Inclusion-exclusion principle. Hamiltonian path problem, counting the number of perfect matchings. Reduction to easy problem. Subset sum problem, maximum 2-satisfiability problem. 20091129_algorithmsfornphardproblems_kulikov_lecture10.pdf
11. FPT-algorithms (Sunday, December 6, 2009 - 10:50) Sunflower lemma. Hitting set problem. Dynamic programming. Steiner tree problems. Iterative compression. Odd cycle transversal problem. 20091206_algorithmsfornphardproblems_kulikov_lecture11.pdf

Share |

Computer Science Club

Мою выпадающее меню

Algorithms for NP-hard Problems

Language

Случайное фото

User login