Overall information...
- Aims
- Structuring NP(NPO). How to exploit this structural knowledge in order to deal with effective resolution of discrete optimization problems.
- Schedule
-
- direct to next session
- regular sessions: each Wednesday, 12h00-13h30, B311
- additionnal sessions: Friday, 10h15-12h00, C214 (check the schedule!)
- Who is concerned?
- Any member of the OCAD team, any member of the lab, any soul interested in our topics/wanting to propose some enlightening perspective... everybody who wants to take part!
- You want to talk/join?
- Just send an e-mail to propose some subject/to get more information.
... more information.
Main research areas that are concerned
- Combinatorial optimization
- Approximation algorithms for combinatorial optimization problems
- [Random] Graph theory
- Algorithm analysis
Specified topics
- Differential approximation classes
- Polynomial approximation within effective resolution of combinatorial problems
- Smoothed analysis (of complexity, combinatorial structures, approximation level)
Ongoing work
- Differential aproximation of 2-CSP problems (2-XOR, 2CCSP, 2-SAT)? Combining approachs: reduction tools, generating function, algebraic approach, neighborhoods.
2006-2008 sessions
-
...
- (Friday, 10h00) 28/11/08 - Hichem Keniche - Cyclic words and necklaces: enumeration, generating functions and random generation.
- 26/10/08 (Friday, 10h00) - Sophie Toulouse - Complexity of the Multiple stack TSP problem.
- 12/10/08 (Friday, 10h00) - Broadcasting in Knesser graphs.
- 06/06/08 (Friday, 14h00) - Sophie Toulouse - QBF2 and inductive logic programming problem.
- 23/05/08 (Friday, 14h00) - Mario Valencia Pabon - Fractionnal coloring.
- 21/05/08 (Wednesday, 12h30) - Mario Valencia Pabon - Fractionnal coloring.
- 16/05/08 (Friday, 14h) - Sophie Toulouse - QBF2 and inductive logic programming problem.
- 09/05/08 (Friday, 14h) - Sophie Toulouse - Links between average complexity and approximation.
- 30/04/08 - Sophie Toulouse - Links between average complexity and approximation.
- 21/03/08 (10h00, A103) - Broadcasting in Knesser graphs.
- 19/03/08 - Mario Valencia Pabon - Properies of Knesser graphs.
- 07/03/08 (14h) - Cyril Banderier - Airy ≠ Airy: a tale of two limit laws.
- 05/03/08 - Cyril Banderier - Airy ≠ Airy: a tale of two limit laws.
- 27/02/08? - Pawel Hitczenko Crash course on martingales.
- 21/02/08 (course #2, 14:00, C214) - Mario Valencia Pabon - Graphs.
- 20/02/08 - Andry Rasoanaivo Minimum broadcast graphs.
- 15/02/08 (course #1, 10:15, C214) - Mario Valencia Pabon - Graphs.
- 13/02/08 (2 sessions) - Vlady Ravelomanana - On the threshold of random 2-CSP formulas.
Erik Alphonse, Aomar Osmani - Threshold phenomena in machine learning.
- Vlady Ravelomanana - On the satisfiability of random 2-XOR-SAT formulas
- Gérard Duchamp - Automata with multiplicity
- Sophie Toulouse - Differential aproximation of 2-CSP problems? Another view of neighborhoods.
- Jean-François Culus - Differential aproximation of 2-CSP problems? Neighborhoods.
- Paulin Jacobe De Naurois Connectivity, acyclicity and NL
- (course #4) - Mario Valencia Pabon - Initiation to group theory
- Gérard Duchamp - Differential aproximation of 2-CSP problems? Algebraic approach.
- (course #3) - Jean-François Culus & Mario Valencia Pabon - Initiation to group theory
- Sophie Toulouse - Differential aproximation of 2-CSP problems (2-XOR, 2CCSP, 2-SAT)? State of the art.
- (course #2) - Mario Valencia Pabon - Initiation to group theory.
- (course #1) - Mario Valencia Pabon - Initiation to group theory.
- Paulin Jacobe De Naurois - Approximating decision problems.
- Andry Rasoanaivo - Models underlying the minimum broadcast problem.
- (course) Cyril Banderier - About the analyzis of combinatorial structures.
- Sophie Toulouse - PCP theorem and inapproximability.
- Vlady Ravelomanana - Tools for average-case approximation: independent set in G(n,1/2).
- Carlos Martinhon - Alternating paths in 2-edge colored graphs.
- Complexity analysis of FPTAS' algorithms for the constrained shortest path problem.
- Laurent Alfandari - Greedy approximation of covering problems.
- Mario Valencia Pabon - Approximation of the Min-max degree Maximum-weight spanning tree.
- Sophie Toulouse - Standard vs. differential approximation.
- Oliver Laval - Constrained Shortest Path problem: exact and approximate resolution.
Bibliography & links
(absolutely incomplete!!!)
- Spanning trees
-
M. Fürer, B. Raghavachari,
Approximating the minimum degree spanning tree to within one from the optimal degree,
Proc. SODA 1992
- IS/Clique in random graphs
-
D. W. Matula,
The largest clique size in a random graph,
Technical report, Southern Methodist University,Dallas 1976
- Computational complexity
-
E. Fischer, F Magniez, M de Rougemont,
Approximate satisfiability and equivalence,
Approximate satisfiability and equivalence. In Proceedings of 21st IEEE Symposium on Logic in Computer Science, pages 421-430, 2006
- Differential approximation
-
G. Ausiello, C. Bazgan, M. Demange, V. Th. Paschos,
Completeness in differential approximation classes,
Proc. MFCS'03, LNCS, Springer-Verlag.
-
J. Monnot, V. Th. Paschos, S. Toulouse,
Approximation polynomiale des problèmes NP-difficiles - Optima locaux et rapport différentiel,
Hermes Science 2003
-
B. Escoffier,
Approximation polynomiale : aspects structurels et opérationnels, thèse de doctorat, Paris 2005
-
Average-case approximation
-
Miscellaneous
