
Publications
Computers are useless. They can only give you answers. — Pablo Picasso
Papers
Scenario-Based Robust Optimization of Tree Structures
with Spyros Angelopoulos, Alex Elenter and Georgii Melidi. The 39th Annual AAAI Conference on Artificial Intelligence (AAAI), 2025.
[paper,
program]
Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms
with Spyros Angelopoulos, Alex Elenter and Yanni Lefki. Poster presentation at the Thirty-eighth Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
[paper,
slides,
program]
Contract Scheduling with Distributional and Multiple Advice
with Spyros Angelopoulos, Marcin Bienkowski and Bertrand Simon. International Joint Conference
on Artificial Intelligence (IJCAI), 2024.
[paper,
program]
Online Computation with Untrusted Advice
with Spyros Angelopoulos, Shendan Jin, Shahin Kamali and Marc Renault. Journal of Computer and System Sciences, 2024. Preliminary version was presented at The 11th Innovations in Theoretical Computer Science (ITCS), 2020.
[paper,
doi]
Best-of-two-worlds analysis of online search
with Spyros Angelopoulos and Shendan Jin. Algorithmica, 2023. Preliminary version was presented at The 36th International Symposium on Theoretical Aspects of Computer Science (STACS), 2019.
[paper, slides,
doi]
On price-induced minmax matchings
with Mathieu Mari and Ulrike Schmidt-Kraepelin.
[paper,
slides]
Scheduling with a processing time oracle
with Fanny Dufossé, Noël Nadal, Denis Trystram and Óscar C. Vásquez.
Applied Mathematical Modelling, 104: 701-720, April 2022.
[paper,
doi,
slides,
programs]
Orienting (hyper)graphs under explorable stochastic uncertainty
with Evripidis Bampis, Thomas Erlebach, Murilo S. de Lima, Nicole Megow, Jens Schlöter.
European Symposium on Algorithms (ESA), September 2021.
[paper,
doi,
slides]
New Results on 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ý.
Theoretical Computer Science, 2021.
[doi]
Randomized Two-Valued Bounded Delay Online Buffer Management
with Shahin Kamali. Operations Research Letters, 49(2): 246-249, 2021.
[paper,
slides,
doi]
older
- 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.