Claire Mathieu

135 papers A* 26A 8B 10C 1Journal 81Unranked 8

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	A tight (1.5+ε )-approximation for unsplittable capacitated vehicle routing on trees. Math. Program. Claire Mathieu, Hang Zhou
2025	—	`conf`	Estimating the Electoral Consequences of Legislative Redistricting in France. FAccT Evripidis Bampis, Thomas Ehrhard, Bruno Escoffier, Claire Mathieu, Fanny Pascual, David Saulpic
2025	J	`jnl`	Scheduling (Dagstuhl Seminar 25121). Dagstuhl Reports Claire Mathieu, Nicole Megow, Benjamin Moseley, Frits C. R. Spieksma, Alexander Lindermayr
2025	A*	`conf`	The SpaceSaving± Family of Algorithms for Data Streams with Bounded Deletions. ICDE Fuheng Zhao, Divyakant Agrawal, Amr El Abbadi, Claire Mathieu, Ahmed Metwally, Michel de Rougemont
2024	J	`jnl`	Apportionment with parity constraints. Math. Program. Claire Mathieu, Victor Verdugo
2024	J	`jnl`	Competitive Data-Structure Dynamization. ACM Trans. Algorithms Claire Mathieu, Rajmohan Rajaraman, Neal E. Young, Arman Yousefi
2024	J	`jnl`	Fairness of linear regression in decision making. Int. J. Data Sci. Anal. Vincent Cohen-Addad, Surya Teja Gavva, Karthik C. S., Claire Mathieu, Namrata
2024	J	`jnl`	Rotation distance using flows. CoRR Claire Mathieu, William Thurston
2023	J	`jnl`	A Detailed Analysis of the SpaceSaving± Family of Algorithms with Bounded Deletions. CoRR Fuheng Zhao, Divyakant Agrawal, Amr El Abbadi, Claire Mathieu, Ahmed Metwally, Michel de Rougemont
2023	J	`jnl`	A PTAS for Capacitated Vehicle Routing on Trees. ACM Trans. Algorithms Claire Mathieu, Hang Zhou
2023	A*	`conf`	A Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees. ICALP Claire Mathieu, Hang Zhou
2023	J	`jnl`	A simple algorithm for graph reconstruction. Random Struct. Algorithms Claire Mathieu, Hang Zhou
2023	A	`conf`	An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees. STACS Marc Dufay, Claire Mathieu, Hang Zhou
2023	J	`jnl`	Approximating Maximum Integral Multiflows on Bounded Genus Graphs. Discret. Comput. Geom. Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Jens Vygen
2023	J	`jnl`	Correlation Clustering and Two-Edge-Connected Augmentation for Planar Graphs. Algorithmica Philip N. Klein, Claire Mathieu, Hang Zhou
2023	J	`jnl`	Errata for "SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model". Proc. VLDB Endow. Fuheng Zhao, Divyakant Agrawal, Amr El Abbadi, Ahmed Metwally, Claire Mathieu, Michel de Rougemont
2023	J	`jnl`	Iterated tour partitioning for Euclidean capacitated vehicle routing. Random Struct. Algorithms Claire Mathieu, Hang Zhou
2023	J	`jnl`	Testing frequency distributions in a stream. CoRR Claire Mathieu, Michel de Rougemont
2023	A	`conf`	Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm. ITCS Fabrizio Grandoni, Claire Mathieu, Hang Zhou
2022	A*	`conf`	A PTAS for Capacitated Vehicle Routing on Trees. ICALP Claire Mathieu, Hang Zhou
2022	J	`jnl`	A Tight 3/2+ε-Approximation for Unsplittable Capacitated Vehicle Routing on Trees. CoRR Claire Mathieu, Hang Zhou
2022	J	`jnl`	An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees. CoRR Marc Dufay, Claire Mathieu, Hang Zhou
2022	J	`jnl`	Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm. CoRR Fabrizio Grandoni, Claire Mathieu, Hang Zhou
2021	J	`jnl`	A PTAS for Capacitated Vehicle Routing on Trees. CoRR Claire Mathieu, Hang Zhou
2021	A	`conf`	A Simple Algorithm for Graph Reconstruction. ESA Claire Mathieu, Hang Zhou
2021	J	`jnl`	A Simple Algorithm for Graph Reconstruction. CoRR Claire Mathieu, Hang Zhou
2021	J	`jnl`	An Approximation Algorithm for Fully Planar Edge-Disjoint Paths. SIAM J. Discret. Math. Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Kevin Schewior, Jens Vygen
2021	J	`jnl`	Apportionment with Parity Constraints. CoRR Claire Mathieu, Victor Verdugo
2021	A*	`conf`	Approximating Maximum Integral Multiflows on Bounded Genus Graphs. ICALP Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Jens Vygen
2021	A*	`conf`	Competitive Data-Structure Dynamization. SODA Claire Mathieu, Rajmohan Rajaraman, Neal E. Young, Arman Yousefi
2021	J	`jnl`	Constrained School Choice with Incomplete Information. CoRR Hugo Gimbert, Claire Mathieu, Simon Mauras
2021	J	`jnl`	Large very dense subgraphs in a stream of edges. Netw. Sci. Claire Mathieu, Michel de Rougemont
2021	J	`jnl`	Mitigating COVID-19 outbreaks in workplaces and schools by hybrid telecommuting. PLoS Comput. Biol. Simon Mauras, Vincent Cohen-Addad, Guillaume Duboc, Max Dupré la Tour, Paolo Frasca, Claire Mathieu, Lulla Opatowski, Laurent Viennot
2021	B	`conf`	Probabilistic Analysis of Euclidean Capacitated Vehicle Routing. ISAAC Claire Mathieu, Hang Zhou
2021	J	`jnl`	Probabilistic Analysis of Euclidean Capacitated Vehicle Routing. CoRR Claire Mathieu, Hang Zhou
2021	B	`conf`	Two-Sided Matching Markets with Strongly Correlated Preferences. FCT Hugo Gimbert, Claire Mathieu, Simon Mauras
2020	J	`jnl`	An Approximation Algorithm for Fully Planar Edge-Disjoint Paths. CoRR Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Kevin Schewior, Jens Vygen
2020	J	`jnl`	Approximating maximum integral multiflows on bounded genus graphs. CoRR Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Jens Vygen
2020	J	`jnl`	Competitive Data-Structure Dynamization. CoRR Claire Mathieu, Rajmohan Rajaraman, Neal E. Young, Arman Yousefi
2020	J	`jnl`	Dynamic Clustering to Minimize the Sum of Radii. Algorithmica Monika Henzinger, Dariusz Leniowski, Claire Mathieu
2020	A*	`conf`	How to aggregate Top-lists: Approximation algorithms via scores and average ranks. SODA Claire Mathieu, Simon Mauras
2020	A*	`conf`	Instance-Optimality in the Noisy Value-and Comparison-Model. SODA Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu
2020	—	`conf`	Large Very Dense Subgraphs in a Stream of Edges. FODS Claire Mathieu, Michel de Rougemont
2020	J	`jnl`	Large Very Dense Subgraphs in a Stream of Edges. CoRR Claire Mathieu, Michel de Rougemont
2020	C	`conf`	Skyline Computation with Noisy Comparisons. IWOCA Benoît Groz, Frederik Mallmann-Trenn, Claire Mathieu, Victor Verdugo
2019	J	`jnl`	Hierarchical Clustering: Objective Functions and Algorithms. J. ACM Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu
2019	J	`jnl`	Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. SIAM J. Comput. Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
2019	—	`conf`	Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint. APPROX-RANDOM Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, Nabil H. Mustafa
2019	J	`jnl`	On popularity-based random matching markets. CoRR Hugo Gimbert, Claire Mathieu, Simon Mauras
2018	B	`conf`	Covering Clients with Types and Budgets. ISAAC Dimitris Fotakis, Laurent Gourvès, Claire Mathieu, Abhinav Srivastav
2018	J	`jnl`	Graph Reconstruction and Verification. ACM Trans. Algorithms Sampath Kannan, Claire Mathieu, Hang Zhou
2018	A*	`conf`	Hierarchical Clustering: Objective Functions and Algorithms. SODA Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu
2018	J	`jnl`	How to aggregate Top-lists: Score based approximation schemes. CoRR Claire Mathieu, Simon Mauras
2018	J	`jnl`	Instance-Optimality in the Noisy Value-and Comparison-Model - Accept, Accept, Strong Accept: Which Papers get in? CoRR Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu
2018	J	`jnl`	Semidefinite and linear programming integrality gaps for scheduling identical machines. Math. Program. Adam Kurpisz, Monaldo Mastrolilli, Claire Mathieu, Tobias Mömke, Victor Verdugo, Andreas Wiese
2017	A	`conf`	Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs. ESA Daniel Antunes, Claire Mathieu, Nabil H. Mustafa
2017	A	`conf`	Dynamic Clustering to Minimize the Sum of Radii. ESA Monika Henzinger, Dariusz Leniowski, Claire Mathieu
2017	J	`jnl`	Dynamic clustering to minimize the sum of radii. CoRR Monika Henzinger, Dariusz Leniowski, Claire Mathieu
2017	J	`jnl`	Hierarchical Clustering: Objective Functions and Algorithms. CoRR Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu
2017	A*	`conf`	Optimization of Bootstrapping in Circuits. SODA Fabrice Benhamouda, Tancrède Lepoint, Claire Mathieu, Hang Zhou
2017	J	`jnl`	Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141). Dagstuhl Reports Bodo Manthey, Claire Mathieu, Heiko Röglin, Eli Upfal
2017	J	`jnl`	Skyline Computation with Noisy Comparisons. CoRR Frederik Mallmann-Trenn, Claire Mathieu, Victor Verdugo
2016	J	`jnl`	Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221). Dagstuhl Reports Jeff Erickson, Philip N. Klein, Dániel Marx, Claire Mathieu
2016	A*	`conf`	Approximating connectivity domination in weighted bounded-genus graphs. STOC Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld
2016	—	`ed.`	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, Paris, France, September 7-9, 2016 APPROX-RANDOM Klaus Jansen, Claire Mathieu, José D. P. Rolim, Chris Umans
2016	A*	`conf`	Carpooling in Social Networks. ICALP Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Claire Mathieu, Rotem Zach
2016	A*	`conf`	Distance in the Forest Fire Model How far are you from Eve? SODA Varun Kanade, Reut Levi, Zvi Lotker, Frederik Mallmann-Trenn, Claire Mathieu
2016	A*	`conf`	Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. FOCS Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
2016	J	`jnl`	Optimization of Bootstrapping in Circuits. CoRR Fabrice Benhamouda, Tancrède Lepoint, Claire Mathieu, Hang Zhou
2016	J	`jnl`	Optimization of Bootstrapping in Circuits. IACR Cryptol. ePrint Arch. Fabrice Benhamouda, Tancrède Lepoint, Claire Mathieu, Hang Zhou
2016	B	`conf`	Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines. IPCO Adam Kurpisz, Monaldo Mastrolilli, Claire Mathieu, Tobias Mömke, Victor Verdugo, Andreas Wiese
2016	J	`jnl`	The power of local search for clustering. CoRR Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
2015	J	`jnl`	A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. ACM Trans. Algorithms Glencora Borradaile, Philip N. Klein, Claire Mathieu
2015	J	`jnl`	A Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing. Algorithmica Aparna Das, Claire Mathieu
2015	A	`conf`	Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs. STACS Philip N. Klein, Claire Mathieu, Hang Zhou
2015	A*	`conf`	Effectiveness of Local Search for Geometric Optimization. SoCG Vincent Cohen-Addad, Claire Mathieu
2015	A	`conf`	Homophily and the Glass Ceiling Effect in Social Networks. ITCS Chen Avin, Barbara Keller, Zvi Lotker, Claire Mathieu, David Peleg, Yvonne-Anne Pignolet
2015	—	`conf`	Near-Linear Query Complexity for Graph Inference. ICALP (1) Sampath Kannan, Claire Mathieu, Hang Zhou
2015	J	`jnl`	The Presburger Award 2016 - Call for Nominations. Bull. EATCS Claire Mathieu
2014	A*	`conf`	Approximating SODA David Eisenstat, Philip N. Klein, Claire Mathieu
2014	J	`jnl`	Convergence of Position Auctions under Myopic Best-Response Dynamics. ACM Trans. Economics and Comput. Matthew Cary, Aparna Das, Benjamin Edelman, Ioannis Giotis, Kurtis Heimerl, Anna R. Karlin, Scott Duke Kominers, Claire Mathieu, Michael Schwarz
2014	B	`conf`	Energy-Efficient Algorithms for Non-preemptive Speed-Scaling. WAOA Vincent Cohen-Addad, Zhentao Li, Claire Mathieu, Ioannis Milis
2014	J	`jnl`	Energy-efficient algorithms for non-preemptive speed-scaling. CoRR Vincent Cohen-Addad, Zhentao Li, Claire Mathieu, Ioannis Milis
2014	—	`conf`	Facility Location in Evolving Metrics. ICALP (2) David Eisenstat, Claire Mathieu, Nicolas Schabanel
2014	J	`jnl`	Facility Location in Evolving Metrics. CoRR David Eisenstat, Claire Mathieu, Nicolas Schabanel
2014	A*	`conf`	First Come First Served for Online Slot Allocation and Huffman Coding. SODA Monik Khare, Claire Mathieu, Neal E. Young
2014	J	`jnl`	Graph Verification and Reconstruction via Distance Oracles. CoRR Sampath Kannan, Claire Mathieu, Hang Zhou
2014	J	`jnl`	K-Slot SSTable Stack Compaction. CoRR Claire Mathieu, Carl Staelin, Neal E. Young
2014	J	`jnl`	Lower bounds for testing digraph connectivity with one-pass streaming algorithms. CoRR Glencora Borradaile, Claire Mathieu, Theresa Migler
2014	J	`jnl`	Recognizing Well-Parenthesized Expressions in the Streaming Model. SIAM J. Comput. Frédéric Magniez, Claire Mathieu, Ashwin Nayak
2014	J	`jnl`	The Unreasonable Success of Local Search: Geometric Optimization. CoRR Vincent Cohen-Addad, Claire Mathieu
2013	J	`jnl`	A polynomial-time approximation scheme for Euclidean Steiner forest CoRR Glencora Borradaile, Philip N. Klein, Claire Mathieu
2013	J	`jnl`	Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421). Dagstuhl Reports Glencora Borradaile, Philip N. Klein, Dániel Marx, Claire Mathieu
2013	J	`jnl`	First-Come-First-Served for Online Slot Allocation and Huffman Coding. CoRR Monik Khare, Claire Mathieu, Neal E. Young
2013	J	`jnl`	Graph Reconstruction via Distance Oracles CoRR Claire Mathieu, Hang Zhou
2013	—	`conf`	Graph Reconstruction via Distance Oracles. ICALP (1) Claire Mathieu, Hang Zhou
2013	J	`jnl`	Online constrained optimization with recourse. Inf. Process. Lett. Tess Avitabile, Claire Mathieu, Laura H. Parkinson
2013	J	`jnl`	The Min Mean-Weight Cycle in a Random Network. Comb. Probab. Comput. Claire Mathieu, David B. Wilson
2012	A*	`conf`	A polynomial-time approximation scheme for planar multiway cut. SODA MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, Claire Mathieu
2012	A*	`conf`	An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. SODA David Eisenstat, Philip N. Klein, Claire Mathieu
2012	J	`jnl`	Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme. SIAM J. Comput. Mordecai J. Golin, Claire Mathieu, Neal E. Young
2012	J	`jnl`	Lower bounds for randomized algorithms for online chain partitioning. Inf. Process. Lett. Claire Mathieu, Olga Ohrimenko
2012	—	`conf`	Maximum Matching in Semi-streaming with Few Passes. APPROX-RANDOM Christian Konrad, Frédéric Magniez, Claire Mathieu
2012	J	`jnl`	On the Number of Indecomposable Permutations with a Given Number of Cycles. Electron. J. Comb. Robert Cori, Claire Mathieu, John Michael Robson
2012	J	`jnl`	The min mean-weight cycle in a random network CoRR Claire Mathieu, David B. Wilson
2011	J	`jnl`	An efficient polynomial-time approximation scheme for Steiner forest in planar graphs CoRR David Eisenstat, Philip N. Klein, Claire Mathieu
2011	B	`conf`	Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack. IPCO Anna R. Karlin, Claire Mathieu, C. Thach Nguyen
2011	J	`jnl`	Maximum Matching in Semi-Streaming with Few Passes CoRR Christian Konrad, Frédéric Magniez, Claire Mathieu
2011	J	`jnl`	Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091). Dagstuhl Reports Klaus Jansen, Claire Mathieu, Hadas Shachnai, Neal E. Young
2010	A*	`conf`	A Quasi-polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing. SODA Aparna Das, Claire Mathieu
2010	A*	`conf`	Correlation Clustering with Noisy Input. SODA Claire Mathieu, Warren Schudy
2010	J	`jnl`	Foreword to special issue SODA 2009. ACM Trans. Algorithms Claire Mathieu
2010	J	`jnl`	Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack CoRR Anna R. Karlin, Claire Mathieu, C. Thach Nguyen
2010	J	`jnl`	Online Correlation Clustering CoRR Claire Mathieu, Ocan Sankur, Warren Schudy
2010	A	`conf`	Online Correlation Clustering. STACS Claire Mathieu, Ocan Sankur, Warren Schudy
2010	B	`conf`	Online Ranking for Tournament Graphs. WAOA Claire Mathieu, Adrian Vladu
2010	A*	`conf`	Recognizing well-parenthesized expressions in the streaming model. STOC Frédéric Magniez, Claire Mathieu, Ashwin Nayak
2010	B	`conf`	The Train Delivery Problem - Vehicle Routing Meets Bin Packing. WAOA Aparna Das, Claire Mathieu, Shay Mozes
2009	J	`jnl`	An ACM Trans. Algorithms Glencora Borradaile, Philip N. Klein, Claire Mathieu
2009	J	`jnl`	Maximizing profit using recommender systems CoRR Aparna Das, Claire Mathieu, Daniel Ricketts
2009	A*	`ed.`	Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009 SODA Claire Mathieu
2009	J	`jnl`	Recognizing well-parenthesized expressions in the streaming model CoRR Frédéric Magniez, Claire Mathieu, Ashwin Nayak
2009	J	`jnl`	Recognizing well-parenthesized expressions in the streaming model. Electron. Colloquium Comput. Complex. Frédéric Magniez, Claire Mathieu, Ashwin Nayak
2009	A*	`conf`	Sherali-adams relaxations of the matching polytope. STOC Claire Mathieu, Alistair Sinclair
2008	A*	`conf`	A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. FOCS Glencora Borradaile, Philip N. Klein, Claire Mathieu
2008	J	`jnl`	A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing CoRR Aparna Das, Claire Mathieu
2008	J	`jnl`	Distortion lower bounds for line embeddings. Inf. Process. Lett. Claire Mathieu, Charalampos Papamanthou
2008	—	`conf`	Improved Approximation Algorithms for Budgeted Allocations. ICALP (1) Yossi Azar, Benjamin E. Birnbaum, Anna R. Karlin, Claire Mathieu, C. Thach Nguyen
2008	J	`jnl`	On-line bipartite matching made simple. SIGACT News Benjamin E. Birnbaum, Claire Mathieu
2008	B	`conf`	Online multicast with egalitarian cost sharing. SPAA Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks
2008	A*	`conf`	Yet another algorithm for dense max cut: go greedy. SODA Claire Mathieu, Warren Schudy
2007	A*	`conf`	Greedy bidding strategies for keyword auctions. EC Matthew Cary, Aparna Das, Benjamin Edelman, Ioannis Giotis, Kurtis Heimerl, Anna R. Karlin, Claire Mathieu, Michael Schwarz
2007	B	`conf`	Steiner Tree in Planar Graphs: An WADS Glencora Borradaile, Philip N. Klein, Claire Mathieu
1987	J	`jnl`	Average Efficiency of Data Structures for Binary Image Processing. Inf. Process. Lett. Claire Mathieu, Claude Puech, Hossein Yahia
1987	J	`jnl`	Some Problems in Computational Geometry. Algorithmica Claire Mathieu