Biographie et publications | Claire Mathieu - Informatique et sciences numériques

Biographie

Ancienne élève de l’ENS et titulaire d’une thèse en informatique de l’Université Paris-Sud, Claire Mathieu, actuellement directrice de recherche au CNRS, a travaillé comme chercheur CNRS à l’ENS-Lyon et comme professeur dans des institutions diverses : ENS (professeur attaché), Université Paris-Sud, École polytechnique, Université de Brown (USA). Elle fait de la recherche sur l’algorithmique, et en particulier sur la conception d’algorithmes pour trouver des solutions quasi optimales à des problèmes qui sont difficiles à résoudre exactement. Récemment, elle s’est intéressée à la modélisation de réseaux sociaux, à la reconstruction de graphes cachés, et aux graphes qui peuvent être dessinés dans le plan. En 2019, elle reçoit la médaille d'argent du CNRS.

Bibliographie sélective

Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics

Cohen-Addad V., Klein P. N. et Mathieu C., « Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics », SIAM Journal on Computing, 2019, p. 644-667, https://doi.org/10.1137/17M112717X.
Effectiveness of Local Search for Geometric Optimization

Cohen-Addad V. et Mathieu C., « Effectiveness of Local Search for Geometric Optimization », 31st International Symposium on Computational Geometry SoCG 2015, 2015, p. 329-343.
A Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing

Das A. et Mathieu C., « A Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing », Algorithmica 73, 2015, p. 115-142, https://doi.org/10.1007/s00453-014-9906-4.
Linear programming relaxations of maxcut

Fernandez de la Vega W. et Kenyon-Mathieu C., « Linear programming relaxations of maxcut », SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 2007, p. 53-61
How to rank with few errors

Kenyon-Mathieu C. et Schudy W., « How to rank with few errors », STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, p. 95-103.
The Data Broadcast Problem with Non-Uniform Transmission Times

Kenyon C. et Schabanel N., « The Data Broadcast Problem with Non-Uniform Transmission Times », Algorithmica 35, 2003, p. 146-175, https://doi.org/10.1007/s00453-002-0990-5.
Carpooling in Social Networks

Fiat A., Karlin A. R, Koutsoupias E., Mathieu C. et Zach R., « Carpooling in Social Networks », in : Díaz, J., Kirousis, L., Ortiz-Gracia, L., Serna, M. (eds) Extended Abstracts Summer 2015, Trends in mathematics book series, vol. 6, 2017, p. 29-34, https://doi.org/10.1007/978-3-319-51753-7_5.
Convergence of Position Auctions under Myopic Best-Response Dynamics

Carry M., Das A., Edelman B., Giotis I., Heimerl K., Karlin A. R., Kominers S. D., Mathieu C. et Schwarz M., « Convergence of Position Auctions under Myopic Best-Response Dynamics », ACM Trans. Economics and Computation, vol. 2, n° 3, 2014, art. 9, https://doi.org/10.1145/2632226.
Improved Approximation Algorithms for Budgeted Allocations

Azar, Y., Birnbaum, B., Karlin, A.R., Mathieu, C. et Nguyen, C.T. « Improved Approximation Algorithms for Budgeted Allocations », In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A. et Walukiewicz, I. (eds) Automata, Languages and Programming. ICALP 2008. Lecture Notes in Computer Science, vol. 5125, https://doi.org/10.1007/978-3-540-70575-8_16.
Online multicast with egalitarian cost sharing

Charikar M., Karloff H. J., Mathieu C., Naor J., Saks M. E., « Online multicast with egalitarian cost sharing », SPAA'08: Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures, 2008, p. 70-76, https://doi.org/10.1145/1378533.1378544.
Dynamic TCP Acknowledgment and Other Stories about e/(e-1)

Karlin A. R., Kanyon C., Randall D., « Dynamic TCP Acknowledgment and Other Stories about e/(e-1) », Algorithmica 36, 2003, p. 209–224, https://doi.org/10.1007/s00453-003-1013-x.
Distance in the Forest Fire Model How far are you from Eve?

Kanade V., Levi R., Lotker Z., Mallmann-Trenn F., Mathieu C., « Distance in the Forest Fire Model How far are you from Eve? », Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016, p. 1602-1620, https://doi.org/10.1137/1.9781611974331.ch109
Homophily and the Glass Ceiling Effect in Social Networks

Avin C., Keller B., Lortker Z., Mathieu C., Peleg D., Pignolet Y. A., « Homophily and the Glass Ceiling Effect in Social Networks », ITCS 2015, 2015, p. 41-50, https://doi.org/10.1145/2688073.2688097.
On the discrete Bak-Sneppen model of self-organized criticality

Barbay J. et Kenyon C., « On the discrete Bak-Sneppen model of self-organized criticality » SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, 2001, p. 928-933.
Selection in the Presence of Noise: The Design of Playoff Systems

Adler M., Gemmel P., Harchol-Balter M., Karp R. M. et Kenyon C., « Selection in the Presence of Noise: The Design of Playoff Systems », SODA '94: Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms , 1994, p. 564-572.
Commitment under uncertainty: Two-stage stochastic matching problems

Katriel I., Kenyon-Mathieu C. et Upfal E., « Commitment under uncertainty: Two-stage stochastic matching problems », in Arge, L., Cachin, C., Jurdziński, T. et Tarlecki, A. (eds) Automata, Languages and Programming. ICALP 2007, Lecture Notes in Computer Science book series, vol. 4596, 2007, p. 171-182.
Matchings in lattice graphs

Kenyon C., Randall D. et Sinclair A., « Matchings in lattice graphs » STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing, 1998, p. 738-746, https://doi.org/10.1145/167088.167278.
On the Sum-of-Squares algorithm for bin packing

Csirik J., Johnson D. S., Kenyon C., Orlin J. B., Shor P. W. et Weber R., « On the Sum-of-Squares algorithm for bin packing », Journal of the ACM, vol. 53, n° 1, 2006, p. 1-65, https://doi.org/10.1145/1120582.1120583, [arXiv : 0210013].
Correlation Clustering with Noisy Input

Mathieu C. et Schudy W., « Correlation Clustering with Noisy Input », Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010, p. 712-728, https://doi.org/10.1137/1.9781611973075.58.
Near-Linear Query Complexity for Graph Inference

Kannan S., Mathieu C. et Zhou H., « Near-Linear Query Complexity for Graph Inference », ICALP 2015. Lecture Notes in Computer Science, vol. 9134, 2015, p. 773-784, https://doi.org/10.1007/978-3-662-47672-7_63, [arXiv : 1402.4037].
Recognizing Well-Parenthesized Expressions in the Streaming Model

Magniez F., Mathieu C. et Nayak A., « Recognizing Well-Parenthesized Expressions in the Streaming Model », SIAM Journal on Computing, vol 43, n° 6, 2014, p. 1880-1905, https://doi.org/10.1137/130926122.