Team : RO - Operation Research

Axes : TMC (👥👥), AID (👥), ASN (👥).

Team leader :

Bruno Escoffier Campus Pierre et Marie Curie 26-00/419

Short presentation

The Operations Research team works on combinatorial optimization problems, with many applications to scheduling, network design but also lot-sizing, operations and supply chain management for example. We approach problems with algorithmic game theory, online and approximation algorithms, fixed parameter algorithms, self-stabilizing algorithms, search heuristics, blackbox complexity, mathematical programming, Markov decision processes and stochastic optimization. Our research both aims developing the theory and designing solutions for pure problems or real life applications.

scheduling, combinatorial optimization, operations research, exact and approximation algorithm, complexity.

No event planned at present.

Selected publications

Ch. Dürr, F. Guíñez, M. Matamala : “Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography”, SIAM Journal on Discrete Mathematics, vol. 26 (1), pp. 330-352, (ISBN: 0895-4801) [Dürr 2012a]
N. Absi, S. Dauzère‑Pérès, S. Kedad‑Sidhoum, B. Penz, Ch. Rapine : “Lot Sizing with Carbon Emission Constraints”, European Journal of Operational Research, vol. 227 (1), pp. 55-61, (ISBN: 0377-2217) [Absi 2013b]
S. Angelopoulos, P. Schweitzer : “Paging and list update under bijective analysis”, Journal of the ACM (JACM), vol. 60 (2), pp. 7, (ISBN: 0004-5411) [Angelopoulos 2013]
E. Bampis, D. Letsios, G. Lucarelli, E. Markakis, I. Milis : “On multiprocessor temperature-aware scheduling problems”, Journal of Scheduling, vol. 16 (5), pp. 529-538 [Bampis 2013c]
B. Doerr, C. Doerr, T. Kötzing : “The unbiased black-box complexity of partition is polynomial”, Artificial Intelligence, vol. 216, pp. 12, (Elsevier) [Doerr 2014g]
A. López‑Ortiz, S. Angelopoulos, A. Hamel : “Optimal Scheduling of Contract Algorithms for Anytime Problem-Solving”, Journal of Artificial Intelligence Research, vol. 51, pp. 533-554, (ISBN: 1076-9757) [López-Ortiz 2014]
Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Performance guarantees for a scheduling problem with common stepwise job payoffs”, Theoretical Computer Science, vol. 562, pp. 377-394, (ISBN: 0304-3975) [Seddik 2015]
É. Bonnet, B. Escoffier, Vangelis Th. Paschos, É. Tourniaire : “Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization”, Algorithmica, vol. 71 (3), pp. 566-580, (ISBN: 0178-4617) [Bonnet 2015b]
É. Bonnet, B. Escoffier, E. Kim, Vangelis Th. Paschos : “On Subexponential and FPT-Time Inapproximability”, Algorithmica, vol. 71 (3), pp. 541-565, (ISBN: 0178-4617) [Bonnet 2015a]
E. Bampis, A. Kononov, D. Letsios, G. Lucarelli, I. Nemparis : “From preemptive to non-preemptive speed-scaling scheduling”, Discrete Applied Mathematics, vol. 181, pp. 11-20, (Elsevier), (ISBN: 0166-218X) [Bampis 2015a]
E. Bampis, D. Letsios, G. Lucarelli : “Green scheduling, flows and matchings”, Theoretical Computer Science, vol. 579, pp. 126-136, (Elsevier) [Bampis 2015b]
P. Bendotti, P. Fouilhoux : “Feasibility recovery for the Unit-capacity Constrained Permutation Problem”, Discrete Optimization, vol. Volume 22, Part A, pp. 66-86, (Elsevier) [Bendotti 2016]
B. Doerr, C. Doerr, R. Spoehel, H. Thomas : “Playing Mastermind with Many Colors”, Journal of the ACM (JACM), vol. 63, (ACM) [Doerr 2016d]
S. Angelopoulos, D. Arsenio, Ch. Dürr, A. López‑Ortiz : “Multi-processor Search and Scheduling Problems with Setup Cost”, Theory of Computing Systems, (Springer Verlag) [Angelopoulos 2016d]
P. Bendotti, Ph. Chrétienne, P. Fouilhoux, A. Quilliot : “Anchored reactive and proactive solutions to the CPM-scheduling problem”, European Journal of Operational Research, vol. 261 (1), pp. 67-74, (Elsevier) [Bendotti 2017c]
L. Gourvès, J. Monnot, F. Pascual, D. Vanderpooten : “Bi-objective matchings with the triangle inequality”, Theoretical Computer Science, vol. 670, pp. 1-10, (Elsevier) [Gourvès 2017]
S. Kedad‑Sidhoum, F. Monna, G. Mounié, D. Trystram : “A Family of Scheduling Algorithms for Hybrid Parallel Platforms”, International Journal of Foundations of Computer Science, vol. 29 (1), pp. 63-90 [Kedad-Sidhoum 2018]
A. Carlier, C. Hanen, A. Munier‑Kordon : “The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays”, Journal of Scheduling, pp. 1-9, (Springer Verlag) [Carlier 2017]

All…