Menu

Marc Demange
Professor, Information Systems, Decision Sciences and Statistics (IDS) Department
Director, ESSEC Business School Romania Foundation, Bucharest

Photo de Marc Demange
General Information Research Areas Publications Other Activities
Education

HDR (Computer Science), Paris-Dauphine University

PHD (Doctoral Thesis), Computer Science, Paris I University

Research Master (DEA) Modeling and Mathematical Methods for Economy, Paris I University-Ecole Polytechnique

Agrégation (French Diploma for Teaching), Mathematics (Probability)

Ecole Normale Supérieure de Cachan (French school for teaching and research career), Mathematics
Research Areas
Areas
Operations research, Combinatorial optimization, Modeling, Approximation of hard problems, On-line algorithms, Combinatorial inverse optimization


Academic Publications
Articles
  "On some applications of the selective graph coloring problem" (M. Demange, T. Ekim, B. Ries, C. Tanasescu), European Journal of Operational Research, Issue 
  "Hardness and approximation of minimum maximal matchings" (M. Demange, T. Ekim, C. Tanasescu), international journal of computer mathematics, Jan 2014, Vol. available online, Issue  , p.  ‑  (graph algorithms; minimum maximal matching; edge dominating set; regular graphs; complexity and approximation)
  "Efficient Recognition of Equimatchable Graphs" (M. Demange, T. Ekim), Information Processing Letters, Jan 2014, Vol. 114, Issue 1-2, p. 66‑71
  "A note on the NP-hardness of two matching problems in induced subgrids" (M. Demange, T. Ekim), Discrete Mathematics and Theoretical Computer Science, Aug 2013, Vol. 15, Issue 2, p. 233‑242
  "On the complexity of the selective graph coloring problem in some special classes of graphs" (M. Demange, J. Monnot, P. Pop, B. Ries), Theoretical Computer Science, Issue   (A preliminary version appeared in proceeding of ISCO 2012, LNCS 7422, pp 320-331, Springer (2012))
  "New Results on Maximum Induced Matchings in Bipartite Graphs and Beyond" (M. Demange, K. Dabrowski, V. Lozin), Theoretical Computer Science, Mar 2013, Vol. 478, Issue  , p. 33‑40
  "On some coloring problems in grids" (M. Demange, D. De Werra), Theoretical Computer Science, Feb 2013, Vol. 472, p. 9‑27
  "On online track assignment problem" (M. Demange, G. Di Stefano, B. Leroy‑Beaulieu), Discrete Applied Mathematics, May 2012, Vol. 160, Issue 7-8, p. 1072 ‑ 1093 ((a preliminary version appeared in proceeding of "IV Latin-American Algorithms, Graphs and Optimization Symposium", Electronic Notes in Discrete Mathematics 30, 213-218, 2008))
  "Some Inverse Traveling Salesman Problems" (M. Demange, Y. Chung), 4OR - A Quarterly Journal of Operations Research, Jan 2012, Vol. 10, Issue 2, p. 193‑209 ((A prelimination version appeared in proceedings of "IV Latin-American Algorithms, Graphs and Optimization Symposium", Electronic Notes in Discrete Mathematics 30, 9-14, 2008))
  "On-line computation and maximum-weighted hereditary subgrah problems" (M. Demange, B. Kouakou, E. Soutif), yugoslav Journal of Operations Research, Jun 2011, Vol. 21, Issue 1, p. 11‑28 (A preliminary extended abstract appeared in the Proceeding of ISAAC 2005, LNCS 3827, pp. 433-442, 2005)
  "Weighted coloring on planar, bipartite and split graphs: complexity and approximation " (M. Demange, B. Escoffier, J. Monnot, V. Paschos, D. Dominique), Discrete Applied Mathematics, Feb 2009, Vol. 157, Issue 4, p. 819‑832
  "A tutorial on the use of graph coloring for some problems in robotics" (M. Demange, T. Ekim, D. De Werra), European Journal of Operational Research, Jan 2009, Vol.  192, Issue 1, p.  41‑ 55
  "The 0-1 inverse maximum stable set problem" (M. Demange, Y. Chung), Discrete Applied Mathematics, Jul 2008, Vol.  156, Issue  13, p. 2516‑2516 (A preliminary version appeared in the proceedings of Francoro conference, 2007, PUG, pp. 47-55)
  "Time Slot Scheduling of Compatible Jobs" (M. Demange, D. De Werra, J. Monnot, V. Paschos), Journal of scheduling, Apr 2007, Vol. 10, Issue 2, p. 111‑ 127
  "On the approximation of Min Split-coloring and Min Cocoloring" (M. Demange, D. De Werra, T. Ekim), Journal of Graph Algorithms and Applications, Dec 2006, Vol. 10, Issue 2, p. 297‑315
  "(p,k)-coloring Problems in Line-graphs" (M. Demange, T. Ekim, D. De Werra), Theoretical Computer Science, Dec 2005, Vol. 349, Issue 3, p. 462‑474
  "Completeness in Differential Approximation Classes" (M. Demange, G. Ausiello, C. Bazgan, V. Paschos), International Journal of Foundations of Computer Science , Dec 2005, Vol. 16, Issue 6, p. 179‑188 (prelim. version in Proc. of MFCS 2003, LNCS 2747)
  "Partitioning Cographs into Cliques and Stable Sets" (M. Demange, T. Ekim, D. De Werra), Discrete Optimization, Jun 2005, Vol. 2, Issue 2, p. 145‑153
  "On-line Maximum Order Induced Hereditary Subgraphs Problems" (M. Demange, X. Paradon, V. Paschos), International Transactions in Operational Research, Mar 2005, Vol. 12, Issue 2, p. 185‑201
  "On-line Vertex Covering" (M. Demange, V. Paschos), Theoretical Computer Science, Feb 2005, Vol. 332, Issue 1, p. 83‑108
  "A Hypocoloring Model for Batch Scheduling" (M. Demange, D. De Werra, J. Monnot, V. Paschos), Discrete Applied Mathematics, Feb 2005, Vol. 146, Issue 1, p. 3‑26
  "Polynomial Approximation Algorithms with Performance Guarantees: An Introduction-by-example" (M. Demange, V. Paschos), European Journal of Operational Research, Jan 2005, Vol. 165, p. 555‑568
  "Improved Approximations for Weighted and Unweighted Graph Models" (M. Demange, V. Paschos), Theory of Computing Systems, Jan 2005, Vol. 38, Issue 6, p. 102‑113
  "Algorithmes d'approximation : un petit tour en compagnie d'un voyageur de commerce" (M. Demange), La Gazette des Mathématiciens, Oct 2004, Issue 102, p. 51‑90
  "Algorithms for the On-line Quota Traveling Salesman Problem" (M. Demange, G. Ausiello, L. Laura, V. Paschos), Information Processing Letters, Jan 2004, Vol. 92, Issue 2, p. 89‑94
  "Reducing Off-line to On-line: An Example and its Applications" (M. Demange), Yugoslav Journal of Operations Research, Jan 2003, Vol. 13, Issue 1, p. 3‑24
  "Differential Approximation Results for the Steiner Tree Problem" (J. Monnot, V. Paschos), Applied Mathematics Letters, Jan 2003, Issue 16, p. 733‑739
  "Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances" (M. Demange, V. Paschos), RAIRO Operations Research, Jan 2002, Vol. 36, Issue 4, p. 311‑350
  "Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation" (V. Paschos), RAIRO Operations Research, Jan 2002, Vol. 36, Issue 3, p. 237‑277
  "Maximizing the number of unused bins" (M. Demange, J. Monnot, V. Paschos), Foundations of Computing and Decision Sciences, Jan 2001, Vol. 26, p. 169‑186
  "Approximating values and solutions of NP-optimization problems: concepts and examples" (J. Lorenzo), Foundations of Computing and Decision Sciences, Jan 2001, p. 145‑168
  "Bridging gap between standard and differential polynomial approximation : the case of bin-packing" (J. Monnot, V. Paschos), Applied Mathematics Letters, Jan 1999, p. 127‑133
  "Asymptotic differential approximation ratio: definitions, motivations and application to some combinatorial problems" (V. Paschos), RAIRO-Operations Research, Jan 1999, p. 481‑507
  "A note on the approximation of a minimum-weight maximal independent set" (M. Demange), Computational Optimization and Applications, Jan 1999, p. 157‑169
  "Differential approximation algorithms for some combinatorial optimization problems" (P. Grisoni, V. Paschos), Theoretical Computer Science, Jan 1998, p. 107‑122
  "The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems" (V. Paschos), Computational Optimization and Applications, Jan 1997, p. 307‑324
  "Improved approximations for maximum independent set via approximation chains" (V. Paschos), Applied Mathematics Letters, Jan 1997, p. 105‑110
  "A generalization of Koenig-Egervery graphs and a new heuristic for maximum independent set problem with improved approximation ratios" (V. Paschos), European Journal of Operational Research, Jan 1997, p. 580‑592
  "Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale" (V. Paschos), Mathématiques, Informatique et Applications aux sciences de l'Homme, Jan 1996, p. 51‑66
  "On an approximation measure founded on the links between optimization and polynomial approximation theory" (V. Paschos), Theoretical Computer Science, Jan 1996, p. 117‑141
  "L'approximabilité de la couverture de sommets et d'un problème de programmation convexe par rapport à celle d'une classe de problèmes de stabilité" (V. Paschos), Notes aux Comptes Rendus de l'Académie des Sciences de Paris, Jan 1995, p. 645‑648
  "Quelques résultats dans le cadre d'une nouvelle théorie de l'approximation polynomiale" (P. Grisoni, V. Paschos), Notes aux Comptes Rendus de l'Académie des Sciences de Paris, Jan 1994, p. 289‑292
  "Approximation algorithms for minimum set covering problem : a survey" (V. Paschos), Foundations of Computing and Decision Sciences, Jan 1994
  "Approximation results for the minimum graph coloring problem" (P. Grisoni, V. Paschos), Information Processing Letters, Jan 1994, p. 19‑23
  "Quelques étapes vers la conciliation de la théorie d'approximation polynomiale et celle d'optimisation : une nouvelle théorie d'approximation polynomiale et résultats préliminaires" (V. Paschos), Notes aux Comptes Rendus de l'Académie des Sciences de Paris, Jan 1993, p. 409‑414


Chapters
  A Model for the Design of a Minimum-cost Telecommunication Network. In: Applications of Combinatorial Optimization (with C. Murat, V. Paschos, S. Toulouse). London - Hoboken (UK - USA) : ISTE - WILEY, Vangelis Th. Paschos. 2010, p. 209-224
  An Introduction to Inverse Combinatorial Problems . In: Paradigms of Combinatorial Optimization (Problems and New Approaches) (with J. Monnot). London - Hoboken (UK - USA) : ISTE - WILEY, Vangelis Th. Paschos. 2010, p. 547-586 (Adapted and updated from"Optimisation combinatoire 2", chap. 5, Paris (France) : Hermes Sciences, Paschos V.T.. 2005 )
  Polynomial Approximation. In: Paradigms of Combinatorial Optimization (Problems and New Approaches) (with V. Pascos). London - Hoboken (UK - USA) : ISTE - WILEY, Vangelis Th. Paschos. 2010, p. 331-349 (Adapted and updated from "Optimisation combinatoire 2", chap. 1, Paris (France) : Hermes Sciences, Paschos V.T.. 2005)
  Weighted edge coloring. In: Combinatorial optimization and theoretical computer science (with B. Escoffier, G. Lucarrelli, I. Milis, J. Monnot, V. Paschos, D. De Werra). Hoboken (USA) : WILEY, Vangelis Th. Paschos. 2008
  Complexity ans approximation results for the min weighted node coloring problem. In: Combinatorial optimization and theoretical computer science (with B. Escoffier, J. Monnot, V. Paschos, D. De Werra). Hoboken (USA) : WILEY, Vangelis Th. Paschos. 2008
  The Online Track Assignment Problem. In: Combinatorial Optimization and Theoretical Computer Science (with G. Di Stefano, B. Leroy-Beaulieu). Hoboken (USA) : WILEY, Vangelis Th. Paschos. 2008
  Approximation polynomiale. In: Optimisation combinatoire 2 (with V. Paschos). Paris (France) : Hermes Sciences, Paschos V.T.. 2005 (English and updated version in "Paradagms of Combinatorial Optimization", ISTE - WILEY, 2010)
  Une introduction aux problèmes combinatoires inverses. In: Optimisation combinatoire 2 (with J. Monnot). Paris (France) : Hermes Sciences, Paschos V.T.. 2005 (English and updated version in "Paradagms of Combinatorial Optimization", ISTE - WILEY, 2010)


Other Publications
Articles published in conference proceedings
  "Minimum maximal matching is NP-hard in regular bipartite graphs", With T. Ekim. In : Lecture Notes in Computer Sciences 4978, Theory and Applications of Models of Computation, TAMC 2008. Xi'an (China) : Springer, 2008, p. 364-374
  "Inverse booking problem: inverse chromatic number problem in interval graphs", With Y. Chung, JF. Culus. In : Lecture Notes in Computer Sciences 4921, WALCOM: Algorithms and Computation. Dhaka (Bangladesh) : Elsevier, 2008, p. 180-187
  "On-line Bin-packing Problem: Maximizing the Number of Unused Bins", With B. Kouakou, E. Soutif. In : Actes du 7ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision,. Lille (France) : Presses Universitaires de Valenciennes, 2006, p. 107-120
  "Oriented Coloring: Complexity and Approximation", With J. Culus. In : 32rd Conference on Current Trends in Theory and Practice of Computer Science - LNCS 3831,. Berlin (Germany) : Springer, 2006, p. 226-236
  "The Hypercoloring Problem: Complexity and Approximability Results when the Chromatic Number is Small", With D. De Werra, J. Monnot, V. Paschos. In : Proceedings of the 30th International Workshop, WG 2004,. Bad Honnef (Allemagne) : TWTH, 2004
  "Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation", With D. De Werra, B. Escoffier, J. Monnot, V. Paschos. In : Algorithms and Computation: 15th International Symposium, ISAAC 2004. Lecture Notes in Computer Science (LNC 3341),. Hong Kong (Chine) : Springer Verlag, 2004
  "Weighted Node Coloring: When Stable Sets Are Expensive", With D. Werra (de), J. Monnot, V. Paschos. In : Proceedings of the 28th International Workshop, Graph Theoretic Concepts in Computer Science, WG 2002. Cesky Krumlov (République Tchèque) : Springer, 2002, p. 114-125
  "Two-steps combinatorial optimization", With V. Paschos. In : Constaint Programming & Logic Programming: Workshop OLCP'01: On-line Combinatorial Problem Solving and Constraint Programming,. Paphos (Cyprus) : THALES Research and Technology, 2001
  "Constructive - non Constructive approximation and maximum independent set problem", With V. Paschos. In : Lecture Notes in Computer Science, Vol. 1120, Proc. of CCS'95. : Springer Verlag, 1996, p. 194-207


Scientific Activities
Editorial Board Membership
  Mathematics and Social Sciences, CAMS
  International Journal of Mathematics and Statistics, CESER
  Bulletin of the Transilvania University of Brasov (serie III), Transilvania University Press
  Discrete Applied Mathematics, Elsevier (with Vadim Lozin, Christophe Picouleau and Bernard Ries)
  International Journal of Applied Management Science, Inderscience Publishers (with Dr. Angelo Sifaleras and Dr. Jason Papathanasiou )



Affiliations and Academic Responsibilities


Member of the French society of operations research (ROADEF);

Member of the European Society of Operations Research (EURO); 
 

In charge of the track "Combinatorial Optimization" of "GDR Recherche Opérationnelle" (National Research Council - CNRS) (2005 - present)


Professional Experience

Professor, ESSEC, DIS department ( (2005-present)

Associated professor, ESSEC, DIS department (2001-2005)

Visiting professor (one mounth per year), Ecole Polytechnique Fédérale de Lausanne, Chair "ROSE", Switzerland (2003 - present)

Assistant professor, Computer Science, Paris I University (1994-2001)
Useful Links
Information Systems, Decision Sciences and Statistics (IDS)
Chair Media & Entertainment
Personal Links
GDR Recherche Opérationnelle
Société française de RO
Contact
E-mail

ESSEC Business School
Av. Bernard Hirsch
B.P. 50105
95021 Cergy Pontoise Cedex
France

This website uses cookies. By continuing to browse this site, we will assume that you consent to the use of cookies. Find out more about cookies.

x
Help Me Choose a program