Arrow Research search

Author name cluster

Howard J. Karloff

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.

31 papers
2 author rows

Possible papers

31

SODA Conference 2010 Conference Paper

A Model of Computation for MapReduce

  • Howard J. Karloff
  • Siddharth Suri
  • Sergei Vassilvitskii

In recent years the MapReduce framework has emerged as one of the most widely used parallel computing platforms for processing data on terabyte and petabyte scales. Used daily at companies such as Yahoo! , Google, Amazon, and Facebook, and adopted more recently by several universities, it allows for easy parallelization of data intensive computations over many machines. One key feature of MapReduce that differentiates it from previous models of parallel computation is that it interleaves sequential and parallel computation. We propose a model of efficient computation using the MapReduce paradigm. Since MapReduce is designed for computations over massive data sets, our model limits the number of machines and the memory per machine to be substantially sublinear in the size of the input. On the other hand, we place very loose restrictions on the computational power of of any individual machine—our model allows each machine to perform sequential computations in time polynomial in the size of the original input. We compare MapReduce to the PRAM model of computation. We prove a simulation lemma showing that a large class of PRAM algorithms can be efficiently simulated via MapReduce. The strength of MapReduce, however, lies in the fact that it uses both sequential and parallel computation. We demonstrate how algorithms can take advantage of this fact to compute an MST of a dense graph in only two rounds, as opposed to Ω(log( n )) rounds needed in the standard PRAM model. We show how to evaluate a wide class of functions using the MapReduce framework. We conclude by applying this result to show how to compute some basic algorithmic problems such as undirected s-t connectivity in the MapReduce framework.

Details

FOCS Conference 2009 Conference Paper

Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP

  • Aaron Archer
  • MohammadHossein Bateni
  • MohammadTaghi Hajiaghayi
  • Howard J. Karloff

We study the prize-collecting versions of the Steiner tree, traveling salesman, and stroll (a. k. a. Path-TSP) problems (PCST, PCTSP, and PCS, respectively): given a graph (V, E) with costs on each edge and a penalty (a. k. a. prize) on each node, the goal is to find a tree (for PCST), cycle (for PCTSP), or stroll (for PCS) that minimizes the sum of the edge costs in the tree/cycle/stroll and the penalties of the nodes not spanned by it. In addition to being a useful theoretical tool for helping to solve other optimization problems, PCST has been applied fruitfully by AT&T to the optimization of real-world telecommunications networks. The most recent improvements for the first two problems, giving a 2-approximation algorithm for each, appeared first in 1992. (A 2-approximation for PCS appeared in 2003.) The natural linear programming (LP) relaxation of PCST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present (2 · ¿)-approximation algorithms for all three problems, connected by a unified technique for improving prize-collecting algorithms that allows us to circumvent the integrality gap barrier.

Details

STOC Conference 2006 Conference Paper

On earthmover distance, metric labeling, and 0-extension

  • Howard J. Karloff
  • Subhash Khot
  • Aranyak Mehta
  • Yuval Rabani

We study the fundamental classification problems O-EXTENSION and METRIC LABELING. MINIMUM WEIGHT TRIANGULATION is closely related to partitioning problems in graph theory and to Lipschitz extensions in Banach spaces; its generalization METRIC LABELING is motivated by applications in computer vision. Researchers had proposed using earthmover metrics to get polynomial time-solvable relaxations for these problems. A conjecture that has attracted much attention recently is that the integrality ratio for these relaxations is constant.We prove that the integrality ratio of the earthmover relaxation for METRIC LABELING is Ω(log n) (which is asymptotically tight), k being the number of labels, whereas the best previous lower bound on the integrality ratio was only constant; that the integrality ratio of the earthmover relaxation for O-EXTENSION is Ω(√log k), k being the number of terminals (it was known to be O((log k)/log log k)), whereas the best previous lower bound was only constant; that for no ε>0 is there a polynomial-time O((log n) 1/4-ε )-approximation algorithm for O-EXTENSION, n being the number of vertices, unless NP ⊆ DTIME(n poly(log n) ), whereas the strongest inapproximability result known before was only MAX SNP-hardness; and that there is a polynomial-time approximation algorithm for O-EXTENSION with performance ratio O(√diam(d)), where diam(d) is the ratio of the largest to smallest nonzero distances in the terminal metric.

Details

FOCS Conference 2004 Conference Paper

On the Integrality Ratio for Asymmetric TSP

  • Moses Charikar
  • Michel X. Goemans
  • Howard J. Karloff

The traveling salesman problem comes in two variants. The symmetric version (STSP) assumes that the cost c/sub ij/ of going to city i to city j is equal to c/sub ji/, while the more general asymmetric version (ATSP) does not make this assumption. In both cases, it is usually assumed that we are in the metric case, i. e. , the costs satisfy the triangle inequality: c/sub ij/ + c/sub jk/ /spl ges/ c/sub ik/ for all i, j, k. In this assumption, 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.

Details

STOC Conference 2003 Conference Paper

On the fractal behavior of TCP

  • Anna C. Gilbert
  • Howard J. Karloff

We propose a natural, mathematically tractable model of TCP which captures both its additive-increase, multiplicative-decrease behavior and its feedback mechanism. Neither a fluid nor a mean-field model, our model does not explicitly model the loss process; the losses are entirely determined by the rates of the sources at the time of buffer overflow. The system involves two sources competing to send packets into one recipient buffer of size B , from which bytes are drained at the rate of d per step. We prove that for many choices of the pairs (B,d) , the long term behavior of the system is fractal. We conjecture that this fact continues to hold for all B > d and d > 2 .

Details

STOC Conference 2003 Conference Paper

OPT versus LOAD in dynamic storage allocation

  • Adam L. Buchsbaum
  • Howard J. Karloff
  • Claire Mathieu
  • 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 is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that OPT≥LOAD ; previous work showed that OPT≤ 3• LOAD . We continue the study of the relationship between OPT and LOAD , proving that OPT=L+O((h max /L) 1/7 )L , where h max is the maximum job height. Conversely, we prove that for any ε>0 , there exists a c>0 such that for all sufficiently large integers h max , there is a DYNAMIC STORAGE ALLOCATION instance with maximum job height h max , maximum load at most L , and OPT≥ L+c(h max /L) 1/2+ε L , for infinitely many integers L . En route, we construct several new polynomial-time approximation algorithms for DYNAMIC STORAGE ALLOCATION.

Details

FOCS Conference 2001 Conference Paper

Approximating Directed Multicuts

  • Joseph Cheriyan
  • Howard J. Karloff
  • Yuval Rabani

The seminal paper of F. T. Leighton and S. Rao (1988) and subsequent papers presented approximate min-max theorems relating multicommodity flow values and cut capacities in undirected networks, developed the divide-and-conquer method for designing approximation algorithms, and generated novel tools for utilizing linear programming relaxations. Yet, despite persistent research efforts, these achievements could not be extended to directed networks, excluding a few cases that are "symmetric" and therefore similar to undirected networks. The paper is an attempt to remedy the situation. We consider the problem of finding a minimum multicut in a directed multicommodity flow network, and give the first nontrivial upper bounds on the maxflow-to-min multicut ratio. Our results are algorithmic, demonstrating nontrivial approximation guarantees.

Details

FOCS Conference 1997 Conference Paper

A 7/8-Approximation Algorithm for MAX 3SAT?

  • Howard J. Karloff
  • Uri Zwick

We describe a randomized approximation algorithm which takes an instance of MAX 3SAT as input. If the instance-a collection of clauses each of length at most three-is satisfiable, then the expected weight of the assignment found is at least 7/8 of optimal. We provide strong evidence (but not a proof) that the algorithm performs equally well on arbitrary MAX 3SAT instances. Our algorithm uses semidefinite programming and may be seen as a sequel to the MAX CUT algorithm of Goemans and Williamson (1995) and the MAX 2SAT algorithm of Feige and Goemans (1995). Though the algorithm itself is fairly simple, its analysis is quite complicated as it involves the computation of volumes of spherical tetrahedra. Hastad has recently shown that, assuming P/spl ne/NP, no polynomial-time algorithm for MAX 3SAT can achieve a performance ratio exceeding 7/8, even when restricted to satisfiable instances of the problem. Our algorithm is therefore optimal in this sense. We also describe a method of obtaining direct semidefinite relaxations of any constraint satisfaction problem of the form MAX CSP(F), where F is a finite family of Boolean functions. Our relaxations are the strongest possible within a natural class of semidefinite relaxations.

Details

FOCS Conference 1992 Conference Paper

A Decomposition Theorem and Bounds for Randomized Server Problems

  • Avrim Blum
  • Howard J. Karloff
  • Yuval Rabani
  • Michael E. Saks

The authors prove a lower bound of Omega ( square root logk/loglogk) for the competitive ratio of randomized algorithms for the k-server problem against an oblivious adversary. The bound holds for arbitrary metric spaces (of at least k+1 points) and provides a new lower bound for the metrical task system problem as well. This improves the previous best lower bound of Omega (loglogk) for arbitrary metric spaces, more closely approaching the conjectured lower bound of Omega (logk). They also prove a lower bound of Omega (/sup logk///sub loglogk/) for the server problem on k+1 equally-spaced points on a line, which corresponds to some natural motion-planning problems. >

Details

TCS Journal 1992 Journal Article

Fast geometric approximation techniques and geometric embedding problems

  • Marshall W. Bern
  • Howard J. Karloff
  • Prabhakar Raghavan
  • Baruch Schieber

Given an undirected n-vertex graph G and a set of n points in R d, we wish to embed the vertices of G onto the points so as to minimize the total embedded edge length. Important special cases of this geometric embedding problem as those in which G is a binary tree, a cycle, or a star. We give fast approximation algorithms for embedding these graphs on the line and in the plane in several metrics. Our principal techniques are: a notion of “approximate geometric sorting” that can be computed in linear time, and fast approximation schemes for the minimum spanning tree problem in the plane. We expect that these approximation techniques can be applied to many geometric problems besides the embedding problem. We give the example of approximating the convex hull of a set of points in the plane.

Details DOI

FOCS Conference 1991 Conference Paper

Competitive Algorithms for Layered Graph Traversal

  • Amos Fiat
  • Dean P. Foster
  • Howard J. Karloff
  • Yuval Rabani
  • Yiftach Ravid
  • Sundar Vishwanathan

A layered graph is a connected, weighted graph whose vertices are partitioned into sets L/sub 0/=(s), L/sub 1/, L/sub 2/, .. ., and whose edges run between consecutive layers. Its width is max( mod L/sub i/ mod ). In the online layered graph traversal problem, a searcher starts at s in a layered graph of unknown width and tries to reach a target vertex t; however, the vertices in layer i and the edges between layers i-1 and i are only revealed when the searcher reaches layer i-1. The authors give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. They give a deterministic online algorithm that is O(9w)-competitive on width-w graphs and prove that for no w can a deterministic online algorithm have a competitive ratio better than 2w/sup -2/ on width-w graphs. They prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized online layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, they give a randomized online algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor. >

Details

FOCS Conference 1990 Conference Paper

Algebraic Methods for Interactive Proof Systems

  • Carsten Lund
  • Lance Fortnow
  • Howard J. Karloff
  • Noam Nisan

An algebraic technique for the construction of interactive proof systems is proposed. The technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. For the proof, a method is developed for reducing the problem of verifying the value of a low-degree polynomial at two points to verifying the value at one new point. The results have implications for program checking, verification, and self-correction. >

Details

TCS Journal 1989 Journal Article

An NC algorithm for Brooks' Theorem

  • Howard J. Karloff

Brooks' Theorem states that any graph G of maximum degree Δ⩾3 can be Δ node colored if and only if G does not contain K Δ+1 as a subgraph. We exhibit an NC algorithm to find a Δ coloring when Brooks' Theorem guarantees it exists.

Details DOI

I&C Journal 1989 Journal Article

The iterated mod problem

  • Howard J. Karloff
  • Walter L. Ruzzo

The iterated mod problem is this: given a, b 1, b 2, …, b n, all integers or all polynomials in Q [x], is ((… ((a mod b 1) mod b 2) …) mod b n ) = 0? When the inputs are integers, we prove the problem P-complete with respect to log-space reductions, whereas in the polynomial case, we prove the problem is in NC. The significance of these results lies primarily in the similarity between the iterated mod problem and the Euclidean algorithm. We also show that the superincreasing knapsack problem is P-complete, using a very similar proof.

Details DOI
v2026.09.13