Arrow Research search

Author name cluster

Claire Mathieu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

47 papers
1 author row

Possible papers

47

SODA Conference 2021 Conference Paper

Competitive Data-Structure Dynamization

  • Claire Mathieu
  • Rajmohan Rajaraman
  • Neal E. Young
  • Arman Yousefi

Data-structure dynamization is a general approach for making static data structures dynamic. It is used extensively in geometric settings and in the guise of so-called merge (or compaction) policies in big-data databases such as Google Bigtable and LevelDB (our focus). Previous theoretical work is based on worst-case analyses for uniform inputs — insertions of one item at a time and constant read rate. In practice, merge policies must not only handle batch insertions and varying read/write ratios, they can take advantage of such non-uniformity to reduce cost on a per-input basis. To model this, we initiate the study of data-structure dynamization through the lens of competitive analysis, via two new online set-cover problems. For each, the input is a sequence of disjoint sets of weighted items. The sets are revealed one at a time. The algorithm must respond to each with a set cover that covers all items revealed so far. It obtains the cover incrementally from the previous cover by adding one or more sets and optionally removing existing sets. For each new set the algorithm incurs build cost equal to the weight of the items in the set. In the first problem the objective is to minimize total build cost plus total query cost, where the algorithm incurs a query cost at each time t equal to the current cover size. In the second problem, the objective is to minimize the build cost while keeping the query cost from exceeding k (a given parameter) at any time. We give deterministic online algorithms for both variants, with competitive ratios of Θ(log∗ n ) and k, respectively. The latter ratio is optimal for the second variant.

Details

SODA Conference 2020 Conference Paper

Instance-Optimality in the Noisy Value-and Comparison-Model

  • Vincent Cohen-Addad
  • Frederik Mallmann-Trenn
  • Claire Mathieu

Motivated by crowdsourced computation, peergrading, and recommendation systems, Braverman, Mao and Weinberg [7] studied the query and round complexity of fundamental problems such as finding the maximum ( max ), finding all elements above a certain value ( threshold - ν ) or computing the top− k elements (Top- k ) in a noisy environment. For example, consider the task of selecting papers for a conference. This task is challenging due to the crowdsourcing nature of peer reviews: the results of reviews are noisy and it is necessary to parallelize the review process as much as possible. We study the noisy value model and the noisy comparison model: In the noisy value model, a reviewer is asked to evaluate a single element: “What is the value of paper i? ” ( e. g. , accept). In the noisy comparison model (introduced in the seminal work of Feige, Peleg, Raghavan and Upfal [17]) a reviewer is asked to do a pairwise comparison: “Is paper i better than paper j? ” In this paper, we introduce new lower bound techniques for these classic problems. In comparison to previous work, our lower bounds are much more fine-grained: they focus on the interplay between round and query complexity and the dependency on the output size. In the setting of conference papers, this translates into a trade-off between number of reviews per paper and the number of review rounds necessary in order find the best 100 papers for the conference. We complement these results with simple algorithms which show that our lower bounds are almost tight. We then go beyond the worst-case and address the question of the importance of knowledge of the instance by providing, for a large range of parameters, instance-optimal algorithms with respect to the query complexity. We complement these results by showing that for some family of instances, no instance-optimal algorithm can exist.

Details

SODA Conference 2018 Conference Paper

Hierarchical Clustering: Objective Functions and Algorithms

  • Vincent Cohen-Addad
  • Varun Kanade
  • Frederik Mallmann-Trenn
  • Claire Mathieu

Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering was based on providing algorithms, rather than optimizing a specific objective, [19] framed similarity-based hierarchical clustering as a combinatorial optimization problem, where a ‘good’ hierarchical clustering is one that minimizes some cost function. He showed that this cost function has certain desirable properties, such as in order to achieve optimal cost, disconnected components must be separated first and that in ‘structureless’ graphs, i. e. , cliques, all clusterings achieve the same cost. We take an axiomatic approach to defining ‘good’ objective functions for both similarity and dissimilarity-based hierarchical clustering. We characterize a set of admissible objective functions (that includes the one introduced by Dasgupta) that have the property that when the input admits a ‘natural’ ground-truth hierarchical clustering, the ground-truth clustering has an optimal value. Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better and faster algorithms for hierarchical clustering. For similarity-based hierarchical clustering, [19] showed that a simple recursive sparsest-cut based approach achieves an O (log 3/2 n )-approximation on worst-case inputs. We give a more refined analysis of the algorithm and show that it in fact achieves an -approximation 1. This improves upon the LP-based O (log n )-approximation of [33]. For dissimilarity-based hierarchical clustering, we show that the classic average-linkage algorithm gives a factor 2 approximation, and provide a simple and better algorithm that gives a factor 3/2 approximation. This aims at explaining the success of these heuristics in practice. Finally, we consider a ‘beyond-worst-case’ scenario through a generalisation of the stochastic block model for hierarchical clustering. We show that Dasgupta's cost function also has desirable properties for these inputs and we provide a simple algorithm that for graphs generated according to this model yields a 1 + o(1) factor approximation.

Details

SODA Conference 2017 Conference Paper

Optimization of Bootstrapping in Circuits

  • Fabrice Benhamouda
  • Tancrède Lepoint
  • Claire Mathieu
  • Hang Zhou 0001

In 2009, Gentry proposed the first Fully Homomorphic Encryption (FHE) scheme, an extremely powerful cryptographic primitive that enables to perform computations, i. e. , to evaluate circuits, on encrypted data without decrypting them first. This has many applications, particularly in cloud computing. In all currently known FHE schemes, encryptions are associated with some ( n on-negative integer) noise level. At each evaluation of an AND gate, this noise level increases. This increase is problematic because decryption succeeds only if the noise level stays below some maximum level L at every gate of the circuit. To ensure that property, it is possible to perform an operation called bootstrapping to reduce the noise level. Though critical, boostrapping is a time-consuming operation. This expense motivates a new problem in discrete optimization: minimizing the number of bootstrappings in a circuit while still controlling the noise level. In this paper, we (1) formally define the bootstrap problem, (2) design a polynomial-time L -approximation algorithm using a novel method of rounding of a linear program, and (3) show a matching hardness result: (L — ∊)- inapproximability for any ∊ > 0.

Details

FOCS Conference 2016 Conference Paper

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

  • Vincent Cohen-Addad
  • Philip N. Klein
  • Claire Mathieu

We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in edge-weighted planar graphs, (2) k-median and k-means in edge-weighted planar graphs, (3) k-means in Euclidean space of bounded dimension. Our first and second results extend to minor-closed families of graphs. All our results extend to cost functions that are the pth power of the shortest-path distance. The algorithm is local search where the local neighborhood of a solution S consists of all solutions obtained from S by removing and adding 1/ε O(1) centers.

Details

SODA Conference 2014 Conference Paper

Approximating k -center in planar graphs

  • David Eisenstat
  • Philip N. Klein
  • Claire Mathieu

We consider variants of the metric k -center problem. Imagine that you must choose locations for k firehouses in a city so as to minimize the maximum distance of a house from the nearest firehouse. An instance is specified by a graph with arbitrary nonnegative edge lengths, a set of vertices that can serve as firehouses (i. e. , centers) and a set of vertices that represent houses. For general graphs, this problem is exactly equivalent to the metric k -center problem, which is APX-hard. We give a polynomial-time bicriteria approximation scheme when the input graph is a planar graph. We also give polynomial-time bicriteria approximation schemes for several generalizations: if, instead of all houses, we wish to cover a specified proportion of the houses; if the candidate locations for firehouses have rental costs and we wish to minimize not the number of firehouses but the sum of their rental costs; and if the input graph is not planar but is of bounded genus.

Details

SODA Conference 2012 Conference Paper

A polynomial-time approximation scheme for planar multiway cut

  • MohammadHossein Bateni
  • MohammadTaghi Hajiaghayi
  • Philip N. Klein
  • Claire Mathieu

Given an undirected graph with edge lengths and a subset of nodes (called the terminals ), the multiway cut (also called the multi-terminal cut ) problem asks for a subset of edges, with minimum total length, whose removal disconnects each terminal from all others. The problem generalizes minimum s-t cut, but is NP-hard for planar graphs and APX-hard for general graphs [11]. In this paper, we present a PTAS for multiway cut on planar graphs.

Details

SODA Conference 2010 Conference Paper

A Quasi-polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing

  • Aparna Das
  • Claire Mathieu

In the capacitated vehicle routing problem, introduced by Dantzig and Ramser in 1959, we are given the locations of n customers and a depot, along with a vehicle of capacity k, and wish to find a minimum length collection of tours, each starting from the depot and visiting at most k customers, whose union covers all the customers. We give a quasi-polynomial time approximation scheme for the setting where the customers and the depot are on the plane, and distances are given by the Euclidean metric.

Details

FOCS Conference 2008 Conference Paper

A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest

  • Glencora Borradaile
  • Philip N. Klein
  • Claire Mathieu

We give a randomized O(n 2 log n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed epsi > 0 and given any n pairs of terminals in the plane, our scheme finds a (1 + epsi)- approximation to the minimum-length forest that connects every pair of terminals.

Details

STOC Conference 2007 Conference Paper

How to rank with few errors

  • Claire Mathieu
  • Warren Schudy

We present a polynomial time approximation scheme (PTAS) for the minimum feedback arc set problem on tournaments. A simple weighted generalization gives a PTAS for Kemeny-Young rank aggregation.

Details

STOC Conference 2003 Conference Paper

Approximation schemes for clustering problems

  • Wenceslas Fernandez de la Vega
  • Marek Karpinski
  • Claire Mathieu
  • Yuval Rabani

Let k be a fixed integer. We consider the problem of partitioning an input set of points endowed with a distance function into k clusters. We give polynomial time approximation schemes for the following three clustering problems: Metric k -Clustering, l 2 2 k -Clustering, and l 2 2 k -Median. In the k -Clustering problem, the objective is to minimize the sum of all intra-cluster distances. In the k -Median problem, the goal is to minimize the sum of distances from points in a cluster to the (best choice of) cluster center. In metric instances, the input distance function is a metric. In l 2 2 instances, the points are in R d and the distance between two points x,y is measured by x−y 2 2 (notice that (R d , ⋅ 2 2 is not a metric space). For the first two problems, our results are the first polynomial time approximation schemes. For the third problem, the running time of our algorithms is a vast improvement over previous work.

Details

FOCS Conference 2001 Conference Paper

Glauber Dynamics on Trees and Hyperbolic Graphs

  • Claire Mathieu
  • Elchanan Mossel
  • Yuval Peres

We study discrete time Glauber dynamics for random configurations with local constraints (e. g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap 1-/spl lambda//sub 2/) for the dynamics on trees and on certain hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that if the relaxation time /spl tau//sub 2/ satisfies /spl tau//sub 2/=O(n), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.

Details

FOCS Conference 2000 Conference Paper

Linear Waste of Best Fit Bin Packing on Skewed Distributions

  • Claire Mathieu
  • Michael Mitzenmacher

We prove that best-fit bin packing has linear waste on the discrete distribution U{j, k} (where items are drawn uniformly from the set {1/k, 2/k, .. ., j/k}) for sufficiently large k when j=/spl alpha/k and 0. 66/spl les//spl alpha/<2/3. Our results extend to continuous skewed distributions, where items are drawn uniformly on [0, a], for 0. 66/spl les/a<2/3. This implies that the expected asymptotic performance ratio of best-fit bin packing is strictly greater than 1 for these distributions.

Details

FOCS Conference 1999 Conference Paper

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates

  • Foto N. Afrati
  • Evripidis Bampis
  • Chandra Chekuri
  • David R. Karger
  • Claire Mathieu
  • Sanjeev Khanna
  • Ioannis Milis
  • Maurice Queyranne

We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation schemes for several variants of this problem. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our schemes are efficient: for all variants the running time for /spl alpha/(1+/spl epsiv/) approximation is of the form f(1//spl epsiv/, m)poly(n).

Details

FOCS Conference 1998 Conference Paper

A Randomized Approximation Scheme for Metric MAX-CUT

  • Wenceslas Fernandez de la Vega
  • Claire Mathieu

Metric MAX-CUT is the problem of dividing a set of points in metric space into two parts so as to maximize the sum of the distances between points belonging to distinct parts. We show that metric MAX-CUT has a polynomial time randomized approximation scheme.

Details

FOCS Conference 1996 Conference Paper

Approximate Strip Packing

  • Claire Mathieu
  • Eric Rémila

We present an approximation scheme for strip-packing, or packing rectangles into a rectangle of fixed width and minimum height, a classical NP-hard cutting-stock problem. The algorithm finds a packing of n rectangles whose total height is within a factor of (1+/spl epsiv/) of optimal, and has running time polynomial both in n and in 1//spl epsiv/. It is based on a reduction to fractional bin-packing, and can be performed by 5 stages of guillotine cuts.

Details

FOCS Conference 1992 Conference Paper

Tiling a Polygon with Rectangles

  • Claire Mathieu
  • Richard W. Kenyon

The authors study the problem of tiling a simple polygon of surface n with rectangles of given types (tiles). They present a linear time algorithm for deciding if a polygon can be tiled with 1 * m and k * 1 tiles (and giving a tiling when it exists), and a quadratic algorithm for the same problem when the tile types are m * k and k * m. >

Details