Claire Mathieu

According to our database1, Claire Mathieu authored at least 141 papers between 1987 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Approximating maximum integral multiflows on bounded genus graphs.
CoRR, 2020

An Approximation Algorithm for Fully Planar Edge-Disjoint Paths.
CoRR, 2020

Dynamic Clustering to Minimize the Sum of Radii.
Algorithmica, 2020

How to aggregate Top-lists: Approximation algorithms via scores and average ranks.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Instance-Optimality in the Noisy Value-and Comparison-Model.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Skyline Computation with Noisy Comparisons.
Proceedings of the Combinatorial Algorithms - 31st International Workshop, 2020

Large Very Dense Subgraphs in a Stream of Edges.
Proceedings of the FODS '20: ACM-IMS Foundations of Data Science Conference, 2020

2019
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics.
SIAM J. Comput., 2019

Hierarchical Clustering: Objective Functions and Algorithms.
J. ACM, 2019

On popularity-based random matching markets.
CoRR, 2019

Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint.
Proceedings of the Approximation, 2019

2018
Graph Reconstruction and Verification.
ACM Trans. Algorithms, 2018

Semidefinite and linear programming integrality gaps for scheduling identical machines.
Math. Program., 2018

How to aggregate Top-lists: Score based approximation schemes.
CoRR, 2018

Instance-Optimality in the Noisy Value-and Comparison-Model - Accept, Accept, Strong Accept: Which Papers get in?
CoRR, 2018

Covering Clients with Types and Budgets.
Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

2017
Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141).
Dagstuhl Reports, 2017

Skyline Computation with Noisy Comparisons.
CoRR, 2017

Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016
Optimization of Bootstrapping in Circuits.
IACR Cryptol. ePrint Arch., 2016

Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221).
Dagstuhl Reports, 2016

The power of local search for clustering.
CoRR, 2016

Approximating connectivity domination in weighted bounded-genus graphs.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

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

Carpooling in Social Networks.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest.
ACM Trans. Algorithms, 2015

The Presburger Award 2016 - Call for Nominations.
Bull. EATCS, 2015

A Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing.
Algorithmica, 2015

Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Homophily and the Glass Ceiling Effect in Social Networks.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Near-Linear Query Complexity for Graph Inference.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Effectiveness of Local Search for Geometric Optimization.
Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014
Convergence of Position Auctions under Myopic Best-Response Dynamics.
ACM Trans. Economics and Comput., 2014

K-Slot SSTable Stack Compaction.
CoRR, 2014

Graph Verification and Reconstruction via Distance Oracles.
CoRR, 2014

The Unreasonable Success of Local Search: Geometric Optimization.
CoRR, 2014

Lower bounds for testing digraph connectivity with one-pass streaming algorithms.
CoRR, 2014

Energy-Efficient Algorithms for Non-preemptive Speed-Scaling.
Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

First Come First Served for Online Slot Allocation and Huffman Coding.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Approximating <i>k</i>-center in planar graphs.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Facility Location in Evolving Metrics.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013
Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421).
Dagstuhl Reports, 2013

The Min Mean-Weight Cycle in a Random Network.
Comb. Probab. Comput., 2013

Graph Reconstruction via Distance Oracles.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012
Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme.
SIAM J. Comput., 2012

Lower bounds for randomized algorithms for online chain partitioning.
Inf. Process. Lett., 2012

On the Number of Indecomposable Permutations with a Given Number of Cycles.
Electron. J. Comb., 2012

An efficient polynomial-time approximation scheme for Steiner forest in planar graphs.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

A polynomial-time approximation scheme for planar multiway cut.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Maximum Matching in Semi-streaming with Few Passes.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091).
Dagstuhl Reports, 2011

Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack.
Proceedings of the Integer Programming and Combinatoral Optimization, 2011

2010
Foreword to special issue SODA 2009.
ACM Trans. Algorithms, 2010

Online Ranking for Tournament Graphs.
Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

The Train Delivery Problem - Vehicle Routing Meets Bin Packing.
Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

Online Correlation Clustering.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Correlation Clustering with Noisy Input.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

A Quasi-polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009
An <i>O</i>(<i>n</i> log <i>n</i>) approximation scheme for Steiner tree in planar graphs.
ACM Trans. Algorithms, 2009

Low Distortion Maps Between Point Sets.
SIAM J. Comput., 2009

On Hierarchical Diameter-Clustering and the Supplier Problem.
Theory Comput. Syst., 2009

Recognizing well-parenthesized expressions in the streaming model.
Electron. Colloquium Comput. Complex., 2009

Maximizing profit using recommender systems
CoRR, 2009

Sherali-adams relaxations of the matching polytope.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008
Commitment under uncertainty: Two-stage stochastic matching problems.
Theor. Comput. Sci., 2008

Alternation and redundancy analysis of the intersection problem.
ACM Trans. Algorithms, 2008

On-line bipartite matching made simple.
SIGACT News, 2008

Distortion lower bounds for line embeddings.
Inf. Process. Lett., 2008

Incremental Medians via Online Bidding.
Algorithmica, 2008

Online multicast with egalitarian cost sharing.
Proceedings of the SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2008

Yet another algorithm for dense max cut: go greedy.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Improved Approximation Algorithms for Budgeted Allocations.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007
Steiner Tree in Planar Graphs: An <i>O</i> ( <i>n</i> log <i>n</i> ) Approximation Scheme with Singly-Exponential Dependence on Epsilon.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

How to rank with few errors.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Linear programming relaxations of maxcut.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

A polynomial-time approximation scheme for Steiner tree in planar graphs.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Greedy bidding strategies for keyword auctions.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

2006
SIGACT news online algorithms column 10: competitiveness via doubling.
SIGACT News, 2006

Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes.
Math. Oper. Res., 2006

On the Sum-of-Squares algorithm for bin packing.
J. ACM, 2006

The reverse greedy algorithm for the metric <i>k</i>-median problem.
Inf. Process. Lett., 2006

How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments.
Electron. Colloquium Comput. Complex., 2006

Oblivious Medians Via Online Bidding.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Plan B: Uncertainty/Time Trade-Offs for Linear and Integer Programming.
Proceedings of the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2006

2005
On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing
CoRR, 2005

The reverse greedy algorithm for the metric k-median problem
CoRR, 2005

On profit-maximizing envy-free pricing.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004
OPT Versus LOAD in Dynamic Storage Allocation.
SIAM J. Comput., 2004

Sensitivity, block sensitivity, and l-block sensitivity of boolean functions.
Inf. Comput., 2004

Approximation Schemes for Metric Clustering Problems.
Proceedings of the STACS 2004, 2004

Approximation schemes for Metric Bisection and partitioning.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Approximation schemes for multidimensional packing.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003
The Data Broadcast Problem with Non-Uniform Transmission Times.
Algorithmica, 2003

Dynamic TCP Acknowledgment and Other Stories about e/(e-1).
Algorithmica, 2003

Approximation schemes for clustering problems.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding.
Proceedings of the Approximation, 2003

Deterministic Algorithm for the t-Threshold Set Problem.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

2002
Linear waste of best fit bin packing on skewed distributions.
Random Struct. Algorithms, 2002

A Polynomial Time Approximation Scheme for Metric MIN-BISECTION
Electron. Colloquium Comput. Complex., 2002

Polynomial Time Approximation Schemes for Metric Min-Sum Clustering
Electron. Colloquium Comput. Complex., 2002

Scheduling Independent Multiprocessor Tasks.
Algorithmica, 2002

Huffman coding with unequal letter costs.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Adaptive intersection and t-threshold problems.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001
A Randomized Approximation Scheme for Metric MAX-CUT.
J. Comput. Syst. Sci., 2001

Dynamic TCP acknowledgement and other stories about e/(e-1).
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Better approximation algorithms for bin covering.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

On the discrete Bak-Sneppen model of self-organized criticality.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Glauber Dynamics on Trees and Hyperbolic Graphs.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem.
Math. Oper. Res., 2000

Polynomial-time approximation scheme for data broadcast.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Scheduling to Minimize the Average Completion Time of Dedicated Tasks.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

1999
Error-resilient DNA computation.
Random Struct. Algorithms, 1999

<i>d</i>-Dimensional Range Search on Multicomputers.
Algorithmica, 1999

The Data Broadcast Problem with Non-Uniform Transmission Rimes.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Scheduling on a Constant Number of Machines.
Proceedings of the Randomization, 1999

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

A Self Organizing Bin Packing Heuristic.
Proceedings of the Algorithm Engineering and Experimentation, 1999

1998
Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing.
J. Algorithms, 1998

Multilayer Neural Networks and Polyhedral Dichotomies.
Ann. Math. Artif. Intell., 1998

1997
Data Structures' Maxima.
SIAM J. Comput., 1997

d-Dimensional Range Search on Multicomputers.
Proceedings of the 11th International Parallel Processing Symposium (IPPS '97), 1997

1996
Planar Cayley Graphs with Regular Dual.
Int. J. Algebra Comput., 1996

Perfect matchings in the triangular lattice.
Discret. Math., 1996

Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (Preliminary Version).
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Best-Fit Bin-Packing with Random Order.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Multilayer Neural Networks: One or Two Hidden Layers?
Proceedings of the Advances in Neural Information Processing Systems 9, 1996

Approximate Strip Packing.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1994
On Boolean Decision Trees with Faulty Nodes.
Random Struct. Algorithms, 1994

Scalable and architecture independent parallel geometric algorithms with high probability optimal time.
Proceedings of the Sixth IEEE Symposium on Parallel and Distributed Processing, 1994

Selection in the Presence of Noise: The Design of Playoff Systems.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993
Optimal Randomized Algorithms for Local Sorting and Set-Maxima.
SIAM J. Comput., 1993

Finding a Target Subnetwork in Sparse Networks with Random Faults.
Inf. Process. Lett., 1993

Matchings in lattice graphs.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992
How to Take Short Cuts.
Discret. Comput. Geom., 1992

Tiling a Polygon with Rectangles
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991
The Maximum Size of Dynamic Data Structures.
SIAM J. Comput., 1991

Maximum Queue Size and Hashing with Lazy Deletion.
Algorithmica, 1991

1990
On Evaluating Boolean Functions with Unreliable Tests.
Int. J. Found. Comput. Sci., 1990

1989
Verifying Partial Orders
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

General Methods for the Analysis of the Maximum Size of Dynamic Data Structures (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

1987
Some Problems in Computational Geometry.
Algorithmica, 1987


  Loading...