Online multicast with egalitarian cost sharing (2009)
Moses Charikar, Joseph (seffi Naor, Howard Karloff
We consider a multicast game played by a set of selfish noncooperative players (i.e., nodes) on a rooted undirected graph. Players arrive one by one and each connects to the root by greedily choosing...
ABSTRACT Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search (2009)
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li
Similarity indices for high-dimensional data are very desirable for building content-based search systems for featurerich data such as audio, images, videos, and other sensor data. Recently, locality...
Abstract A Tight Threshold for Metric Ramsey Phenomena (2009)
In this paper, we examine the metric Ramsey problem for the normed spaces ℓp: given some 1 ≤ p ≤ ∞, α ≥ 1 and an integer n, we ask for the largest m such that every n-point metric space...
Moses Charikar, Surajit Chaudhuri Y
We consider the problem of estimating the number of distinct values in a column of a table. For large tables without an index on the column, random sampling appears to be the only scalable approach...
Amit Agarwal, Konstantin Makarychev, Moses Charikar, Yury Makarychev
We give O ( √ log n)-approximation algorithms for the Min
Amit Agarwal, Konstantin Makarychev, Moses Charikar, Yury Makarychev
We give O ( √ log n)-approximation algorithms for the Min
Nir Ailon, Moses Charikar, Alantha Newman
We address optimization problems in which we are given contradictory pieces of input information and the goal is to find a globally consistent solution that minimizes the number of disagreements with...
Abstract Maximizing quadratic programs: extending Grothendieck’s inequality (2008)
This paper considers the following type of quadratic programming problem. Given an arbitrary matrix A, whose diagonal elements are zero, find x ∈ {−1, 1} n such that x T Ax is maximized. Our...
Yair Bartal, Moses Charikar, Danny Raz
ABSTRACT The min-sum k-clustering problem in a metric space is to find a partition of the space into k clusters as to minimize the total sum of distances between pairs of points assigned to the same...
Yair Bartal, Moses Charikar, Danny Raz
ABSTRACT The min-sum k-clustering problem in a metric space is to find a partition of the space into k clusters as to minimize the total sum of distances between pairs of points assigned to the same...
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li
Building content-based search tools for feature-rich data has been a challenging problem because feature-rich data such as audio recordings, digital images, and sensor data are inherently noisy and...
Amit Agarwal, Noga Alon, Moses Charikar
We present improved approximation algorithms for directed multicut and directed sparsest cut. The current best known approximation ratio for these problems is O(n 1/2). We obtain an...
Piotr Berman, Moses Charikar, Marek Karpinski
We consider the problem of schedulingpermanent jobs on related machinesin an on-line fashion. We design a new algorithm that achievesthe competitive ratio of ¡£¢¥ ¤ ¦¨§�©� �...
Nir Ailon, Moses Charikar, Alantha Newman
We address optimization problems in which we are given contradictory pieces of input information and the goal is to find a globally consistent solution that minimizes the number of disagreements with...
Abstract Incremental Clustering and Dynamic Information Retrieval (2008)
Moses Charikar, Chandra Chekuri
Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space. We propose a model called...
ABSTRACT Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search (2008)
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li
Similarity indices for high-dimensional data are very desirable for building content-based search systems for featurerich data such as audio, images, videos, and other sensor data. Recently, locality...
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li
Ferret is a toolkit for building content-based similarity search systems for feature-rich data types such as audio, video, and digital photos. The key component of this toolkit is a content-based...
9. Vis: A Unified Graphical User Interface For DCPI (2008)
Compiled James Mason, Nawaaz Ahmed, Moses Charikar, Neal Glew, Rajeev Joshi, Thomas Kistler, ...
This document features informal reports by interns who spent the summer of 1997 working with researchers at
Abstract Incremental Clustering and Dynamic Information Retrieval (2008)
Moses Charikar, Chandra Chekurit, Tomas Feder, Rajeev Motwani
Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space. We propose a model-c~led...
Moses Charikar, Konstantin Makarychev, Yury Makarychev
In this note we present an approximation algorithm for MAX 2SAT that given a (1 − ε) satisfiable instance finds an assignment of variables satisfying a 1 − O ( √ ε) fraction of all...
On the Advantage over Random for Maximum Acyclic Subgraph (2008)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
In this paper we present a new approximation algorithm for the MAX ACYCLIC SUBGRAPH problem. Given an instance where the maximum acyclic subgraph contains 1/2+δ fraction of all edges, our algorithm...
Abstract Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems (2008)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
In this paper we present approximation algorithms for the maximum constraint satisfaction problem with k variables in each constraint (MAX k-CSP). Given a (1 − ε) satisfiable 2CSP our first...
Abstract Directed Metrics and Directed Graph Partitioning Problems (2008)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
The theory of embeddings of finite metrics has provided a powerful toolkit for graph partitioning problems in undirected graphs. The connection comes from the fact that the integrality gaps of...
problems MINIMUM LINEAR ARRANGEMENT, (2008)
Moses Charikar, Mohammadtaghi Hajiaghayi, Satish Rao
We design approximation algorithms for the vertex ordering
Abstract Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models (2008)
Moses Charikar, Manoj Prabhakaran, Eric Lehman
We consider the problem of finding the smallest context-free grammar that generates exactly one given string of length n. The size of this grammar is of theoretical interest as an efficiently...
Abstract Algorithms for Facility Location Problems with Outliers (Extended Abstract) (2008)
Moses Charikar, Samir Khuller, David M. Mount, Giri Narasimhan
Facility location problems are traditionally investigated with the assumption that all the clients are to be provided service. A significant shortcoming of this formulation is that a few very distant...
On-line Load Balancing for Related Machines 1 (Revised Version) (2008)
Piotr Berman, Moses Charikar, Marek Karpinskiy
We consider the problem of scheduling permanent jobs on related machinesin an on-line fashion. We design a new algorithm that achievesthe competitive ratio for the deterministic version,...
Query Strategies for Priced Information (Extended Abstract) (2007)
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, Amit Sahai
We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying...
Moses Charikar, Venkatesan Guruswami, Sridhar Rajagopalan, Amit Sahai
Motivated by frequently recurring themes in information retrieval and related disciplines, we define a genre of problems called combinatorial feature selection problems. Given a set S of...
Yair Bartal, Moses Charikar, Piotr Indyk
This paper is concerned with the page migration (or file migration) problem [BS89] as part of a large class of on-line problems. The page migration problem deals with the management of pages residing...
Moses Charikar, Sudipto Guha, Eva Tardos, David B. Shmoys
A constant-factor approximation algorithm
A Constant-Factor Approximation Algorithm for the (2007)
Median Problem Extended, Moses Charikar, Sudipto Guha, Eva Tardos, David B. Shmoys
) Moses Charikar Sudipto Guha y Eva Tardos z David B. Shmoys x Abstract We present the rst constant-factor approximation algorithm for the metric k-median problem. The k-median problem is one of the...
Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha
Most optimization problems on an undirected graph reduce in complexity when restricted to instances on a tree. A recent result [3] for probabilistically approximating graph metrics by trees such that...
Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Cisco Systems, Manoj Prabhakaran, ...
We consider the problem of nding the smallest context-free grammar that generates exactly one given string of length n. The size of this grammar is of theoretical interest as an eciently computable...
S n is min-wise independent if for any set X (2007)
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher
We define and study the notion of min-wise independent families of permutations. We say that
Moses Charikar, Ronald Fagin, Venkatesan Gu-uswami, Jon Kleinberg, Prabhakar Raghavan, Amit Sahai
oo22-oooOl02 $35.00
We give the first non-trivial approximation algorithm for the Capacitated Dial-a-Ride problem: given a collection of objects located at points in a metric space, a specified destination point for...
Abstract. Given n identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them eciently to n target locations (slots) with a vehicle that can carry at...
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, Amit Sahai
We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying...
Moses Charikar, Manoj Prabhakaran, Eric Lehman, Ding Liu, Amit Sahai, Rina Panigrahy
We consider the problem of finding the smallest contextfree grammar that generates exactly one given string of length n. The size of this grammar is of theoretical interest as an efficiently...
Local global tradeoffs in metric embeddings (2007)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Suppose that every k points in a n point metric space X are D-distortion embeddable into ℓ1. We give upper and lower bounds on the distortion required to embed the entire space X into ℓ1. This is...
Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems (2007)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
In this paper we present approximation algorithms for the maximum constraint satisfaction problem with k variables in each constraint (MAX k-CSP). Given a (1 − ε) satisfiable 2CSP our first...
Local global tradeoffs in metric embeddings (2007)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Suppose that every k points in a n point metric space X are D-distortion embeddable into ℓ1. We give upper and lower bounds on the distortion required to embed the entire space X into ℓ1. This is...
Filtering image spam with near-duplicate detection (2007)
Zhe Wang, William Josephson, Qin Lv, Moses Charikar, Kai Li
A new trend in email spam is the emergence of image spam. Although current anti-spam technologies are quite successful in filtering text-based spam emails, the new image spams are substantially more...
On the Integrality Ratio for the Asymmetric Traveling Salesman Problem (2006)
Moses Charikar, Michel X. Goemans, Howard Karloff
informs ® doi 10.1287/moor.1060.0191
Approximation Algorithm for the Max k-CSP Problem (2006)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
We present a ck 2k approximation algorithm for the Max k-CSP problem (where c> 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which has an...
Near-optimal algorithms for Unique Games (2006)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Unique games are constraint satisfaction problems that can be viewed as a generalization of Max-Cut to a larger domain size. The Unique Games Conjecture states that it is hard to distinguish between...
On the Integrality Ratio for the Asymmetric Traveling Salesman Problem (2006)
Moses Charikar, Michel X. Goemans, Howard Karloff
We improve the lower bound on the integrality ratio of the Held-Karp bound for asymmetric TSP with triangle inequality from 4/3 to 2. Key words: Asymmetric traveling salesman problem; Held-Karp...
Embedding the ulam metric into ℓ1 (2006)
Moses Charikar, C Moses Charikar, Robert Krauthgamer, Robert Krauthgamer, M. Charikar, R. Krauthgamer
Abstract: Edit distance is a fundamental measure of distance between strings, the extensive study of which has recently focused on computational problems such as nearest neighbor search, sketching...
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li
Building content-based search tools for feature-rich data has been a challenging problem because feature-rich data such as audio recordings, digital images, and sensor data are inherently noisy and...
Near-optimal algorithms for Unique Games (2006)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Unique games are constraint satisfaction problems that can be viewed as a generalization of Max-Cut to a larger domain size. The Unique Games Conjecture states that it is hard to distinguish between...
On non-uniform multicommodity buy-at-bulk network design (2005)
Moses Charikar, Adriana Karagiozova
We study the multicommodity buy-at-bulk network design problem in which we seek to design a network that satisfies the demands between terminals from a given set of sourcesink pairs. The key...
Fitting tree metrics: Hierarchical clustering and phylogeny (2005)
Given dissimilarity data on pairs of objects in a set, we study the problem of fitting a tree metric to this data so as to minimize additive error (i.e. some measure of the difference between the...
Sampling bounds for stochastic optimization (2005)
Moses Charikar, Ra Chekuri, Martin Pál
Abstract. A large class of stochastic optimization problems can be modeled as minimizing an objective function f that depends on a choice of a vector x ∈ X, as well as on a random external...
On the impossibility of dimension reduction in ℓ1 (2003)
The Johnson-Lindenstrauss Lemma shows that any n points in Euclidean space (with distances measured by the ℓ2 norm) may be mapped down to O((log n)/ε 2) dimensions such that no pairwise distance...
On the impossibility of dimension reduction in `1 (2003)
The Johnson-Lindenstrauss Lemma shows that any n points in Euclidean space (with distances measured by the # 2 norm) may be mapped down to O((log n)/# 2) dimensions such that no pairwise distance is...
Better Streaming Algorithms for Clustering Problems (2003)
Moses Charikar, Liadan O'Callaghan, Rina Panigrahy
We study cluster ng pr blems in the str aming model, wher e the goal is to cluster a set of points by making one pass (or a few passes) over the data using a small amount of storSD space.Our mainr...
Better streaming algorithms for clustering problems (2003)
We study clustering problems in the streaming model, where the goal is to cluster a set of points by making one pass (or a few passes) over the data using a small amount of storage space. Our main...
Moses Charikar, Piotr Indyk, Rina Panigrahy
- N * 2O(m log 2 mpc / log N) space, and O(N/2c) time, for any c- Nmc space and O(mN/c) query time, for any c < = N We extend these results to the more general problem of orthogonal range...
On semidefinite programming relaxations for graph coloring and vertex cover (2002)
Abstract We investigate the power of a strengthened SDP relaxation for graph coloring whose value is equal to a variant of the Lov'asz #-function. We show families of graphs where the value of...
Finding frequent items in data streams (2002)
Moses Charikar, Kevin Chen, Martin Farach-colton
Abstract. We present a 1-pass algorithm for estimating the most frequent items in a data stream using very limited storage space. Our method relies on a novel data structure called a count sketch,...
Finding frequent items in data streams (2002)
Moses Charikar, Kevin Chen, Martin Farach-colton
Abstract. We present a 1-pass algorithm for estimating the most frequent items in a data stream using very limited storage space. Our method relies on a novel data structure called a count sketch,...
Dimension Reduction in the l1 norm (2002)
The Johnson-Lindenstrauss Lemma shows that any set of n points in Euclidean space can be mapped linearly down to ) dimensions such that all pairwise distances are distorted by at most 1 + #. We study...
Algorithms for facility location problems with outliers (2001)
Moses Charikar, Samir Khuller, David M. Mount, Giri Narasimhan
Facility location problems are traditionally investigated with the assumption that all the clients are to be provided service. A significant shortcoming of this formulation is that a few very distant...
Algorithms for facility location problems with outliers (2001)
Moses Charikar, Samir Khuller, David M. Mount, Giri Narasimhan
Facility location problems are traditionally investigated with the assumption that all the clients are to be provided service. A significant shortcoming of this formulation is that a few very distant...
Query Strategies for Priced Information (Extended Abstract) (2000)
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, Amit Sahai
We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying...
Resource Optimization in QoS Multicast Routing of Real-Time Multimedia (2000)
Moses Charikar, Joseph (Seffi) Naor, Baruch Schieber
We consider a network design problem, where applications require various levels of Quality-of-Service (QoS) while connections have limited performance. Suppose that a source needs to send a message...
Query Strategies for Priced Information (2000)
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, Amit Sahai
We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying...
A constant-factor approximation algorithm for the k-median problem (1999)
Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys
We present the first constant-factor approximation algorithm for the metric k-median problem. The k-median problem is one of the most well-studied clustering problems, i.e., those problems in which...
Minimizing wirelength in zero and bounded skew clock trees (1999)
Moses Charikar, Jon Kleinberg, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins
An important problem in VLSI design is distributing a clock signal to synchronous elements in a VLSI circuit so that the signal arrives at all elements simultaneously. The signal is distributed by...
On targeting Markov segments (1999)
Moses Charikar, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
Consider two user populations, of which one is targeted and the other is not. Users in the targeted population follow a Markov chain on a space of n states. The untargeted population follows another...
Minimizing Wirelength in Zero and Bounded Skew Clock Trees (1999)
Moses Charikar, Jon Kleinberg, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins
An important problem in VLSI design is distributing a clock signal to synchronouselements in a VLSI circuit such that the clock arrives at all elements simultaneously. The clock signal is distributed...
Improved Combinatorial Algorithms for the Facility Location and k-Median Problems (1999)
We present improved combinatorial approximation algorithms for the uncapacitated facility location and k-median problems. Two central ideas in most of our results are cost scaling and greedy...
On targeting Markov segments (1999)
Moses Charikar, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
Consider two user populations, of which one is targeted and the other is not. Users in the targeted population follow a Markov chain P on a space of n states. The untargeted population follows Q,...
Minimizing Wirelength in Zero and Bounded Skew Clock Trees (1999)
Moses Charikar, Jon Kleinberg, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins
An important problem in VLSI design is distributing a clock signal to synchronous elements in a VLSI circuit so that the signal arrives at all elements simultaneously. The signal is distributed by...
A constant-factor approximation algorithm for the k-median problem (Extended Abstract) (1999)
Moses Charikar, Sudipto Guha, Éva Tardos, Eva Tardos, David B. Shmoys
) Moses Charikar Sudipto Guha y Eva Tardos z David B. Shmoys x Abstract We present the rst constant-factor approximation algorithm for the metric k-median problem. The k-median problem is one of the...
On targeting Markov segments (1999)
Moses Charikar, Ravi Kumaryprabhakar, Raghavanysridhar Rajagopalanyandrew Tomkinsy
Consider two user populations, of which one is targeted and the other is not. Users in the targeted population follow a Markov chain on a space ofnstates. The untargeted population follows another...
Improved combinatorial algorithms for the facility location and k-median problems (1999)
We present improved combinatorial approximation algorithms for the uncapacitated facility location problem. Two central ideas in most of our results are cost scaling and greedy improvement. We...
Min-wise Independent Permutations (1998)
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher
We define and study the notion of min-wise independent families of permutations. We say that F ⊆ Sn is min-wise independent if for any set X ⊆ [n] and any x ∈ X, when π is chosen at random in...
Delayed information and action in on-line algorithms (1998)
Susanne Albers, Moses Charikar, Michael Mitzenmacher
Most on-line analysis assumes that, at each time step, all relevant information up to that time step is available and a decision has an immediate e#ect. In many on-line problems, however, the time...
Min-wise Independent Permutations (1998)
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher
We define and study the notion of min-wise independent families of permutations. We say that F ⊆ Sn is min-wise independent if for any set X ⊆ [n] and any x ∈ X, when π is chosen at random in...
Algorithms for capacitated vehicle routing (1998)
Moses Charikar, Samir Khuller, Balaji Raghavachari
Given n identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to n target locations (slots) with a vehicle that can carry at most k...
The Finite Capacity Dial-A-Ride Problem (1998)
Moses Charikar, Balaji Raghavachari
We give the rst non-trivial approximation algorithm for the Capacitated Dial-a-Ride problem: given a collection of objects located at points in a metric space, a specied destination point for each...
Approximation Algorithms for Directed Steiner Problems (1998)
Moses Charikar, Chandra Chekuri, To-yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, ...
We give the first non-trivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in...
Approximation Algorithms for Directed Steiner Problems (1998)
Moses Charikar, Chandra Chekuri, To-yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, ...
We give the rst non-trivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in...
Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha
Most optimization problems on an undirected graph reduce in complexity when restricted to instances on a tree. A recent result [3] for probabilistically approximating graph metrics by trees such that...
Approximation Algorithms for Directed Steiner Problems (1998)
Moses Charikar Stanford, Moses Charikar, Chandra Chekuri, Zuo Dai, Ashish Goel, Sudipto Guha, ...
We give the first non-trivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in...
Approximation Algorithms for Directed Steiner Problems (1998)
Moses Charikar, Chandra Chekuri, To-yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, ...
We give the first non-trivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in...
Delayed Information and Action in On-Line Algorithms (1998)
Susanne Albers, Moses Charikar, Michael Mitzenmacher
Most on-line analysis assumes that, at each time-step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time...
Algorithms for Capacitated Vehicle Routing (1998)
Moses Charikar, Samir Khuller, Balaji Raghavachari
Given n identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to n target locations (slots) with a vehicle that can carry at most k...
A Derandomization Using Min-Wise Independent Permutations (Extended Abstract) (1998)
Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher
Min-wise independence is a recently introduced notion of limited independence, similar in spirit to pairwise independence. The later has proven essential for the derandomization of many algorithms....
The Dynamic Servers Problem (1998)
Moses Charikar, Dan Halperin, Rajeev Motwani
Introduction. We introduce the dynamic servers problem, a generalization of the k-server problem [11]. This problem is a simultaneous abstraction for problems arising in a variety of applications...
The Dynamic Servers Problem (1998)
Moses Charikar, Dan Halperin, Rajeev Motwani
We present a generalization of the k-server problem, called dynamic servers, where the number of servers is not fixed a priori; rather, the algorithm is free to increase and decrease the number of...
The Dynamic Servers Problem (1998)
Moses Charikar, Dan Halperin, Rajeev Motwani
We present a generalization of the k-server problem, called dynamic servers, where the number of servers is not fixed a priori; rather, the algorithm is free to increase and decrease the number of...
A derandomization using min-wise independent permutations (1998)
Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher
Min-wise independence is a recently introduced notion of limited independence, similar in spirit to pairwise independence. The later has proven essential for the derandomization of many algorithms....
Min-wise Independent Permutations (1998)
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher
We define and study the notion of min-wise independent families of permutations. We say that F⊆Sn is min-wise independent if for any set X ⊆ [n] and any x ∈ X, whenπ is chosen at random in F...
Delayed information and action in on-line algorithms (1998)
Susanne Albers, Moses Charikar, Michael Mitzenmacher
Most on-line analysis assumes that, at each time step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time...
: www.idealibrary.com on Min-Wise Independent Permutations (1998)
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher
We define and study the notion of min-wise independent families of permutations. We say that F Sn (the symmetric group) is min-wise independent if for any set X [n] and any x # X, when? is chosen at...
Delayed information and action in on-line algorithms (1998)
Susanne Albers, Moses Charikar, Michael Mitzenmacher
Most on-line analysis assumes that, at each time step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time...
Algorithms for Capacitated Vehicle Routing (1997)
Charikar, Moses, Khuller, Samir, Raghavachari, Balaji
Given $n$ identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to $n$ target locations (slots) with a vehicle that can carry at...
Algorithms for Capacitated Vehicle Routing (1997)
Charikar, Moses, Khuller, Samir, Raghavachari, Balaji
Given $n$ identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to $n$ target locations (slots) with a vehicle that can carry at...
Constrained TSP and Low-Power Computing (1997)
Moses Charikar, Rajeev Motwani, Prabhakar Raghavan
. In the precedence-constrainedtraveling salesmanproblem (PTSP) we are givena partial order on n nodes, each of which is labeled by one of k points in a metric space.We are to find a visit order...
Incremental Clustering and Dynamic Information Retrieval (1997)
Moses Charikar, Chandra Chekuri
Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space. We propose a model called...
On Page Migration and Other Relaxed Task Systems (1997)
Yair Bartal, Moses Charikar, Piotr Indyk
This paper is concerned with the page migration (or le migration) problem [BS89] as part of a large class of on-line problems. The page migration problem deals with the management of pages residing...
On-line Load Balancing for Related Machines (1997)
Piotr Berman, Moses Charikar, Marek Karpinski
this paper appeared in Proceedings of WADS 97, LNCS 1272, SpringerVerlag, 1997, 116-125.
On-line Load Balancing for Related Machines (1997)
Piotr Berman Moses, Moses Charikar, Marek Karpinski
We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3+ p 8 5:828 for the deterministic...
Constrained TSP and Low-Power Computing (1997)
Moses Charikar, Rajeev Motwani, Prabhakar Raghavan, Craig Silverstein
. In the precedence-constrainedtraveling salesmanproblem (PTSP) we are givena partial order on n nodes, each of which is labeled by one of k points in a metric space.We are to find a visit order...
Incremental Clustering and Dynamic Information Retrieval (1997)
Moses Charikar, Chandra Chekuri
Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space. We propose a model called...
Incremental Clustering and Dynamic Information Retrieval (1997)
Moses Charikar, Chandra Chekuri, Tomas Feder, Rajeev Motwani
Abstract. Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space. We propose a model...
A Derandomization Using Min-Wise Independent Permutations
Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher
. Min-wise independence is a recently introduced notion of limited independence, similar in spirit to pairwise independence. The later has proven essential for the derandomization of many algorithms....
Algorithms for Capacitated Vehicle Routing
Given n identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to n target locations (slots) with a vehicle that can carry at most k...