Arrow Research search

Author name cluster

Richard M. Karp

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.

44 papers
2 author rows

Possible papers

44

SODA Conference 2011 Conference Paper

Algorithms for Implicit Hitting Set Problems

  • Karthekeyan Chandrasekaran
  • Richard M. Karp
  • Erick Moreno-Centeno
  • Santosh S. Vempala

A hitting set for a collection of sets is a set that has a nonempty intersection with each set in the collection; the hitting set problem is to find a hitting set of minimum cardinality. Motivated by instances of the hitting set problem where the number of sets to be hit is large, we introduce the notion of implicit hitting set problems. In an implicit hitting set problem the collection of sets to be hit is typically too large to list explicitly; instead, an oracle is provided which, given a set H, either determines that H is a hitting set or returns a set that H does not hit. We show a number of examples of classic implicit hitting set problems, and give a generic algorithm for solving such problems optimally. The main contribution of this paper is to show that this framework is valuable in developing approximation algorithms. We illustrate this methodology by presenting a simple on-line algorithm for the minimum feedback vertex set problem on random graphs. In particular our algorithm gives a feedback vertex set of size n –(1/ p ) log np (1 − o (1)) with probability at least 3/4 for the random graph G n, p (the smallest feedback vertex set is of size n − (2/ p ) log np (1 + o (1))). We also consider a planted model for the feedback vertex set in directed random graphs. Here we show that a hitting set for a polynomial-sized subset of cycles is a hitting set for the planted random graph and this allows us to exactly recover the planted feedback vertex set.

Details

SODA Conference 2009 Conference Paper

Sorting and selection in posets

  • Constantinos Daskalakis
  • Richard M. Karp
  • Elchanan Mossel
  • Samantha J. Riesenfeld
  • Elad Verbin

Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study these problems in the context of partially ordered sets, in which some pairs of objects are incomparable. This generalization is interesting from a combinatorial perspective, and it has immediate applications in ranking scenarios where there is no underlying linear ordering, e. g. , conference submissions. It also has applications in reconstructing certain types of networks, including biological networks. Our results represent significant progress over previous results from two decades ago by Faigle and Turán. In particular, we present the first algorithm that sorts a width- w poset of size n with optimal query complexity O ( n ( w + log n )). We also describe a variant of Mergesort with query complexity and total complexity; an algorithm with the same query complexity was given by Faigle and Turán, but no efficient implementation of that algorithm is known. Both our sorting algorithms can be applied with negligible overhead to the more general problem of reconstructing transitive relations. We also consider two related problems: finding the minimal elements, and its generalization to finding the bottom k “levels”, called the k-selection problem. We give efficient deterministic and randomized algorithms for finding the minimal elements with O ( wn ) query and total complexity. We provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k -selection problem. Finally, we present efficient algorithms for computing a linear extension of a poset and computing the heights of all elements.

Details

TCS Journal 2005 Journal Article

The minimum-entropy set cover problem

  • Eran Halperin
  • Richard M. Karp

We consider the minimum entropy principle for learning data generated by a random source and observed with random noise. In our setting we have a sequence of observations of objects drawn uniformly at random from a population. Each object in the population belongs to one class. We perform an observation for each object which determines that it belongs to one of a given set of classes. Given these observations, we are interested in assigning the most likely class to each of the objects. This scenario is a very natural one that appears in many real life situations. We show that under reasonable assumptions finding the most likely assignment is equivalent to the following variant of the set cover problem. Given a universe U and a collection S = ( S 1, …, S t ) of subsets of U, we wish to find an assignment f: U → S such that u ∈ f ( u ) and the entropy of the distribution defined by the values | f - 1 ( S i ) | is minimized. We show that this problem is NP-hard and that the greedy algorithm for set cover s with an additive constant error with respect to the optimal cover. This sheds a new light on the behavior of the greedy set cover algorithm. We further enhance the greedy algorithm and show that the problem admits a polynomial time approximation scheme (PTAS). Finally, we demonstrate how this model and the greedy algorithm can be useful in real life scenarios, and in particular, in problems arising naturally in computational biology.

Details DOI

STOC Conference 2003 Conference Paper

A stochastic process on the hypercube with applications to peer-to-peer networks

  • Micah Adler
  • Eran Halperin
  • Richard M. Karp
  • Vijay V. Vazirani

Consider the following stochastic process executed on a graph G=(V,E) whose nodes are initially uncovered. In each step, pick a node at random and if it is uncovered, cover it. Otherwise, if it has an uncovered neighbor, cover a random uncovered neighbor. Else, do nothing. This can be viewed as a structured coupon collector process. We show that for a large family of graphs, O(n) steps suffice to cover all nodes of the graph with high probability, where n is the number of vertices. Among these graphs are d -regular graphs with d =Ω(log n log log n) , random d -regular graphs with d =Ω(log n) and the k -dimensional hypercube where n=2 k .This process arises naturally in answering a question on load balancing in peer-to-peer networks. We consider a distributed hash table in which keys are partitioned across a set of processors, and we assume that the number of processors grows dynamically, starting with a single processor. If at some stage there are n processors, the number of queries required to find a key is log 2 n+O(1) , the number of pointers maintained by each processor is log 2 n+O(1) , and moreover the worst ratio between the loads of processors is O(1) , with high probability. To the best of our knowledge, this is the first analysis of a distributed hash table that achieves asymptotically optimal load balance, while still requiring only O(log n) pointers per processor and O(log n) queries for locating a key; previous methods required Ω(log 2 n) pointers per processor and Ω(log n) queries for locating a key.

Details

FOCS Conference 2000 Conference Paper

Optimization Problems in Congestion Control

  • Richard M. Karp
  • Elias Koutsoupias
  • Christos H. Papadimitriou
  • Scott Shenker

One of the crucial elements in the Internet's success is its ability to adequately control congestion. The paper defines and solves several optimization problems related to Internet congestion control, as a step toward understanding the virtues of the TCP congestion control algorithm currently used and comparing it with alternative algorithms. We focus on regulating the rate of a single unicast flow when the bandwidth available to it is unknown and may change over time. We determine near-optimal policies when the available bandwidth is unchanging, and near-optimal competitive policies when the available bandwidth is changing in a restricted manner under the control of an adversary.

Details

FOCS Conference 2000 Conference Paper

Randomized Rumor Spreading

  • Richard M. Karp
  • Christian Schindelhauer
  • Scott Shenker
  • Berthold Vöcking

Investigates the class of epidemic algorithms that are commonly used for the lazy transmission of updates to distributed copies of a database. These algorithms use a simple randomized communication mechanism to ensure robustness. Suppose n players communicate in parallel rounds in each of which every player calls a randomly selected communication partner. In every round, players can generate rumors (updates) that are to be distributed among all players. Whenever communication is established between two players, each one must decide which of the rumors to transmit. The major problem is that players might not know which rumors their partners have already received. For example, a standard algorithm forwarding each rumor form the calling to the called players for /spl Theta/(ln n) rounds needs to transmit the rumor /spl Theta/(n ln n) times in order to ensure that every player finally receives the rumor with high probability. We investigate whether such a large communication overhead is inherent to epidemic algorithms. On the positive side, we show that the communication overhead can be reduced significantly. We give an algorithm using only O(n ln ln n) transmissions and O(ln n) rounds. In addition, we prove the robustness of this algorithm. On the negative side, we show that any address-oblivious algorithm needs to send /spl Omega/(n ln ln n) messages for each rumor, regardless of the number of rounds. Furthermore, we give a general lower bound showing that time and communication optimality cannot be achieved simultaneously using random phone calls, i. e. every algorithm that distributes a rumor in O(ln n) rounds needs /spl omega/(n) transmissions.

Details

FOCS Conference 1996 Conference Paper

Efficient Information Gathering on the Internet (extended abstract)

  • Oren Etzioni
  • Steve Hanks
  • Tao Jiang 0001
  • Richard M. Karp
  • Omid Madani
  • Orli Waarts

The Internet offers unprecedented access to information. At present most of this information is free, but information providers ore likely to start charging for their services in the near future. With that in mind this paper introduces the following information access problem: given a collection of n information sources, each of which has a known time delay, dollar cost and probability of providing the needed information, find an optimal schedule for querying the information sources. We study several variants of the problem which differ in the definition of an optimal schedule. We first consider a cost model in which the problem is to minimize the expected total cost (monetary and time) of the schedule, subject to the requirement that the schedule may terminate only when the query has been answered or all sources have been queried unsuccessfully. We develop an approximation algorithm for this problem and for an extension of the problem in which more than a single item of information is being sought. We then develop approximation algorithms for a reward model in which a constant reward is earned if the information is successfully provided, and we seek the schedule with the maximum expected difference between the reward and a measure of cost. The monetary and time costs may either appear in the cost measure or be constrained not to exceed a fixed upper bound; these options give rise to four different variants of the reward model.

Details

FOCS Conference 1995 Conference Paper

An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract)

  • Paul Dagum
  • Richard M. Karp
  • Michael Luby
  • Sheldon M. Ross

A typical approach to estimate an unknown quantity /spl mu/ is to design an experiment that produces a random variable Z distributed in [O, 1] with E[Z]=/spl mu/, run this experiment independently a number of times and use the average of the outcomes as the estimate. In this paper, we consider the case when no a priori information about Z is known except that is distributed in [0, 1]. We describe an approximation algorithm AA which, given /spl epsiv/ and /spl delta/, when running independent experiments with respect to any Z, produces an estimate that is within a factor 1+/spl epsiv/ of /spl mu/ with probability at least 1-/spl delta/. We prove that the expected number of experiments ran by AA (which depends on Z) is optimal to within a constant factor for every Z.

Details

MFCS Conference 1995 Invited Paper

Scheduling Parallel Communication: The h-relation Problem

  • Micah Adler
  • John W. Byers
  • Richard M. Karp

Abstract This paper is concerned with the efficient scheduling and routing of point-to-point messages in a distributed computing system with n processors. We examine the h -relation problem, a routing problem where each processor has at most h messages to send and at most h messages to receive. Communication is carried out in rounds. Direct communication is possible from any processor to any other, and in each round a processor can send one message and receive one message. The off-line version of the problem arises when every processor knows the source and destination of every message. In this case the messages can be routed in at most h rounds. More interesting, and more typical, is the on-line version, in which each processor has knowledge only of h and of the destinations of those messages which it must send. The on-line version of the problem is the focus of this paper. The difficulty of the h -relation problem stems from message conflicts, in which two or more messages are sent to the same processor in a given round, but at most one can be received. The problem has been well studied in the OCPC optical network model, but not for other contemporary network architectures which resolve message conflicts using other techniques. In this paper, we study the h -relation problem under alternative models of conflict resolution, most notably a FIFO queue discipline motivated by wormhole routing and an arbitrary write discipline motivated by packet-switching networks. In each model the problem can be solved by a randomized algorithm in an expected number of rounds of the form ch +o( h )+log Θ (1) n, and we focus on obtaining the smallest possible asymptotic constant factor c. We first present a lower bound, proving that a constant factor of 1 is not achievable in general. We then present a randomized algorithm for each discipline and show that they achieve small constant factors.

Details

FOCS Conference 1995 Conference Paper

The Bit Vector Intersection Problem (Preliminary Version)

  • Richard M. Karp
  • Orli Waarts
  • Geoffrey Zweig

This paper introduces the bit vector intersection problem: given a large collection of sparse bit vectors, find all the pairs with at least t ones in common for a given input parameter t. The assumption is that the number of ones common to any two vectors is significantly less than t, except for an unknown set of O(n) pairs. This problem has important applications in DNA physical mapping, clustering, and searching for approximate dictionary matches. We present two randomized algorithms that solve this problem with high probability and in sub-quadratic expected time. One of these algorithms is based on a recursive tree-searching procedure, and the other on hashing. We analyze the tree scheme in terms of branching processes, while our analysis of the hashing scheme is based on Markov chains. Since both algorithms have similar asymptotic performance, we also examine experimentally their relative merits in practical situations. We conclude by showing that a fundamental problem arising in the Human Genome Project is captured by the bit vector intersection problem described above and hence can be solved by our algorithms.

Details

FOCS Conference 1992 Conference Paper

Competitive Analysis of Financial Games

  • Ran El-Yaniv
  • Amos Fiat
  • Richard M. Karp
  • G. Turpin

In the unidirectional conversion problem an on-line player is given the task of converting dollars to yen over some period of time. Each day, a new exchange rate is announced and the player must decide how many dollars to convert. His goal is to minimize the competitive ratio. defined as sup/sub E/ (P/sub OPT/(E)/P/sub X/E) where E ranges over exchange rate sequences. P/sub OPT/(E) is the number of yen obtained by an optimal off-line algorithm, and Px(E) is the number of yen obtained by the on-line algorithm X. The authors also consider a continuous version of the problem. in which the exchange rate varies over a continuous time interval. The on-line line players a priori information about the fluctuation of exchange rates distinguishes different variants of the problem. For three variants they show that a simple threat-based strategy is optimal for the on-line player and determine its competitive ratio. They also derive and analyze an optimal policy for the on-line player when he knows the probability distribution of the maximum value that the exchange rate will reach. Finally, they consider a bidirectional conversion problem, which the player may trade dollars for yen or yen for dollars. >

Details

STOC Conference 1988 Conference Paper

A Randomized Parallel Branch-and-Bound Procedure

  • Richard M. Karp
  • Yanjun Zhang

We present a universal randomized method called Local Best-First Search for parallelizing sequential branch-and-bound algorithms. The method executes on a message-passing multiprocessor system, and requires no global data structures or complex communication protocols. We show that, uniformly on all instances, the execution time of the method is unlikely to exceed a certain inherent lower bound by more than a constant factor.

Details

FOCS Conference 1986 Conference Paper

FFD Bin Packing for Item Sizes with Distributions on [0, 1/2]

  • Sally Floyd
  • Richard M. Karp

We study the expected behavior of the FFD binpacking algorithm applied to items whose sizes are distributed in accordance with a Poisson process with rate N on the interval [0, 1/2] of item sizes. By viewing the algorithm as a succession of queueing processes we show that the expected wasted space for FFD bin-packing is bounded above by 9. 4 bins, independent of N. We extend this upper bound to a FFD bin-packing of items in accordance with a non-homogeneous Poisson process with a nonincreasing intensity function λ(t) on [0, 1/2].

Details

FOCS Conference 1985 Conference Paper

The Complexity of Parallel Computation on Matroids

  • Richard M. Karp
  • Eli Upfal
  • Avi Wigderson

In [KUW1] we have proposed the setting of independence systems to study the relation between the computational complexity of search and decision problems. The universal problem that captures this relation, which we termed the S-search problem, is: "Given an oracle for the input system, find a maximal independent subset in it". Many interesting and important search problems can be described by a special class of independence systems, called matroids. This paper is devoted to die complexity of the S- search problem for matroids. Our main result is a lower bound on any probabilistic algorithm for the S-search problem that acquires information about the input system by interrogating an independence oracle. We prove that the expected time of any such probabilistic algorithm that uses a sub-exponential number of processors is Ω(n1/3-ε). This is one of the first nontrivial, super-logarithmic lower bounds on a randomized parallel computation. It implies that in our model of computation Random-NC is strictly contained in P. Another consequence of the lower bound is that the O(√n) time probabilistic upper bound for arbitrary independence systems, presented in [KUW1], is close to optimal and cannot be significantly improved, even for matroids. However, fills O(√n) upper bound can be improved in a different sense for matroids -it can be made deterministic, still with polynomially many processors. Finally, we show that the lower bound can be beaten for the special case of graphic matroids. Here, the S-search problem is simply to find a spanning forest of a graph, when the algorithm cannot see the graph, but can only ask whether subsets of edges are forests or not. We give an O(logn) time deterministic parallel algoritlun that uses nO(logn) processors. From the upper bounds on parallel time above we deduce similar bounds (up to a poly-log factor) on thc sequential space required by a deterministic Turing machine with an independence oracle to solve the S-search problem.

Details

STOC Conference 1984 Conference Paper

A Fast Parallel Algorithm for the Maximal Independent Set Problem

  • Richard M. Karp
  • Avi Wigderson

A parallel algorithm is presented which accepts as input a graph G and produces a maximal independent set of vertices in G. On a P-RAM without the concurrent write or concurrent read features, the algorithm executes in O((log n) 4 ) time and uses O((n/log n) 3 ) processors, where n is the number of vertices in G. The algorithm has several novel features that may find other applications. These include the use of balanced incomplete block designs to replace random sampling by deterministic sampling, and the use of a “dynamic pigeonhole principle” that generalizes the conventional pigeonhole principle.

Details

FOCS Conference 1983 Conference Paper

Global Wire Routing in Two-Dimensional Arrays (Extended Abstract)

  • Richard M. Karp
  • Frank Thomson Leighton
  • Ronald L. Rivest
  • Clark D. Thompson
  • Umesh V. Vazirani
  • Vijay V. Vazirani

We examine the problem of routing wires on a VLSI chip, where the pins to be connected are arranged in a regular rectangular array. We obtain tight bounds for the worst-case "channel-width" needed to route an n × n array, and develop provably good heuristics for the general case. An interesting "rounding algorithm" for obtaining integral approximations to solutions of linear equations is used to show the near-optimality of single-turn routings in the worst-case.

Details

AIJ Journal 1983 Journal Article

Searching for an optimal path in a tree with random costs

  • Richard M. Karp
  • Judea Pearl

We consider the problem of finding an optimal path leading from the root of a tree to any of its leaves. The tree is known to be uniform, binary, and of height N, and each branch independently may have a cost of 1 or 0 with probability p and 1−p, respectively. We show that for p<1/2 the uniform cost algorithm can find a cheapest path in linear expected time. By contrast, when p>1/2, every algorithm which guarantees finding an exact cheapest path, or even a path within a fixed cost ratio of the cheapest, must run in exponential average time. If, however, we are willing to accept a near optimal solution almost always, then a pruning algorithm exists which finds such a solution in linear expected time. The algorithm employs a depth-first strategy which stops at regular intervals to appraise its progress and, if the progress does not meet a criterion based on domain-specific knowledge, the current node is irrevocably pruned.

Details DOI

FOCS Conference 1982 Conference Paper

An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem

  • Narendra Karmarkar
  • Richard M. Karp

We present several polynomial-time approximation algorithms for the one-dimensional bin-packing problem. using a subroutine to solve a certain linear programming relaxation of the problem. Our main results are as follows: There is a polynomial-time algorithm A such that A(I) ≤ OPT(I) + O(log2 OPT(I)). There is a polynomial-time algorithm A such that, if m(I) denotes the number of distinct sizes of pieces occurring in instance I, then A(I) ≤ OPT(I) + O(log2 m(I)). There is an approximation scheme which accepts as input an instance I and a positive real number ε, and produces as output a packing using as most (1 + ε) OPT(I) + O(ε-2) bins. Its execution time is O(ε-c n log n), where c is a constant. These are the best asymptotic performance bounds that have been achieved to date for polynomial-time bin-packing. Each of our algorithms makes at most O(log n) calls on the LP relaxation subroutine and takes at most O(n log n) time for other operations. The LP relaxation of bin packing was solved efficiently in practice by Gilmore and Gomory. We prove its membership in P, despite the fact that it has an astronomically large number of variables.

Details

FOCS Conference 1980 Conference Paper

On Linear Characterizations of Combinatorial Optimization Problems

  • Richard M. Karp
  • Christos H. Papadimitriou

We show that there can be no computationally tractable description by linear inequalities of the polyhedron associated with any NP-complete combinatorial optimization problem unless NP = co-NP -- a very unlikely event. We also apply the ellipsoid method for linear programming to show that a combinatorial optimization problem is solvable in polynomial time if and only if it admits a small generator of violated inequalities.

Details

STOC Conference 1980 Conference Paper

Some Connections between Nonuniform and Uniform Complexity Classes

  • Richard M. Karp
  • Richard J. Lipton

It is well known that every set in P has small circuits [13]. Adleman [1] has recently proved the stronger result that every set accepted in polynomial time by a randomized Turing machine has small circuits. Both these results are typical of the known relationships between uniform and nonuniform complexity bounds. They obtain a nonuniform upper bound as a consequence of a uniform upper bound.

Details

STOC Conference 1972 Conference Paper

Rapid Identification of Repeated Patterns in Strings, Trees and Arrays

  • Richard M. Karp
  • Raymond E. Miller
  • Arnold L. Rosenberg

In this paper we look at a number of matching problems and devise general techniques for attacking such problems. In particular, we describe a strategy for constructing efficient algorithms for solving two types of matching problems. We use this strategy to develop explicit algorithms for these two problems applied to strings (where the patterns are substrings) and arrays (where the patterns are subarrays or blocks). We also develop algorithms for these and related problems for trees, where the patterns are subtrees. Certain special cases of these algorithms are also discussed. Although we do not claim that these algorithms are optimal, we analyze each algorithm to estimate its computational cost. This provides some basis for choosing which algorithm is most desirable in any given situation.

Details
v2026.09.13