Publications

Papers

Tile Packing Tomography is NP-hard

with Marek Chrobak, Flavio Guíñez, Antoni Lozano, Nguyễn Kim Thắng. technical report.
[paper]

Polynomial Time Algorithms for Minimum Energy Scheduling

with Philippe Baptiste, Marek Chrobak, technical report. Preliminary version in Proc. of the 15th Annual European Symposium on Algorithms (ESA), 136-150, 2007.
[paper, slides, program 1, 2]

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

with Flavio Guíñez, Martín Matamala, Proc. of the 17th Annual European Symposium on Algorithms (ESA), 2009. ♥ best paper award
[paper, slides, program]

Finding total unimodularity in optimization problems solved by linear programs

with Mathilde Hurand, Algorithmica, DOI: 10.1007/s00453-009-9310-7, 2009. 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]

Online Scheduling of Bounded Length Jobs to Maximize Throughput

with Łukasz Jeż and Nguyễn Kim Thắng. Proc. of the 7th Workshop on Approximation and Online Algorithms (WAOA), 2009.
[paper]

Non-Clairvoyant Scheduling Games

with Nguyễn Kim Thắng. Proc. of the 2nd International Symposium on Algorithmic Game Theory (SAGT), 2009.
[paper, slides]

Collecting Weighted Items from a Dynamic Queue

with Marcin Bienkowski, Marek Chrobak, Mathilde Hurand, Artur Jeż, Łukasz Jeż, Grzegorz Stachowiak. Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009. previous version was entitled Generalized Whac-a-Mole.
[paper, program]

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]

Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems

with Marek Chrobak, Mathilde Hurand, Julien Robert. Proc. of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM), 2008.
[paper]

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]

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]

Competitive Analysis of Scheduling Algorithms for Aggregated Links

with Wojciech Jawor (first author) and Marek Chrobak. Algorithmica, DOI 10.1007/s00453-007-9053-2, 2007. Preliminary version in Proc. of the conference Latin American Theoretical INformatics (LATIN), pp. 617-628, 2006.
[long version]

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]

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.