Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Approximation Algorithms
& Molecular Algorithms

(2019/2020, 8x3h, 3 ECTS)
Wednesdays 8:45-11:45 Room SG1014

Presumed dates for the lectures:

Approximation algorithms

  • Lecture 1: Wed 11 SEP Approximation algorithms 1/4
  • Lecture 2: Wed 18 SEP Approximation algorithms 2/4
  • Lecture 3: Wed 25 SEP Approximation algorithms 3/4
  • Lecture 4: Wed 2 OCT Approximation algorithms 4/4

Molecular programming

  • Lecture 5: Wed 9 OCT Molecular algorithms 1/4
  • Lecture 6: Wed 16 OCT Molecular algorithms 2/4
  • Lecture 7: Wed 23 OCT Molecular algorithms 3/4
  • No lecture on Wed 30 OCT
  • Lecture 8: Wed 6 NOV Molecular algorithms 4/4

Final exam

  • No lecture on Wed 13 and 20 OCT
  • Final Exam: Wed 27 NOV 8:45-11:45

Teachers:

Lectures will take place every Wednesdays 08:45-11:45 in room SG1014 starting on 11/9.

Goals

This lecture explore actual trends in algorithms (and complexity). We will first focus on classic technique mainly based on randomness to obtain approximate solutions to NP-hard problems with proven guarantee. Second, we will explore how algorithms (randomized algorithms and structures) can help understanding better how nature works.

  1. Approximation algorithms: We will first learn how to provide guarantee on the quality of a solution with respect to the optimal when the optimal cannot be computed because either the problem considered is NP-hard or no known exact algorithms are fast enough to be effective. We will practise the various technics designed to analyze its cost guarantee. This field makes extensive use of randomness in order to improve performances.
  2. Molecular algorithms: The second part of the lectures will be dedicated to an introduction to the new field of molecular programming where people are developing theoretical algorithmic models and realizing in wetlab experiments computers compatible with life as we know it. Exploiting the flexibility of DNA molecule, implementations of this new of a kind computer are already happening. We will explore the very rich theory behind this field and hopefully realize some wetlab experiments together to implement algorithms using molecular interactions. Computations in these models are naturally random.

Approximation Algorithms

Approximation algorithm design essentially consists on the positive side in finding the proper relaxation of the constraints in the initial problem in order to get a polynomial-time estimate of the optimal that can then be converted into a solution of the initial problem. The art consists in showing that the quality of the solution does not change in the process. Typical tools are linear and semi-definite programming. On the negative side, it consists in using the celebrated PCP theorem and polynomial reductions (very similar to the classic NP-hardness reductions) to show that some problems cannot be approached within some factor unless P=NP or other catastrophes of the same kind.

Molecular Algorithms

In this second part of the lecture, we will overview the various approaches to the exciting and uprising field of Molecular programming where one uses algorithms to design real molecules that processes information algorithmically. We will explore in details the various theoretical models, their complexity and expressiveness, learn how to program them and survey their experimental realizations, in particular how to design algorithmically these molecules for real. Depending on the timing, we hope to be able to have you take part to a real wetlab experiments where we will have molecules executing a (simple) program for us and observe at the end of its execution the nanoscopic results (usually only about few 100nm large) thru atomic force microscope (to be confirmed).

Prerequisites

A good base in algorithms and complexity is helpful (elementary algorithms, circuits, complexity classes). Knowledge of discrete probabilities and basic information theory (Shannon entropy) helpful.

Course outline (preliminary, subject to changes)

  1. Approximation algorithms: (4 sessions)
  2. Molecular Algorithms theory and practice (4 sessions)
    • Tile self-assembly system: model, intrinsic universality, algorithms, realizations, DNA computing nanotubes
    • Boolean circuits: model, circuit, realizations
    • RNA based computing: oritatami systems, shapes, Turing universality
    • Experiments: how do we proceed

Language of the course

The lectures will be given in english unless every attendee is fluent in french.

The exam will be given in English, and can be written by the students in either language (french or english).

Sessions schedule

Every session will consist in general of ≈2h lecture followed by ≈1h exercises session.

A small exercise will be given as an homework at the end of each session to be returned for the next session.

Materials

  • Algorithmes d'approximation, V. Vazirani, Springer, 2006 (traduit de l'américain par N. Schabanel)
  • Approximation algorithms, V. Vazirani, Springer, 2001
  • Probability And Computing: Randomized Algorithms And Probabilistic Analysis, by M. Mitzenmacher and E. Upfal, Cambridge University Press, 2005
  • Computational Complexity: A Modern Approach . S. Arora and B. Barak. Cambridge University Press, 2009.
  • Communication Complexity. E. Kushilevitz and N. Nisan. Cambridge University Press, 1997.
  • Data Streams: Algorithms and Applications (Foundations and Trends in Theoretical Computer Science). S. Muthukrishnan. Now Publishers Inc, 2005.

There are no lecture notes. The lectures will be given on the board. Students will be encouraged to write down lecture notes that will be made later available to everyone. Some additional reading will be suggested during the course.

Internships

Internships are available. Contact the teachers of the lectures directly (for instance by email):

Teaching team

Suggested M2 courses

Parcours: Algorithms & Complexity
Parcours: Molecular and Biological programming & modelling

The following is a coherent list of courses on the thematic 'Molecular and Biological programming & modelling'.

Some related research articles:

Course Summary 2019-20: Molecular programming (Lectures 5-8)

Lecture 6 (2019.10.16): Universality in assembly Model (I): Theory and experiment

  • Universality in assembly Model (I) [ Slides ]
    • Simulating a Turing machine at temperature T°=2 in aTAM
    • Optimal hardcoding of a binary string at T°=2 in aTAM
    • Simulating a Turing machine at temperature T°=1 in aTAM in 3D
  • An experimental realisation of a universal computer (I) [ Slides ]
    • Single stranded tile nantubes
    • Atomic Force Microscopy (AFM)
    • Marking 0s and 1s using biotin-ptreptavidin
    • kTAM cinetic assembly model
    • Error correction using proof-reading tiles
    • DNA nanotube circuit model
  • Exercise sessions [ HW2 ]
    1. Staged self-assembly (from HW1)
    2. Exponential random variables and kTAM implementation
    3. :!: Tileset for simulating cellular automata return your solution by Wed Oct 23 before 11:45
    4. Probabilistic simulation of Turing Machine at T°=1 in 2D

Lecture 5 (2019.10.09): Introduction to DNA programming & Tile Assembly Systems [ Slides ]

  • Introduction to DNA programming & overview of the field
  • Abstract tile assembly systems:
    • Definition
    • Minimizing the assembly time
  • Exercise sessions [ HW1 | Solutions ]
    1. Guess the assembly 1
    2. Guess the assembly 2
    3. :!: A binary counter
    4. Staged self-assembly
    5. Assembly time = O(rank of the produced shape)

Course Summary 2019-20: Approximation Algorithms (Lectures 1-4)

Lecture 1: Introduction

  • Introduction to Approximation Algorithms & overview of the field
  • Examples of Combinatorial/LP-Based/Randomized Algorithms for NP-hard Problems
  • Min-Cut Algorithm of Karger
  • First Assignment PDF

Lecture 2: Chernoff Bounds

  • Christofides' TSP algorithm
  • Chernoff Bounds
  • Integer Multi-commodity Flow
  • 3-Coloring Dense Graphs
  • Second Assignment PDF

Lecture 3: Random Walk and Submodular Function

  • 2SAT
  • K-Coverage

Lecture 4: Semi-Definitie Programming

  • Max-Cut
  • Color-Coding
  • Vertex-Cover Revisited
  • Third Assignment PDF

Archives 2018-2019 (8x3h)

Course Summary 2018-19: Approximation algorithms (Lectures 1-4)

Lecture 1 Introduction to Randomised and Approximation Algorithms

  • Introduction to the Course
  • Optimization problems & Approximation Algorithms
  • Vertex Cover
  • Set Cover
  • Min Cut of Karger
  • First Assignment PDF

Lecture 2 Chernoff Bounds

  • Chernoff Bounds
  • Integer Multi-commodity Flow
  • Coloring 3-colorable Graph
  • Christofides Algorithm
  • Second Assignment PDF

Lecture 3

  • Introduction to Linear Programming
  • Facility Location
  • Third Assignment PDF

Lecture 4

  • Introduction to Semi-Definite Programming
  • Max-Cut
  • Color-Coding and Vertex-Feedback Set

Course Summary 2018-19: Molecular programming (Lectures 5-8)

Lecture 5: Introduction to DNA programming & Tile Assembly Systems [ Slides ]

  • Introduction to DNA programming & overview of the field
  • Abstract tile assembly systems:
    • Definition
    • Minimizing the assembly time
  • Exercise sessions [ HW1 ]
    1. Guess the assembly 1
    2. Guess the assembly 2
    3. :!: A binary counter
    4. Staged self-assembly
    5. Assembly time = O(rank of the produced shape)
    6. Minimum number of tiles self-assembling squares and rectangle

Lecture 6: Universality in assembly models & Introduction to Strand displacement

  • Universality in assembly models [ Slides A ]
    • aTAM simulate Turing machines at temperature T=2
    • Optimal seed encoding at T=2: Kolmogorov complexity & unpacking
    • aTAM simulate Turing machines at temperature T=1 in 3D but not 2D
    • Intrinsic universality of aTAM at temperature T=2
    • One (polygonal) tile is enough!
  • Introduction to Strand displacement [ Slides B (by Chris Thachuk) ]
  • Exercise sessions [ HW2 ]
    1. Tileset for simulating cellular automata
    2. Probabilistic simulation of Turing machine at temperature T=1 in 2D
    3. :!: Window movie lemma

Lecture 7: Strand Displacement

  • Boolean circuits using Strand displacement [ Slides (by Chris Thachuk) ]
    • Making an AND gate: rough computation of energy and entropy deltas
    • Composing gates: making a wire
    • Reading the result optically: fluorophore and quencher
    • Implementing a reaction gate
    • Implementing monotonic gates (AND and OR)
    • Handling NOT gates with dual rails
    • Moving NOT gates to the top
    • Robustness: preventing leaking:
      • Fixing molecular synthesis imperfection
      • Using double long domains (DLD)
    • Presenting Breadboard 1.0
  • Exercise sessions [ HW3 ]
    1. :!: DNA circuits
    2. Building shapes with oritatami

Lecture 8: Oritatami: A computational model for cotranscriptional molecular folding [ Slides ]

Movies & animations: [ RNA folding (slide 11) | Oritatami step 1 (slide 15) 2 (slide 21) 3 (slide 25) | Oritatami counter (slide 30) | Module G (slide 102) ]

  • Co-transcriptional RNA folding experiment
  • Oritatami
    • The model
    • A binary counter
    • Proving the binary counter
  • Complexity
    • NP-hardness of the rule design problem
    • Fixed parameter linear-time algorithm of the rule design problem
  • Efficient Turing machine simulation in oritatami
    • Skipping cyclic tag systems (SCTS)
    • Simulating SCTS with oritatami
    • Proving the correctness of the simulation
    • Oritatami programming toolbox: switchback/glider, offsets, exponential coloring & socks
    • Proving the correctness of the implementation
  • Exercise sessions
    1. HW2 exercise 1
    2. HW3 exercise 2

Archives 2017-2018 (8x3h)

Course Summary: Approximation algorithms (Lectures 1-4)

Lecture 1 Introduction to Approximation Algorithms

  • Introduction to the Course
  • Optimization problems & Approximation Algorithms
  • Set Cover (two LP-based approximation algorithms)
  • Min Cut of Karger
  • First Assignment PDF

Lecture 2 Chernoff Bound

  • Chernoff Bound
  • Congestion Minimization
  • 3-Coloring in Dense Graph
  • Travelling Salesman Problem (Christofidis algorithm)
  • Bin-Packing
  • Second Assignment PDF

Lecture 3 Max Cut

  • An algorithm of Fernandez de la Vega for max cut in dense graph (an exposé of Nicholas Schabanel is here PDF)
  • Third Assignment PDF

Lecture 4 Semi-Definite Programming

  • Goemans-Williamson Max-Cut
  • Integrality Gap

Course Summary: Molecular programming (Lectures 5-8)

Lecture 5: Introduction to molecular programming & Tile assembly systems (Oct 18) Video

  • Introduction to the course [0:00:00]
  • A little history of the field [0:09:14]
  • Tile assembly systems [0:35:41]
  • A binary counter [0:51:50]
  • Minimizing the assembly time [1:10:01]
  • Exercises session [1:51:44] HW1 PDF
    1. Guess the assembly 1
    2. Guess the assembly 2
    3. A counter :!:
    4. Staged assembly of a candelabrum
    5. Expected assembly time & rank of a construction
    6. Minimum number of tiles for the families of squares and rectangles

Lecture 6: Universality in tile assembly systems (Oct 25) Video

  • Simulating Turing Machines at T°=2 [0:00:00]
  • Kolmogorov Complexity [0:29:02]
  • Lower Bounding the minimal number of tiles to hardcode the input seed with Kolmogorov complexity [0:54:16]
  • Optimal number of tiles for hardcoding the seed [1:06:43]
  • Exercises session [1:42:54] HW2 PDF
    1. HW1 exercise 5: Assembly time = O(rank) w.h.p.

Lecture 7: Universality in Tile Assembly and Oritatami Systems (Nov 8) Video

  • Tile sets self-assembling an arbitrary shape [0:00:00]
  • Turing-Universal tile set in 3D at T°1 [0:29:05]
  • Intrinsically universal tile set in 2D at T°2 [0:49:06]
  • Magic Powder [1:11:56]
  • Oritatami: A model for co-transcriptional folding [1:15:19]
  • Exercise session:
    1. Designing DNA origami using cadnano [2:19:08]

Lecture 8: Some experimental achievements in DNA programing (Nov 15) Video

  • The equipment: Pipetters, thermocycler & AFM microscopy [0:00:00]
  • A tour of built DNA nano-structures [0:39:17]
  • DNA single stranded tiles [1:00:41]
  • Stacking interactions [1:01:29]
  • Strand displacement [1:03:55]
  • Exercise session:
    1. cadnano is back [1:11:49]
    2. HW1-6: Tile set of minimimum size for Squares and Rectangles [1:15:28]
    3. HW2-1: Discrete slope [1:31:01]
    4. HW2-2: Window movie lemma [1:42:40]

Archives 2016-2017 (8 x 3h)

Lecture 1 [Wed 14/9/2016 16:15-19:15] Introduction to Approximation Algorithms Video

  • Introduction to the Course
  • Optimization problems & Approximation Algorithms
  • About Hardness of approximation
  • Approximation Algorithms for Metric TSP
  • Exercices Session 1 PDF
    1. 3/2-Approximation for Metric TSP
    2. Cost-based approximation for Vertex Cover :!:
    3. Maximum Arc-Disjoint Paths (1)

Lecture 2 [Wed 21/9/2016 16:15-19:15] Mathematical Programming 1: Linear programming Video

  • Mathematical Programming [0:00:00]
  • Introduction to Linear Programming [0:01:45]
  • First Example: Max-CUT as an Integer Program [0:07:04]
  • LP Relaxation for Max-CUT & Randomized Rounding [0:38:16]
  • Max-SAT: Random Assignment [1:09:26]
  • Max-SAT: Randomized Rounding [1:24:23]
  • Max-SAT: Combining both Algorithms into One [2:12:33]
  • Exercises Session 2 PDF
    • Maximum Arc-Disjoint Paths (2)
    1. Dumb Algorithm for Max-SAT
    2. Metric k-Center :!:
    3. SDP Approximation for Weighted Max-2SAT

Lecture 3 [Wed 28/9/2016 16:15-19:15] Mathematical Programming 2: Semi-definite / Vector programming Video

  • 0. Introduction [0:00:00]
  • 1. A quadratic program for Max-CUT [0:02:09]
  • 2. Relaxing a Quadratic Program as a Vector Program [0:10:17]
  • 3. Vector Programs = Semi-Definite Programs [0:16:14]
  • 4. VP is indeed a relaxation of integer QP [0:27:28]
  • 5. Rounding VP: the Random Hyperplane Technic [0:38:43]
  • 6. Analysis of the Random Hyperplane Algorithm [1:10:09]
  • Exercise Session 3: PDF
    • Exercise HW2-1: A Dumb Algorithm for Max-SAT [1:31:47]
    • Exercise HW2-3: SDP-Approximation for Max-2SAT [1:39:12]
    1. Randomized Rounding for Set Cover :!:

Lecture 4 [Wed 5/10/2016 16:15-19:15] Polynomial Time Approximation Schemes Video

  • 0. (F)PT(R)AS: (Fully) Polynomial-Time (Randomized) Approximation Schemes [0:00:00]
  • 1. A FPTAS for the Knapsack Problem [0:10:31]
  • 2. A FPTRAS for Max-Cut in α-Dense Graphs [1:05:27]
  • Exercise Session 4: PDF
    1. A PTAS for the Minimum Cost Overflow Problem :!:

Lecture 5 [Wed 26/10/2016 16:15-19:15] Nature Programming: Abstract Tile Assembly Model Slides

  • 0. Introduction to Nature programming & DNA assembly
  • 1. Abstract Tile Assembly Model
  • 2. A binary counter
  • 3. Minimizing the assembly time for squares & cubes
  • Exercise Session 5: PDF
    1. Guess the result of the algorithmic Self-Assembly (I)
    2. Guess the result of the algorithmic Self-Assembly (II)
    3. :!: Counter at T°=2
    4. Staged assembly scheme at temperature T°=1
    5. Concentrations, Rank and Assembly time
    6. Minimum number of tile types for squares and rectangles

Lecture 6 [Wed 2/11/2016 16:15-19:15] Nature Programming: Universality in Tile Assembly Systems Video

  • 0. HW4: NP-completeness & Optimization Problems [0:00:00]
  • 1. Turing Universality in tile assembly systems [0:05:43]
  • 2. Turing universality at T°=2 [0:12:31]
  • 3. Turing universality at T°=1 [0:36:19]
  • 4. Minimizing the number of tiles to build a shape [1:19:04]
  • Exercise Session 6: [2:31:39]
    1. HW5(2): Assembly time, rank & concentrations

Lecture 7 [Wed 9/11/2016 16:15-19:15] Nature programming: Intrinsic Universality & Other Models including Oritatami Video

  • 0. Theory vs Practice [0:00:00]
  • 1. Intrinsic Universality of Tile Assembly Systems at T°=2 [0:04:59]
  • 2. One (Polygonal) Tile is Enough! [0:39:20]
  • 3. Other Models: Bio-Logical Circuits [0:43:00]
  • 4. Nubots: a Model for Molecular Reconfiguration [0:49:43]
  • 5. About Experiments: Nanotubes that Compute [0:54:07]
  • 6. Oritatatami: one Molecule that computes co-transcriptionally [0:58:26]
    • 6.1 Experiment: Synthetic RNA Co-Transcriptional Folding-based Meshes [0:58:54]
    • 6.2 Oritatami: A Model for Co-Transcriptional Folding [1:11:58]
    • 6.3 Oritatami: How to Compute? [1:18:02]
    • 6.4 Oritatami: Rule Design is NP-hard but Fixed Parameter Tractable [1:31:55]
    • 6.5 Oritatami Systems simulate efficiently Turing machines [1:41:20]
    • 6.6 Oritatami: How to Prove the Correctness? [2:04:36]
    • 6.7 Oritatami: Conclusion [2:28:48]
  • No Exercise Session

Lecture 8 (last) [Wed 9/11/2016 16:15-19:15] Nature programming: Experiments

  • 1. Description of the recent experiment of Damien Woods et al on building nanotubes implementing 6-bit circuits computation
  • 2. Introduction to CADNano, a DNA Origami Designer
  • 3. Introduction to NUPack, a DNA/RNA strand(s) energy/partition function calculator

Archives 2014-2015 (24h)

Lecture 1 [18/9/2014] NP-completeness, Hardness of approximation & Approximation algorithms Video 1 2 3

  • Introduction to approximation algorithms
  • NP-completeness, PCP theorem & hardness of approximation
  • Definitions: Optimization problem & Approximation
  • Hardness of approximation for non-metric TSP
  • A 2-approximation for metric TSP
  • A 3/2-approximation for metric TSP
  • Exercise session 1 PDF
    1. Max-Cut: randomized 2-approximation and greedy approximation by the conditional expectation method
    2. Coloring 3-colorable graphs
    3. Cost-based 2-approximation for Vertex Cover

Lecture 2 [25/9/2014] Introduction to Integer Programming, Linear Relaxation and Rounding Video 1 2 3

  • Max-SAT
  • Random solution to Max-SAT
  • A (1-1/e)-approximation based on a randomized rounding of a solution to a linear program for Max-SAT
  • Mixing both algorithms yield a 3/4-approximation
  • Exercise session 2 PDF
    1. Dumb algorithm for Max-SAT
    2. Simple rounding f-approximation for Set Cover
    3. Randomized rounding (ln(n)+O(1))-approximation for Vertex Cover
    4. 2- and 3-approximations for Minimum Weighted Sum of Completion Time Scheduling with dependencies and with and without release dates

Lecture 3 [16/10/2014] PTAS: Polynomial Time Approximation Schemes Video 1 2 3

  • Euclidean Traveling Salesman problem
  • Exercise session 3 PDF
    1. A Fully Polynomial Time Approximation Scheme (FPTAS) for the Knapsack Problem
    2. A Constant Time Approximation Scheme (CTAS) for the size of a maximal matching in a constant degree graph

Lecture 4 [23/10/2014] Introduction to semi-definite programming Video 1 2 3

  • From quadratic formulation to vector program
  • Rounding with cutting hyperplanes for Max-Cut
  • A O(n1/3)-approximation for coloring 3-colorable graphs
  • Exercise session 4 PDF
    1. How to draw unit vector uniformly at random
    2. A O(n1/4)-approximation for coloring 3-colorable graphs

Lecture 5 [30/10/2014] Introduction to Lasserre's hierarchy (1/2) Video 1 2 3

  • Important properties of semi-definite matrices
  • Equivalence of vector programs and semi-definite programming
  • Definition of Lasserre's hierarchy
  • First properties of the solutions
  • Decomposition: lemma and theorem
  • No exercise session today

Lecture 6 [6/11/2014] Lasserre's hierarchy (2/2) Video 1 2 3

  • Decomposition theorem
  • First examples of applications
  • Exercise session 5 PDF
    1. Lasserre support lemma
    2. Scheduling with precedence constraints: application of Lasserre decomposition
    3. A (1-ε)ln(m)-approximation for Set Cover with Laserre hierarchy

Lecture 7 [13/11/2014] Natural algorithms: the Small-World phenomenon Video 1 2 3

  • Sociological context: Milgram's experiment
  • First Small World models
  • Kleinberg's augmented grid model
  • Case α < 2: Long-range links are too messy
  • Case α > 2: Long-range links are too short
  • Case α = 2: The greedy algorithm
  • Small-World emergence: the Move-and-Forget model
  • No exercise session today

Lecture 8 (last) [20/11/2014] Algorithmic self-assembly & Non-clairvoyant scheduling Video 1 2 3

  • Simulation of routing algorithms in Kleinberg's small world model
  • Algorithmic self-assembly PDF
    • Winfree's model and Rothermund's realizations
    • Cube construction in real-time (order, signals and synchronization)
  • Non-clairvoyant scheduling PDF
    • Introduction to online algorithms
    • Jeff Edmonds's non-clairvoyant model
    • Competitive hardness of approximation
    • Competitive analysis with resource augmentation: LAPSβ algorithm
    • Extension to precedence constraints
  • No exercise session today

Archives 2012-2013 (12h)

Lecture 1: Wed Sep 26, 2012 - 12:45-15:45 Vidéo
  1. Introduction to Approximation Algorithms
    • P vs NP, a refinement of NP-completeness: Inapproximability results
    • Definitions of Optimization problems and Approximation algorithms
    • General principles for obtaining approximation algorithms
  2. An exemplary example: the Travelling Salesman Problem
    • Definition of TSP
    • Inapproximability of general TSP unless P = NP
    • A first 2-approximation algorithm (MST-based)
    • Cristofides algorithm: a 3/2-approximation algorithm
    • Family of tight instances for both algorithms
TD1 PDF
  1. Random Cut for Max-Cut and derandomization by the conditional expectation method
  2. 2-approximation for Metric Steiner Tree and isofactor reduction from general to metric
Lecture 2: Wed Oct 3, 2012 - 12:45-15:45 Vidéo
  1. Linear Programming
    • Introduction, LP Relaxation, First rounding (Vertex-Cover)
    • Duality and Complementary Slackness Conditions
    • Application: primal-dual algorithm for Vertex-Cover & Maximum/-al Matching
    • (Note for next year: primal dual algorithm for Set-Cover would have been a better choice)
TD2 PDF
  1. Basic duality manipulation
  2. A randomized LP-rounding algorithm for Set-Cover
Lecture 3: Wed Oct 10, 2012 - 12:45-15:45 - A Polynomial Time Randomized Approximation Scheme (PTRAS) for dense Max-Cut Vidéo
  1. Definition of PTAS, PTRAS, example of dependence in ε
  2. Dense Max-Cut
    • definition
    • the partition of the cut covers a constant fraction of the nodes
  3. A first algorithm
    • A non-adaptative randomized sampling based algorithm
    • An example on why it does not work
  4. The PTRAS
    • Description of the algorithm
    • Exhaustive guessing
    • Hybridation
    • Algorithmic analysis
    • Probabilistic analysis
    • Final theorem
TD3 PDF
  1. A Fixed-Parameter Tractable (FPT) algorithm for k disjoint triangles
  2. A Constant Time Approximation Scheme (CTAS) for the size of a maximal matching
Lecture 4: Wed Nov 7, 2012 - 12:45-15:45 - Hardness of approximation: The PCP theorem by GAP amplification Vidéo Slides
  1. A little bit of history
  2. Gap problems and Hardness of approximation
  3. The CSP: Graph Constraints Satisfaction Problem
  4. Overview of the Gap amplication process 2.a) definition
  5. A key tool: Expander graphs I
  6. Step 1: Degree uniformization
  7. Step 2: Expanderization
  8. Expander graphs II: spectral theory and random walks
  9. Step 3: Gap amplification
  10. Step 4 (last): Alphabet reduction
  11. Gap-preserving reductions
TD4: PDF
  1. Gap-preserving reductions for Vertex-Cover and Steiner Tree
  2. Random walks on expanders
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA