-
© Universität Bielefeld
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
teaching:2024summer:karp [2024/03/11 16:10] rwittler |
teaching:2024summer:karp [2024/04/23 11:28] (current) rwittler |
||
|---|---|---|---|
| Line 8: | Line 8: | ||
| \\ | \\ | ||
| - | Based on a classical research paper, the participants will give oral presentations and write short summaries about algorithmic problems and their complexity. Algorithmic solutions will be discussed and, as a practical exercise, implemented in a proof-of-concept fashion. Talks and essays can be done in German or English. The first day covers an introduction into the topic and an overview of possible topics, which will then be distributed to the students. Aspects of scientific writing and presenting will be covered as well. | + | Based on a classical research paper, the participants will give oral presentations and write short summaries about algorithmic problems and their complexity. Formal problems / algorithmic solutions will be discussed and, as a practical exercise, implemented in a proof-of-concept fashion. Talks and essays can be done in German or English. The first day covers an introduction into the topic and an overview of possible topics, which will then be distributed to the students. Aspects of scientific writing and presenting will be covered as well. |
| \\ | \\ | ||
| \\ | \\ | ||
| - | The overarching topic of this semester are "Karp's 21 NP-complete problems": [[https://pdfs.semanticscholar.org/a3c3/7657822859549cd6b12b0d1f76f8ee3680a0.pdf|Richard M. Karp. "Reducibility among combinatorial problems" (1972)]] | + | The overarching topic of this semester are "Karp's 21 NP-complete problems": [[https://link.springer.com/content/pdf/10.1007/978-1-4684-2001-2_9.pdf|Richard M. Karp. "Reducibility among combinatorial problems" (1972)]] |
| In this work, Karp shows NP-hardness of many classical, important formal problems, mainly by listing reductions/equivalence between them. The given reductions appear like brief cooking recipes, but no intuition or proof of equivalence is provided. The relations are not too obvious but also not too hard to see -- excellent exercises for understanding formal statements, logical thinking, formal writing etc. | In this work, Karp shows NP-hardness of many classical, important formal problems, mainly by listing reductions/equivalence between them. The given reductions appear like brief cooking recipes, but no intuition or proof of equivalence is provided. The relations are not too obvious but also not too hard to see -- excellent exercises for understanding formal statements, logical thinking, formal writing etc. | ||
| \\ | \\ | ||
| \\ | \\ | ||
| - | {{karp-fig1.png}} | + | {{teaching:2024summer:karp:karp-fig1.png}} |
| Line 28: | Line 28: | ||
| Concrete tasks are: | Concrete tasks are: | ||
| + | * Carefully read the original publication of Karp until 17 April | ||
| * Understand the two problems (A and B) | * Understand the two problems (A and B) | ||
| * Understand the reduction from B to A | * Understand the reduction from B to A | ||
| Line 36: | Line 37: | ||
| * example for the reduction | * example for the reduction | ||
| * research on approximations, heuristics, problem variants | * research on approximations, heuristics, problem variants | ||
| - | * A (naiv) implementation including a stress test (How far can we get with this?) | + | * A (naive) implementation including a stress test (How far can we get with this?) |
| \\ | \\ | ||
| Line 42: | Line 43: | ||
| \\ | \\ | ||
| - | | Clique (from Satisfiability) | as example by Kassian and Roland | | + | * Set Packing (from Clique) |
| - | | Set Packing (from Clique) | | | + | * Exact Cover (from Chromatic Number) |
| - | | Feedback Arc Set (from Node Cover) | | | + | * Partition (from Knapsack) |
| - | | Exact Cover (from Chromatic Number) | | | + | * Steiner Tree (from Exact Cover) |
| - | | Hitting Set (from Exact Cover) | | | + | \\ |
| - | | Steiner Tree (from Exact Cover) | | | + | |
| - | | 3-dim. Matching (from Exact Cover) | | | + | As backup, we could also do: |
| - | | Knapsack (from Exact Cover) | | | + | * Feedback Arc Set (from Node Cover) |
| - | | Sequencing (from Knapsack) | | | + | * Hitting Set (from Exact Cover) |
| - | | Partition (from Knapsack) | | | + | * Knapsack (from Exact Cover) |
| + | * Sequencing (from Knapsack) | ||
| + | \\ | ||
| + | \\ | ||
| + | |||
| + | ^ Day ^ Topic ^ Responsible person ^ | ||
| + | | 10.04. | Overview | all | | ||
| + | | 17.04. | Discussion of Karp's Paper | all | | ||
| + | | | Repetition NP-completeness | Roland ({{:teaching:2024summer:karp:np_completeness.pdf|slides}}) | | ||
| + | | | Example: Clique (from Satisfiability) | Kassian | | ||
| + | | 24.04. | [[:teaching:2024summer:karp:writing|Scientific writing]] & presentations | Roland {{:teaching:2022summer:algbioinf:howtoread.pdf|Slides: HowToRead}} [[https://chat.openai.com/share/b941110b-63ce-4355-8a7f-28fd6dcc8906 | ||
| + | |chatGPT: Beautifully phrased nonsense]] | | ||
| + | | 01.05. | -- (national holiday) || | ||
| + | | 08.05. | | | | ||
| + | | 15.05. | | | | ||
| + | | 22.05. |Set Packing |Olivia (Kassian)| | ||
| + | | 29.05. | Exact Cover|Enna (Roland)| | ||
| + | | 05.06. | | | | ||
| + | | 12.06. | | | | ||
| + | | 19.06. | Partition| Asal (Kassian)| | ||
| + | | 26.06. | Steiner Tree| Franziska (Roland)| | ||
| + | | 03.07. | Abgabe Implementierung | | | ||
| + | | 10.07. | presentation of implementations | all | | ||
| + | | 17.07. | | | | ||
teaching/2024summer/karp.1710169832.txt.gz · Last modified: 2024/03/11 16:10 by rwittler
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International