homepage Vincent JOST Vincent page perso CNRS LIX Polytechnique

Vincent JOST

	CR-CNRS at LIX Laboratory

Adress :	Ecole polytechnique
	Laboratoire d'informatique (LIX)
	91128 Palaiseau Cedex
	France

Phone :	(+33) 1 69 33 40 52
Fax :	(+33) 1 69 33 30 14
email :	vincent.jost(at)lix.polytechnique.fr

Research interests: discrete optimization

I try to understand, develop and apply the following paradigms

Polyhedral combinatorics (TDI and IRP systems, perfect graphs, submodular functions...)

Structural graph theory (classes, minors, decompositions, representations...)

Game theory (cooperation and cores, coherence...)

Convex analysis (Lagrangian relaxation, semi-definite programming...)

Algorithmic complexity (NP-completeness, efficient algorithms...)

in order to make relevant observations in the following fields

Partition problems (bounded coloring, list-coloring, max-coloring, online coloring...)

Scheduling (just-in-time, batch and parallel machines...)

Graph connectivity (TSP and Hamiltonicity, scattering sets and toughness, simple max cut...)

Operations research (production planning, transport planning...)

Please contact me directly if you need any updated version.

Published or accepted papers	[2008]	Denis Cornaz, Vincent Jost A one-to-one correspondence between colorings and stable sets Operation Research Letters. 36(6): 673-676 (2008)
		Gerd Finke, Vincent Jost, Maurice Queyranne, András Sebö Batch Processing with Interval graph compatibilities between tasks Discrete Applied Mathematics. 156(5): 556-568 (2008)
		Nadia Brauner, Vincent Jost Small deviations, JIT sequencing and symmetric case of Fraenkel's conjecture Discrete Mathematics. 308(11): 2319-2324 (2008)
	[2007]	Dion Gijswijt, Vincent Jost, Maurice Queyranne Clique partitioning of interval graphs with submodular costs on the cliques RAIRO-OR. 41(3): 275-287 (2007) , available on EGRES Tech Report TR-2006-14
		Vincent Jost, Benjamin Lévêque, Frédéric Maffray Precoloring extension of co-Meyniel graphs Graphs and Combinatorics. 23: 291-301 (2007)
		Vassilissa Lebacque, Vincent Jost, Nadia Brauner Simultaneous optimization of classical objectives in JIT scheduling European Journal of Operations Research. 182(1): 29-39 (2007)

PhD thesis		Chromatic scheduling: polyhedra, complexity and classification. (2006) Résumé + notes pour suivre les Slides de soutenance (french.pdf) Texte complet (french.pdf last version: 1/12/2006)

Teachings

Courses given (268h)

196h

Assistant in computer sciences at Université Joseph Fourier (2002 - 2005)
"Moniteur" au CIES de Grenoble

Algorithms and C (INF111)	172h C,TD,TP	Imperative programming and langage C Top-down analysis and drawing in Logo Unix system
Formal tools	24h TD	Basics of logic and set theory Introduction to relational algebra

72h

Assistant in mathematics at Université de Montréal (1999 - 2000)

Linear Algebra	24h TD	Linear systems, Gaussian elimination Matrix inversion, Diagonalisation
Real Analysis	24h TD	Continuity and differentiability
Analytic Calculus	24h TD	Derivatives, integrals Optimisation and extremal problems

Students supervision

Master thesis of Samir Aider co-supervised with Gerd Finke (2005)

Master thesis of Vassilissa Lebacque co-supervised with Nadia Brauner (2004)

Curriculum Vitae CV(french).pdf

2008 -	Researcher (permanent position) at LIX - CNRS
2007	Post-doc (6 months) at INRIA Rhône-Alpes in group BIPOP with Claude Lemaréchal
2006 - 2007	Post-doc (8 months) at EPFL in groups ROSO (Thomas Liebling) and TRANSP-OR (Michel Bierlaire)
2005 - 2006	Doctoral mobility (9 months) at EGRES-ELTE, Budapest supervised by András Frank
2002 - 2006	PhD at Université Joseph Fourier supervised by András Sebö and Nadia Brauner Laboratory Leibniz, groups Graphes et Optimisation Combinatoire and Recherche Opérationnelle
2001 - 2002	Master Mathématiques, Informatique Spécialité Recherche Opérationnelle et Combinatoire (mention très bien).
2000 - 2002	Engineer degree from ENSIMAG with honors (mention bien).