Publications

Online Maximum Matching with Recourse

with Spyros Angelopoulos, Shendan Jin. Journal of Combinatorial Optimization, 40: 974–1007, 2020. Preliminary version was presented at the International Symposium on Mathematical Foundations of Computer Science (MFCS), August 2018 and at the Modern Online Algorithms workshop (MOLI), July 2018.
[paper, slides, doi]

An Adversarial Model for Scheduling with Testing

with Thomas Erlebach, Nicole Megow, Julie Meißner. Algorithmica, (82) 3630–3675, 2020. Preliminary version appeared under the title "Scheduling with Explorable Uncertainty" at The 9th Innovations in Theoretical Computer Science Conference (ITCS), Jan 2018.
[paper, doi, slides]

Non-monotone DR-submodular Maximization: Approximation and Regret Guarantees

with Nguyễn Kim Thắng, Abhinav Srivastav and Léo Tible. International Joint Conference on Artificial Intelligence (IJCAI), 2020.
[paper, poster, doi]

Online Algorithms for Multi-Level Aggregation

with Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyễn Kim Thắng, Pavel Veselý. Operations Research, 68(1): 214-232, 2020. Preliminary version was presented in The 24th European Symposium on Algorithms (ESA), August 2016 and in The 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP) june 2015, under the title "Online Multilevel Acknowledgment with Bounded Depth".
[paper, doi, slides]

Online Computation with Untrusted Advice

with Spyros Angelopoulos, Shendan Jin, Shahin Kamali and Marc Renault. The 11th Innovations in Theoretical Computer Science (ITCS), 2020.
[short, long, doi]

Online Clique Clustering

with Marek Chrobak, Aleksander Fabijan and Bengt Nilsson. Algorithmica, (82) 938-965, 2020. Preliminary version was presented in Proc. of the 9th International Conference on Algorithms and Complexity, (CIAC) May 2015, under the title "Competitive Strategies for Online Clique Clustering".
[paper, slides, doi]

The expanding search ratio of a graph

with Spyros Angelopoulos and Thomas Lidbetter, Discrete Applied Mathematics, Volume 260, Pages 51-65, May 2019. Preliminary version was presented in The 33rd International Symposium on Theoretical Aspects of Computer Science (STACS), 2016.
[paper, slides, doi]

Online Bin Packing with Advice of Small Size

with Spyros Angelopoulos, Shahin Kamali, Marc Renault and Adi Rosén. Theory of Computing Systems, 1-29, 2018. Preliminary version was presented at The Algorithms and Data Structures Symposium (WADS), august 2015.
[paper, slides, doi]

The triangle scheduling problem

with Zdeněk Hanzálek, Christian Konrad, Yasmina Seddik, René Sitters, Óscar C. Vásquez and Gerhard Woeginger, Journal of Scheduling, 21(3), 305-312, 2018.
[paper, slides, program, doi]

Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling

with Łukasz Jeż and Oscar C. Vasquez, Theoretical Computer Science, 695, 28-41, 2017. Preliminary version was presented at The 9th Conference on Web and Internet Economics (WINE), 2013.
[paper, slides, doi]

The local-global conjecture for scheduling with non-linear cost

with Nikhil Bansal, Nguyễn Kim Thắng and Oscar C. Vásquez, Journal of Scheduling, 20(3), 2017. DOI:10.1007/s10951-015-0466-5. Preliminary version was presented at The 16th Workshop on Algorithm Engineering and Experiments (ALENEX), 2014, under the title "Order constraints for single machine scheduling with non-linear cost".
[paper, program]

Infinite linear programming and online searching with turn cost

with Spyros Angelopoulos and Diogo Arsénio. Theoretical Computer Science, 2017. DOI: 10.1016/j.tcs.2017.01.013

Multi-processor Search and Scheduling Problems with Setup Cost

with Spyros Angelopoulos, Diogo Arsénio and Alejandro López-Ortiz. Theory of Computing Systems, 2016. DOI: 10.1007/s00224-016-9691-3

On the Power of Advice and Randomization for Online Bipartite Matching

with Christian Konrad and Marc Renault, The 24th European Symposium on Algorithms (ESA), August 2016.
[paper]

A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines

with Odile Bellenguez-Morineau, Marek Chrobak and Damien Prot. Journal of Scheduling, 18(3): 299-304, 2015.
[paper]
Corrects an erroneous proof from The Complexity of Mean Flow Time Scheduling Problems with Release Times with Philippe Baptiste, Peter Brucker, Marek Chrobak, Svetlana A. Kravchenko and Francis Sourd, Journal of Scheduling, 10(2): 139-146, 2007. Part of this work was presented at MAPSP 2005 workshop under the title "Preemptive Multi-Machine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time". [paper, slides, program]

Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption

with Łukasz Jeż and Oscar C. Vasquez, Discrete Applied Mathematics, 196: 20-27, 2015.
[paper]

The Wide Partition Conjecture and the Atom Problem in Discrete Tomography

with Flavio Guíñez, Electronic Notes in Discrete Mathematics, 351-356, 2013. The VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), 2013.

A φ-Competitive Algorithm for Collecting Items with Increasing Weights from a Dynamic Queue

with Marcin Bienkowski, Marek Chrobak, Mathilde Hurand, Artur Jeż, Łukasz Jeż, Grzegorz Stachowiak. Theoretical Computer Science, 475, 92-102, 2013.
[paper]

Collecting Weighted Items from a Dynamic Queue

with Marcin Bienkowski, Marek Chrobak, Mathilde Hurand, Artur Jeż, Łukasz Jeż, Grzegorz Stachowiak. DOI 10.1007/s00453-011-9574-6, Algorithmica 65(1):60-94, 2013. Preliminary version in Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.
[paper, program]

Speed scaling with power down scheduling for agreeable deadlines

with Evripidis Bampis, Fadi Kacem and Ioannis Milis. Sustainable Computing: Informatics and Systems, 2(4):184-189, 2012.
[paper, slides, program]

Smooth Inequalities and Equilibrium Inefficiency in Scheduling Games

with Johanne Cohen and Nguyễn Kim Thắng. Proc. of the 8th Workshop on Internet & Network Economics (WINE), 2012.
[paper, slides]

Approximating the Throughput by Coolest First Scheduling

with Ioannis Milis, Julien Robert and Georgios Zois. Proc. of the 10th Workshop on Approximation and Online Algorithms (WAOA), 2012.
[slides]

Online Scheduling of Bounded Length Jobs to Maximize Throughput

with Łukasz Jeż and Nguyễn Kim Thắng. Journal of Scheduling 15(5):653-664, 2012. Preliminary version in Proc. of the 7th Workshop on Approximation and Online Algorithms (WAOA), 2009.
[paper, slides]

Polynomial Time Algorithms for Minimum Energy Scheduling

with Philippe Baptiste, Marek Chrobak, Journal ACM Transactions on Algorithms 8(3), article no 26, 2012. Preliminary version in Proc. of the 15th Annual European Symposium on Algorithms (ESA), 136-150, 2007.
[paper, slides 1, 2, program 1, 2]

Tile Packing Tomography is NP-hard

with Marek Chrobak, Flavio Guíñez, Antoni Lozano, Nguyễn Kim Thắng. Algorithmica, 64(2): 267-278, 2012. Preliminary version in Proc. of the 16th Annual International Computing and Combinatorics Conference (Cocoon), 254-263, 2010
[paper, slides]

Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard

with Flavio Guíñez, Martín Matamala, SIAM J. on Discrete Math, 26(1): 330-352, 2012. Preliminary version in Proc. of the 17th Annual European Symposium on Algorithms (ESA), 2009. ♥ best paper award
[paper, slides, program]

The interval ordering problem

with Maurice Queyranne, Frits C.R. Spieksma, Fabrice Talla Nobibon and Gerhard J. Woeginger. Discrete Applied Mathematics 160: 1094-1103, 2012.
[paper, slides]

Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems

with Marek Chrobak, Mathilde Hurand, Julien Robert. Sustainable Computing: Informatics and Systems, 1(3):241-247, 2011. Preliminary version in Proc. of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM), 2008.
[paper]

Non-Clairvoyant Scheduling Games

with Johanne Cohen and Nguyễn Kim Thắng. Theory of Computing Systems 49(1): 3-23, 2011. Preliminary version in Proc. of the 2nd International Symposium on Algorithmic Game Theory (SAGT), 2009.
[paper, slides]

Finding total unimodularity in optimization problems solved by linear programs

with Mathilde Hurand, Algorithmica, 59(2): 256-268, 2011. Preliminary version in Proc. of the 14th Annual European Symposium on Algorithms (ESA), 315-326, 2006. Contains results from a technical report called "A simple algorithm for scheduling equal sized jobs on parallel machines with release times and deadlines".
[paper, slides, programs 1, 2, 3]

Runway scheduling with holding loop

with Konstantin Artiouchine and Philippe Baptiste. European Journal of Operational Research, 189(3): 1254-1266, 2008. Preliminary version in Proceedings of Discrete Optimization Methods in Production and Logistics (DOM), pp. 96-101, Omsk-Irkutsk, Russia, 2004.
[program, doi]

Nash equilibria in Voronoi games on graphs

with Nguyễn Kim Thắng. Proc. of the 15th Annual European Symposium on Algorithms (ESA), 17-28, 2007.
[paper, slides, program]

Competitive Analysis of Scheduling Algorithms for Aggregated Links

with Wojciech Jawor (first author) and Marek Chrobak. Algorithmica, 51(4): 367-386, 2008. Preliminary version in Proc. of the conference Latin American Theoretical INformatics (LATIN), pp. 617-628, 2006.
[paper]

Quantum Query Complexity in Computational Geometry

with Abhinav Bahadur, Raghav Kulkarni and Thibault Lafaye. Proc. of the Conference on Quantum Information and Computation IV by The International Society for Optical Engineering (SPIE) 2006.
[paper]

Quantum query complexity of some graph problems

with Mark Heiligman, Peter Høyer and Mehdi Mhalla, SIAM J. of Computing. 35 (6):1310-1328, 2006. Preliminary version in Proc. of the 31st International Colloquium on Automata, Languages and Programming (ICALP), pp. 481-493, 2004. ♥ track A best paper award
[paper, slides]

A Note on Scheduling Equal-Length Jobs to Maximize Throughput

with Marek Chrobak, Wojciech Jawor, Łukasz Kowalik, Maciej Kurowski, Journal of Scheduling, Volume 9, Number 1, 71-73, 2006.
[long version]

Quantum Algorithms for Element Distinctness

with Harry Buhrman, Mark Heiligman, Peter Høyer, Fréderic Magniez, Miklos Santha, Ronald de Wolf. SIAM J. of Computing, vol. 34 (6), pp.1324-1330, 2005. Preliminary version in Proc. of the 16th IEEE Conference on Computational Complexity, pp. 131-137, 2001.
[conference, journal, slides]

Cellular automata and communication complexity

with Ivan Rapaport and Guillaume Theyssier, Theoretical Computer Science, vol. 322, pp. 355-368, 2004.
[paper, slides, webpage]

Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput

with Philippe Baptiste, Marek Chrobak, Wojciech Jawor and Nodari Vakhania, Operation Research Letters, vol. 32 (3), pp. 258-264, 2004.
[paper, program]

Tiling with bars under tomographic constraints

with Eric Goles, Ivan Rapaport, Eric Rémila. Theoretical Computer Science, vol. 290, pp. 1317--1329, 2003.
[paper, program]

A Note on Tiling under Tomographic Constraints

with Marek Chrobak, Peter Couperus and Gerhard Woeginger. Theoretical Computer Science, vol. 290, pp. 2125-2136, 2003.
[paper, slides]

A decision procedure for unitary quantum linear cellular automata

with Miklos Santha. SIAM J. of Computing, vol. 31 (4), pp.1076-1089, 2002. Preliminary version in Proc. of the 37th Symposium on Foundations of Computer Science (FOCS), pp. 37-45, 1996.
[paper, slides, program]

Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms

with Marek Chrobak. Theoretical Computer Science, vol 259, pp. 81-98, 2001. Preliminary version in Proc. of the 23rd International Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS vol 1450, pp. 185-193, 1998.
[paper, slides]

Reconstructing hv-Convex Polyominoes from Orthogonal Projections

with Marek Chrobak. Information Processing Letters, vol. 69, pp. 283-289, 1999.
[paper, slides, program]

Enumération et génération aléatoire de polyominos en réseau hexagonal

with Alain Denise and Fouad Ibn-Majdoub-Hassani. Proc. of the 9-th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC), pp. 222-234, 1997.
[paper, program]

A decision procedure for well formed quantum cellular automata

with Hương LêThanh and Miklos Santha. Random Structures & Algorithms, vol. 11, pp. 381-394, 1997. Preliminary version  in Proc. of the 13rd International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 281-292, 1996.
[paper]

Invited talks/tutorials

Introduction à l'algorithmique en ligne

ROADEF - Congrès annuel de la Société Française de Recherche Opérationnelle et Aide à la Décision, 2021
[slides, video]

Bijective analysis of online algorithms

MOTOR - Mathematical Optimization Theory and Operations Research, Ekaterinburg, 2019
[slides]

Optimizing with explorable uncertainty

LAGOS - The Latin and American Algorithms, Graphs and Optimization Symposium, 2017
[slides]

A survey on discrete tomography

ECCO - Conference of the European Chapter on Combinatorial Optimization, 2014
[slides]

Gestion de tampon en ligne,

ROADEF - Congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision, 2014
[abstract, slides]

Science Popularization (in french)

Se prendre au jeu du voyageur du commerce.

avec Pierre Fouilhoux. La Recherche. Hors-Série Jeux mathématiques, juin-juillet, 2018.

Sur la ligne.

Tangeante hors série numéro 75. Recherche Opérationnelle. 2021.

Manuscripts (in french)

Deux mariages et aucun enterrement (sur une chaîne de Markov)

mémoire de DEA, 1994.

Automates cellulaires quantiques finis

thèse , 1997.

Tomographie discrète, calcul quantique et ordonnancement

habilitation , 2005.