DOI 10.1007/s00453-007-9005-x Incremental Medians via Online Bidding (2010)
Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young, M. Chrobak, N. E. Young, ...
Abstract In the k-median problem we are given sets of facilities and customers, and distances between them. For a given set F of facilities, the cost of serving a customer u is the minimum distance...
Online Medians via Online Bribery (Extended Abstract) (2009)
Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young
We then consider the competitive ratio with respect to size. An algorithm is s-size-competitive if, for each k, the cost of Fk is at most the minimum cost of any set of k facilities, while the size...
We study discrete time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with vertices and of bounded degree. We...
ABSTRACT Polynomial-Time Approximation Scheme for Data Broadcast (2008)
Claire Kenyon, Nicolas Schabanel, Neal Young
The data broadcast problem is to find a schedule for broad-casting a given set of messages over multiple channels. The goal is to minimize the cost of the broadcast plus the ex-pected response time...
Oblivious Medians Via Online Bidding (Extended Abstract) (2008)
Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young
Abstract. Following Mettu and Plaxton [22, 21], we study oblivious algorithms for the k-medians problem. Such an algorithm produces an incremental sequence of facility sets. We give improved...
Alternation and Redundancy Analysis of the Intersection Problem (2008)
The intersection of sorted arrays problem has applications in search engines such as Google. Previous work propose and compare deterministic algorithms for this problem, in an adaptive analysis based...
Categories and Subject Descriptors (2008)
We initiate the study of the minimum distortion problem: given as input two n-point metric spaces, find a bijection between them with minimum distortion. This is an abstraction of certain geometric...
Alternation and Redundancy Analysis of the Intersection Problem (2008)
BARBAY, JEREMY, KENYON, CLAIRE
The intersection of sorted arrays problem has applications in search engines such as Google. Previous work has proposed and compared deterministic algorithms for this problem, in an adaptive analysis...
Broadcasting on Trees and the Ising Model \Lambda (2008)
William Evans, Claire Kenyon, Yuval Peresy, Leonard J. Schulmanz
1
In the bin packing problem, one is given a sequence (2007)
Claire Kenyon, Universite Paris-sud, Michael Mitzenmacher
We prove that Best Fit bin packing has linear waste on the discrete distribution Ufj; kg (where items are drawn uniformly from the set f1=k; 2=3; \Delta \Delta \Delta; j=kg) for sufficiently large k...
Advances for Exact Resolution of Polyhedral Dichotomies By Multilayer Neural Networks (2007)
We study the number of hidden layers required by a multilayer neural network with threshold units to compute a dichotomy from R d to f0; 1g, defined by a finite set of hyperplanes. We show that this...
Proc Of Nd, Yann Le Guyadec, Bernard Virot, Luc Boug, Luc Boug, Claire Kenyon, ...
y Gauthier, Jean-Marc Geib, Christophe Gransart, Fred Hmery, Jean-Franois Mhaut, Jean-Louis Roch, Jean-Franois Roos, El-Ghazali Talbi, and Alexandre Vermeeghen. Algorithmes Parallles: Analyse et...
Marek Karpinski, Claire Kenyon, 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...
Sensitivity is one of the simplest, and block sensitivity one of the most useful, invariants of a boolean function. Nisan [8] and Nisan and Szegedy [9] have shown that block sensitivity is...
Adaptive Intersection and t-Threshold Problems (2007)
Consider the problem of computing the intersection of k sorted sets. In the comparison model, we prove a new lower bound which depends on the non-deterministic complexity of the instance, and implies...
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
In this paper we present a theoretical analysis of the deterministic on-line Sum of Squares algorithm (SS) for bin packing introduced and studied experimentally
Claire Kenyon, 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...
Adaptive Intersection and t-Threshold Problems (2007)
Consider the problem of computing the intersection of k sorted sets. In the comparison model, we prove a new lower bound which depends on the non-deterministic complexity of the instance, and implies...
Abstract On the Sum-of-Squares Algorithm for Bin Packing (2007)
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Cedex France
In this paper we present a theoretical analysis of the deterministic on-line Sum of Squares algorithm (SS) for bin packing, introduced and studied experimentally in [8], along with several new...
Frank Dehne, Claire Kenyon, Andreas Fabri
We present parallel computational geometry algorithms that are scalable, architecture independent, easy to implement, and have, with high probability, an optimal time complexity for uniformly...
Mordecai J. Golin, Claire Kenyon, Neal E. Young
In the standard Human coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding must...
Foto Afrati, Evripidis Bampis, Aleksei V. Fishkin, Klaus Jansen, Claire Kenyon
dedicated tasks
Claire Kenyon's Statement of Purpose (2007)
this paper, by providing a detailed analysis of a simple model, will help to clarify a diverse area
Claire Kenyon's research statement (2007)
this paper, by providing a detailed analysis of a simple model, will help to clarify a diverse area
Approximation Schemes for Metric Minimum Bisection and Partitioning (2007)
W. Fernandez De La Vega, Marek Karpinski, Claire Kenyon
We design polynomial time approximation schemes (PTASs) for Metric MINBISECTION, i.e. dividing a given nite metric space into two halves so as to minimize the sum of distances across the cut. The...
Marek Karpinski, Claire Kenyon
We design a polynomial time approximation scheme (PTAS) for the problem of Metric MIN-BISECTION of dividing a given nite metric space into two halves so as to minimize the sum of distances across...
Marek Karpinski, Claire Kenyon
z Abstract. We design the rst polynomial time approximation schemes (PTASs) for the problem of Metric MIN-BISECTION of dividing a given nite metric space into two halves so as to minimize the sum of...
Marek Karpinski, Claire Kenyon, Yuval Rabani
We give polynomial time approximation schemes for the problem of partitioning an input set of n points into a xed number k of clusters so as to minimize the sum over all clusters of the total...
Bin packing in multiple dimensions: Inapproximability results and approximation schemes (2006)
Nikhil Bansal, Jos É R. Correa, Claire Kenyon, Maxim Sviridenko
Abstract. We study the multidimensional generalization of the classical Bin Packing problem: Given a collection of d-dimensional rectangles of specified sizes, the goal is to pack them into the...
On hierarchical diameter-clustering and the supplier problems (2006)
Abstract We study the problem of hierarchical clustering to minimize the diameter of clusters of a given point set, and the hierarchical version of the k-supplier problem with customers arriving...
Bin packing in multiple dimensions: Inapproximability results and approximation schemes (2006)
Nikhil Bansal, José R. Correa, Claire Kenyon, Maxim Sviridenko
informs ® doi 10.1287/moor.1050.0168
Janos Csirik, David S. Johnson, Claire Kenyon
The Sum of Squares algorithm for bin packing was defined in [2] and studied in great detail in [1], where it was proved that its worst case performance ratio is at most 3. In this note, we improve...
OPT versus LOAD in Dynamic Storage Allocation (2003)
Adam L. Buchsbaum, Howard Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup
Dynamic Storage Allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L = LOAD...
A polynomial time approximation scheme for metric MIN-BISECTION (2002)
W. Fernandez De La Vega, Marek Karpinski, Claire Kenyon
We design a polynomial time approximation scheme (PTAS) for the problem of Metric MIN-BISECTION of dividing a given finite metric space into two halves so as to minimize the sum of distances across...
Huffman coding with unequal letter costs (2002)
Mordecai J. Golin, Claire Kenyon, Neal E. Young
In the standard Hu#man coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding...
Adaptive Intersection and t-Threshold Problems (2002)
Consider the problem of computing the intersection of k sorted sets whose sizes sum to n. In the comparison model, we prove a new lower bound which depends on the non-deterministic complexity of the...
Approximation Schemes for Clustering Problems in Finite Metrics and High Dimensional Spaces (2002)
W. Fernandez De La Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani
We give polynomial time approximation schemes (PTASs) for the problem of partitioning an input set of n points into a fixed number k of clusters so as to minimize the sum over all clusters of the sum...
Polynomial Time Approximation Schemes for Metric Min-Sum Clustering (2002)
W. Fernandez De La Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani
We give polynomial time approximation schemes for the problem of partitioning an input set of n points into a fixed number k of clusters so as to minimize the sum over all clusters of the total...
Dynamic TCP acknowledgement and other stories about e/(e-1 (2001)
Anna R. Karlin, Claire Kenyon, Dana Randall
x Abstract We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [8]. These problems are well-known to be generalizations of the...
Dynamic TCP acknowledgement and other stories about e/(e-1 (2001)
Anna R. Karlin, Claire Kenyon, Dana Randall
We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [7]. These problems are wellknown to be generalizations of the classical...
Dynamic TCP acknowledgement and other stories about e/(e-1 (2001)
Anna R. Karlin, Claire Kenyon, Dana Randall
We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [7]. These problems are well-known to be generalizations of the classical...
On the discrete Bak-Sneppen model of selforganized criticality (2001)
We propose a discrete variant of the Bak-Sneppen model for self-organized criticality. In this process, a configuration is an n-bit word, and at each step one chooses a random bit of minimum value...
Better Approximation Algorithms for Bin Covering (2001)
Janos Csirik, David S. Johnson, Claire Kenyon
Bin covering takes as input a list of item sizes and places them into bins of unit demand so as to maximize the number of bins whose demand is satisfied. This is in a sense a dual problem to the...
Better Approximation Algorithms for Bin Covering (2001)
Janos Csirik David, David S. Johnson, Claire Kenyon
Bin covering takes as input a list of item sizes and places them into bins of unit demand so as to maximize the number of bins whose demand is satisfied. This is in a sense a dual problem to the...
Dynamic TCP acknowledgement and other stories about e/(e-1 (2001)
Anna R. Karlin, Claire Kenyon, Dana Randall
x Abstract We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [8]. These problems are well-known to be generalizations of the...
Dynamic TCP Acknowledgement and Other Stories about e/(e-1) (2001)
Anna R. Karlin, Claire Kenyon, Dana Randall
We present the rst optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [8]. These problems are well-known to be generalizations of the classical...
Linear waste of best fit bin packing on skewed distributions (2000)
Claire Kenyon, Universite Paris-sud, 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,
Linear waste of best fit bin packing on skewed distributions (2000)
Claire Kenyon, Universite Paris-sud, 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,
Broadcasting on trees and the Ising model (2000)
William Evans, Claire Kenyon, Yuval Peres, Leonard J. Schulman
Consider a process in which information is transmitted from a given root node on a noisy tree network T. We start with an unbiased random bit R at the root of the tree, and send it down the edges of...
Broadcasting on trees and the Ising model (2000)
William Evans, Claire Kenyon, Yuval Peres, Leonard J. Schulman
Consider a process in which information is transmitted from a given root node on a noisy tree network T. We start with an unbiased random bit R at the root of the tree, and send it down the edges of...
Polynomial-time approximation scheme for data broadcast (2000)
Claire Kenyon, Nicolas Schabanel, Neal Young
The data broadcast problem is to nd a schedule for broadcasting a given set of messages over multiple channels. The goal is to minimize the cost of the broadcast plus the expected response time to...
On the discrete Bak-Sneppen model of self-organized criticality (2000)
We propose a discrete variant of the Bak-Sneppen model for Self-Organized criticality. In this process, a configuration is an n-bit word, and at each step one chooses a random bit of minimum value...
Linear Waste of Best Fit Bin Packing on Skewed Distributions (2000)
Claire Kenyon, 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/3, , j/k} for su#ciently large k when j = #k and .66 # #...
On the Sum-of-Squares Algorithm for Bin Packing (2000)
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
In this paper we present a theoretical analysis of the deterministic on-line Sum of Squares algorithm (SS) for bin packing, introduced and studied experimentally in [8], along with several new...
A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem (2000)
We present an asymptotic fully polynomial approximation scheme for strip-packing, or packing rectangles into a rectangle of fixed width and minimum height, a classical NP-hard cutting-stock problem....
Linear waste of best fit bin packing on skewed distributions (2000)
Claire Kenyon, Université Paris-sud
We prove that Best Fit bin packing has linear waste on the discrete distribution U fj � kg (where items are drawn uniformly from the set f1=k � 2=3 � �j=kg) for sufficiently large k when j =...
Linear waste of best fit bin packing on skewed distributions (2000)
Claire Kenyon, Michael Mitzenmacher
ABSTRACT: 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 kwhen j �...
The data broadcast problem with non-uniform transmission times (1999)
Claire Kenyon, Nicolas Schabanel
Abstract. The data broadcast problem consists in nding an innite schedule to broadcast a given set of messages so as to minimize the average service time to clients requesting messages, and the cost...
Approximation schemes for minimizing average weighted completion time with release dates (1999)
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
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...
Approximation schemes for minimizing average weighted completion time with release dates (1999)
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
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...
A Self Organizing Bin Packing Heuristic (1999)
Janos Csirik David, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber
. This paper reports on experiments with a new on-line heuristic for one-dimensional bin packing whose average-case behavior is surprisingly robust. We restrict attention to the class of...
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates (1999)
Foto Afrati Evripidis, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
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...
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates (1999)
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
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...
A Self-Organizing Bin Packing Heuristic (1999)
Janos Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber
. This paper reports on experiments with a new on-line heuristic for one-dimensional bin packing whose average-case behavior is surprisingly robust. We restrict attention to the class of...
The Data Broadcast Problem with Non-Uniform Transmission Times (1999)
Claire Kenyon, Nicolas Schabanel
. The data broadcast problem consists in finding an infinite schedule to broadcast a given set of messages so as to minimize the average response time to clients requesting messages, and the cost of...
A Self-Organizing Bin Packing Heuristic (1999)
Janos Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber
This paper reports experiments with a new and surprisingly robust on-line heuristic for one-dimensional bin packing. This new Sum of Squares algorithm (SS) is restricted to the class of...
A Self-Organizing Bin Packing Heuristic (1999)
Janos Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber
This paper reports experiments with a new and surprisingly robust on-line heuristic for one-dimensional bin packing. This new Sum of Squares algorithm (SS) is restricted to the class of...
The data broadcast problem with non-uniform transmission times (1999)
Claire Kenyon, Nicolas Schabanel
Abstract. The data broadcast problem consists in finding an infinite schedule to broadcast a given set of messages so as to minimize the average response time to clients requesting messages, and the...
Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (1998)
Alistair Sinclair, Alistair Sinclair, Claire Kenyon, Claire Kenyon, Claire Kenyon, Yuval Rabani, ...
We study the Best Fit algorithm for on-line bin packing under the distribution in which the item sizes are uniformly distributed in the discrete range f1=k � 2=k�:::�j=kg. Our main result is...
Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (1998)
[summary by Philippe Robert] This talk considers the average case behavior of the best fit algorithm for on-line bin packing in the case where the item sizes are uniformly distributed in f1=k; : : :...
Broadcasting on Trees and the Ising Model (1998)
William Evans, Claire Kenyon, Yuval Peres, Leonard J. Schulman
Consider a process in which information is transmitted from a given root node on a noisy tree network T . We start with an unbiased random bit R at the root of the tree, and send it down the edges of...
Broadcasting on Trees and the Ising Model (1998)
William Evans, Claire Kenyon, Yuval Peres, Leonard J. Schulman
Consider a process in which information is transmitted from a given root node on a noisy tree network T . We start with an unbiased random bit R at the root of the tree, and send it down the edges of...
Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (1998)
Preliminary Version, Claire Kenyon, Yuval Rabani, Alistair Sinclair
We study the average case performance of the Best Fit algorithm for on-line bin packing under the distribution Ufj; kg, in which the item sizes are uniformly distributed in the discrete range f1=k;...
A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem (1998)
Ecole Normale, Eric Rémila, Superieure Lyon, Unite Mixte, Recherche Cnrs-inria-ens Lyon, Claire Kenyon, ...
We present an asymptotic fully polynomial approximation scheme for strippacking, or packing rectangles into a rectangle of fixed width and minimum height, a classical NP -hard cutting-stock problem....
Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (1998)
Claire Kenyon, Yuval Rabani, Alistair Sinclair
We study the average case performance of the Best Fit algorithm for on-line bin packing under the distribution Ufj; kg, in which the item sizes are uniformly distributed in the discrete range f1=k;...
Best-Fit Bin-Packing with Random Order (1997)
Best-fit is the best known algorithm for on-line binpacking, in the sense that no algorithm is known to behave better both in the worst case (when Best-fit has performance ratio 1.7) and in the...
Error-Resilient DNA Computation (1997)
Richard M. Karp, Claire Kenyon, Orli Waarts
The DNA model of computation, with test tubes of DNA molecules encoding bit sequences, is based on three primitives, Extract-A-Bit, which splits a test tube into two test tubes according to the value...
d-dimensional range search on multicomputers (1996)
Afonso Ferreira, Claire Kenyon, Andrew Rau-chaplin, Stephane Ubeda
The range tree is a fundamental data structure for multi-dimensional point sets, and as such, is central in a wide range of geometric and database applications. In this paper, we describe the rst...
d-Dimensional Range Search on Multicomputers (1996)
Ecole Normale, Ecole Normale, Suprieure Lyon, Stéphane Ubéda, Suprieure Lyon, Afonso Ferreira, ...
Given a set L of n points in the d-dimensional Cartesian space E d , and a query specifying a domain q in E d , the Range Search problem consists in identifying the subset R(q) of the points of L...
Multilayer Neural Networks: One Or Two Hidden Layers? (1996)
Graham Brightwell, Claire Kenyon, Hélène Paugam-Moisy
We study the number of hidden layers required by a multilayer neural network with threshold units to compute a function f from R d to f0; 1g. In spite of similarity with the characterization of...
Approximating the Number of Monomer-Dimer Coverings of a Lattice (1996)
Claire Kenyon, Dana Randall, Alistair Sinclair
The paper studies the problem of counting the number of coverings of a d-dimensional rectangular lattice by a specified number of monomers and dimers. This problem arises in several models in...
Approximating the Number of Monomer-Dimer Coverings of a Lattice (1996)
Claire Kenyon, Dana Randall, Alistair Sinclair
The paper studies the problem of counting the number of coverings of a d-dimensional rectangular lattice by a specified number of monomers and dimers. This problem arises in several models in...
Approximating the Number of Monomer-Dimer Coverings of a Lattice (1996)
Claire Kenyon, Dana Randall, Alistair Sinclair
The paper studies the problem of counting the number of coverings of a d-dimensional rectangular lattice by a specified number of monomers and dimers. This problem arises in several models in...
d-dimensional range search on multicomputers (1996)
Afonso Ferreira, Claire Kenyon, Andrew Rau-chaplin, Stéphane Ubéda
The range tree is a fundamental data structure for multidimensional point sets, and as such, is central in a wide range of geometric and database applications. In this paper, we describe the first...
Error-resilient DNA computation (1996)
Richard M. Karp, Richard M. Karp, Claire Kenyon, Claire Kenyon, Orli Waarts, Orli Waarts
The DNA model of computation, with test tubes of DNA molecules encoding bit sequences, is based on three primitives, Extract-A-Bit, Merge-Two-Tubes and Detect-Emptiness. Perfect operations can test...
Selection in the Presence of Noise: The Design of Playoff Systems (1995)
Micah Adler, Peter Gemmell, Mor Harchol, Richard M. Karp, Claire Kenyon
this paper we consider the optimal design of such systems. We seek designs that are optimally efficient, in the sense that they minimize the number of rounds or the number of games needed to select...
Claire Kenyon, Claire Kenyon, Claire Kenyon
Best- t is the best known algorithm for on-line bin-packing, in the sense that no algorithm is known to behave better both in the worst case and in the average uniform case. In practice, Best- t...
Frank Dehne, Claire Kenyon, Andreas Fabri
Abstract * We present parallel computational geometry algorithms that are scalable, architecture independent, easy to implement, and have, with high probability, an optimal time complexity for...
Selection in the Presence of Noise: The Design of Playoff Systems (1994)
Micah Adler, Peter Gemmell, Mor Harchol, Richard M. Karp, Claire Kenyon
this paper we consider the optimal design of such systems. We seek designs that are optimally efficient, in the sense that they minimize the number of rounds or the number of games needed to select...
On Boolean Decision Trees with Faulty Nodes (1994)
We consider the problem of computing with faulty components in the context of the Boolean decision tree model, in which cost is measured by the number of input bits queried and the responses to...
Selection in the Presence of Noise: The Design of Playoff Systems (1994)
Micah Adler, Peter Gemmell, Mor Harchol, Richard M. Karp, Claire Kenyon
this paper we consider the optimal design of such systems. We seek designs that are optimally efficient, in the sense that they minimize the number of rounds or the number of games needed to select...
On Boolean Decision Trees with Faulty Nodes (1994)
We consider the problem of computing with faulty components in the context of the Boolean decision tree model, in which cost is measured by the number of input bits queried and the responses to...
Matchings in Lattice Graphs (1993)
Claire Kenyon, Dana Randall, Alistair Sinclair
We study the problem of counting the number of matchings of given cardinality in a d-dimensional rectangular lattice. This problem arises in several models in statistical physics, including...
Tiling a Polygon with Rectangles (1992)
We study the problem of tiling a simple polygon of surface n with rectangles of given types (tiles). We present a linear time algorithm for deciding if a polygon can be tiled with 1 \Theta m and k...
Louchard, Guy, Kenyon, Claire, Schott, René
The purpose of this paper is to analyze the maxima properties (value and position) of some data structures. Our theorems concern the distribution of the random variables. Previously known results...
Louchard, Guy, Kenyon, Claire, Schott, René
The purpose of this paper is to analyze the maxima properties (value and position) of some data structures. Our theorems concern the distribution of the random variables. Previously known results...
Louchard, Guy, Kenyon, Claire, Schott, René
The purpose of this paper is to analyze the maxima properties (value and position) of some data structures. Our theorems concern the distribution of the random variables. Previously known results...
Fast algorithms for bin packing (1974)
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
In this paper we present a theoretical analysis of the online Sum-of-Squares algorithm (SS) for bin packing along with several new variants. SS is applicable to any instance of bin packing in which...
Fast algorithms for bin packing (1974)
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
In this paper we present a theoretical analysis of the on-line Sum-of-Squares algorithm (SS) for bin packing along with several new variants. SS is applicable to any instance of bin packing in which...
A Randomized Approximation Scheme for Metric MAX-CUT
W. Fernandez De La Vega, Universite Paris Sud, Claire Kenyon
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...