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

## Approximation Algorithms & Molecular Algorithms (2020/2021, 8x3h, 3 ECTS) Wednesdays 16:15-19:15 Room SG1014

To join the EXAM online please log to:

https://webconference2.ens-lyon.fr/b/nic-m0h-95l-h0u

Dates for the lectures:

Molecular algorithms

• Lecture 1: Wed 16 SEP Molecular algorithms 1/4
• Lecture 2: Wed 23 SEP Molecular algorithms 2/4
• Lecture 3: Wed 30 SEP Molecular algorithms 3/4
• Lecture 4: Wed 7 OCT Molecular algorithms 4/4

For the second homework, in the second generalisation of the set cover, the condition that M(s,e) ≤ r(e), for all elements e in the universe, should be included.

Approximation & Randomized Algorithms

• Lecture 5: Wed 14 OCT Approximation & Randomized Algorithms 1/4
• Lecture 6: Wed 21 OCT Approximation & Randomized Algorithms 2/4
• Lecture 7: Wed 28 OCT Approximation & Randomized Algorithms 3/4
• Lecture 8: Wed 4 NOV Approximation & Randomized Algorithms 4/4

Final exam

• Final Exam: ONLINE on 2 DEC 16:15-19:15

Teachers:

Lectures will take place every Wednesdays 16:15-19:15 in SG1014 starting on 16/9.

Internship proposals:

### 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, uncomputability
• 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):

### Suggested M2 courses

##### 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:

• Experiments:
• Abstract tile sel-assembly:
• DNA strand displacement systems:
• Oritatami:

### Course Summary 2020-21: Molecular programming (Lectures 1-4)

Lecture 1 (2019.09.16): 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. Assembly time = O(rank of the produced shape)
4. Staged self-assembly
5. Making turns

Lecture 2 (2019.09.23): 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 realization of a universal computer [ Slides ]
• Single stranded tile nanotubes
• Atomic Force Microscopy (AFM)
• Marking 0s and 1s using biotin-streptavidin
• kTAM kinetic assembly model
• Error correction using proof-reading tiles
• DNA nanotube circuit model
• Examples of nanotube circuits
• A 6-bits Turing universal nanotube circuit
• Minimizing errors with proof-reading tiles
• Counting the glues
• Sequence design
• Experiment results
• Exercise sessions [ HW2 ]
1. Exponential random variables and kTAM implementation
2. Tileset for simulating cellular automata
3. Probabilistic simulation of Turing Machine at T°=1 in 2D

Lecture 3 (2020.09.30): Universality in assembly Model (II): Intrinsic universality and Oritatami

• Intrinsic Universality in tile assembly model [ Slides ]
• Intrinsic universality at T°2
• The supercell, the probes
• One (polygonal) tile is enough
• Oritami: a computational model for co-transcriptional folding [ Slides ]
• RNA co-transcriptional folding
• Oritatami model
• A first example: a binary counter
• Proving its correctness
• Rule design is NP-hard but FP-tractable
• Oritatami is Turing complete
• Simple intrinsic Oritatami simulation of cellular automata
• Exercise sessions [ HW3 ]
1. Building shapes with Oritatami

Lecture 4 (2020.10.07, Last): Strand displacement boolean circuits [ Slides ]

• DNA Strand displacement mechanism
• Some basic of thermodynamics [ Slides ]
• Reading with fluophore
• Dealing with leaks
• Double long domain [ Slides ]
• Exercise sessions [ HW4 ]
1. DNA circuits
2. Strand displacement: DNA gate (1 page maximum)
3. aTAM: Scale the wall (1 page maximum)

### Course Summary 2020-21: Approximation Algorithms (Lectures 5-8)

Lecture 5 (2020.10.14): Introduction to Approximation Algorithms

• Overview of the field
• Greedy algorithm for Set Cover
• Laying algorithm for Weighted Vertex Cover
• Approximation scheme for Knapsack
• First Assignment PDF

Lecture 6 (2020.10.21): Introduction to Linear Program

• Christofides' TSP Algorithm
• Introduction to Linear Program and Duality Theory
• Two Rounding Algorithm for Set Cover
• Analysis of Greedy for Set Cover Using Dual-Fitting
• Second Assignment PDF

Lecture 7 (2020.10.28): Introduction to Large Concentration Inequality

• Third Assignment PDF

## Archives 2019-2020

### 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

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

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 ]
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)

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 nanotubes
• Atomic Force Microscopy (AFM)
• Marking 0s and 1s using biotin-streptavidin
• kTAM kinetic 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
4. Probabilistic simulation of Turing Machine at T°=1 in 2D

Lecture 7 (2019.10.23): Universality in assembly Model (II): experiment, intrinsic universality and Oritatami

• An experimental realisation of a universal computer (II) [ Slides (again) ]
• Examples of nanotube circuits
• A 6-bits Turing universal nanotube circuit
• Minimizing errors with proof-reading tiles
• Counting the glues
• Sequence design
• Experiment results
• Intrinsic Universality in tile assembly model [ Slides ]
• Intrinsic universality at T°2
• The supercell, the probes
• One (polygonal) tile is enough
• Oritami: a computational model for co-transcriptional folding [ Slides ]
• RNA co-transcriptional folding
• Oritatami model
• A first example: a binary counter
• Proving its correctness
• Rule design is NP-hard but FP-tractable
• Oritatami is Turing complete
• Simple intrinsic Oritatami simulation of cellular automata
• Exercise sessions [ HW3 ]
1. Window movie Lemma

Lecture 8 (2019.10.30 - Last): Oritatami Shapes & Strand displacement boolean circuits

• Oritatami: building shapes [ Slides ]
• The problem
• Some impossible shapes
• Scaling schemes
• Algorithm for scales Bn≥3
• Filling a pseudo-hexagon
• Bead type set for tight Oritatami systems
• Algorithm for scales An≥5
• Algorithm for scale A4
• Algorithm for scale A3
• Time anomalies and how to fix them
• Strand displacement boolean circuits [ Slides ]
• DNA Strand displacement mechanism
• Some basic of thermodynamics [ Slides ]
• Reading with fluophore
• Dealing with leaks
• Double long domain [ Slides ]

## 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 ]

• 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éoSlides
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