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...
On Earthmover Distance, Metric Labeling, and 0-Extension (2008)
Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
We study the classification problem Metric Labeling and its special case 0-Extension in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial...
Compressing Rectilinear Pictures and Minimizing Access Control Lists (2008)
Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, Jia Wang
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
Extension and Metric Labeling. 0-Extension is closely (2008)
Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
We study the fundamental classification problems 0-
Caching with Expiration Times for Internet Applications (2008)
Parikshit Gopalan, Howard Karloff, Aranyak Mehta, Milena Mihail, Nisheeth Vishnoi
Abstract. Caching data together with expiration times beyond which the data are no longer valid is a standard method for promoting information coherence in distributed systems, including the...
On the Weak mod m Representation of Boolean Functions (2007)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
one article at a time in L ATEX source form on the Internet. Pagination
Yair Bartal, Howard Karloff, Rakesh Vohra
We consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on the m machines so as to minimize the makespan, the...
Gruia Calinescu Howard, Howard Karloff, Yuval Rabani
Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the...
Gruia Calinescu, Amit Chakrabarti, Howard Karloff, Yuval Rabani
Abstract. We study the problem of finding a most profitable subset of n given tasks, each with a given start and finish time as well as profit and resource requirement, that at no time exceeds the...
Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan
We prove that if a linear error-correcting code C: f0; 1g
Dean P. Foster, Howard Karloff, Yuval Rabani, Yiftach Ravid, Sundar Vishwanathan
A layered graph is a connected graph whose vertices are partitioned into sets L 0 = fsg; L 1; L 2;:::, and whose edges, which have nonnegative integral weights, run between consecutive layers. Its...
Avrim Blum, Howard Karloff, Michael Saks
We consider the problem faced by a mobile robot that has to reach a given target by traveling through an unmapped region in the plane containing oriented rectangular obstacles. We assume the robot...
David L. Applegate, Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, Jia Wang
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
David L. Applegate, Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, Jia Wang
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
Compressing rectilinear pictures and minimizing access control lists (2007)
Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, Jia Wang
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
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
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...
Caching with Expiration Times for Internet Applications (2005)
Gopalan, Parikshit, Karloff, Howard, Mehta, Aranyak, Mihail, Milena, Vishnoi, Nisheeth
Caching data together with expiration times beyond which the data are no longer valid is a standard method for promoting information coherence in distributed systems, including the Internet, the...
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...
Caching with expiration times (2002)
Parikshit Gopalan, Howard Karloff, Aranyak Mehta, Milena Mihail, Nisheeth Vishnoi
Abstract. Caching data together with expiration times beyond which the data is no longer valid is a standard method for promoting information coherence in distributed systems, including the Internet...
Improved Approximation Algorithms for Resource Allocation (2002)
Gruia Calinescu, Amit Chakrabarti, Howard Karloff, Yuval Rabani
We study the problem of nding a most pro table subset of n given tasks, each with a given start and nish time as well as pro t and resource requirement, that at no time exceeds the quantity B of...
Approximation algorithms for the 0-extension problem (2001)
Gruia Calinescu, Howard Karloff, Yuval Rabani
Abstract. In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to...
Approximation algorithms for the 0-extension problem (2001)
Gruia Calinescu, Howard Karloff, Yuval Rabani
In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as...
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval (2001)
Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan
We prove that if a linear error correcting code C : f0; 1g is such that a bit of the message can be probabilistically reconstructed by looking at two entries of a corrupted codeword, then m =...
Approximation Algorithms for the 0-Extension Problem (2000)
Gruia Calinescu, Howard Karloff, Yuval Rabani
In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as...
An improved approximation algorithm for multiway cut (1998)
Gruia Călinescu, Howard Karloff, Yuval Rabani
Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the...
Competitive Algorithms For Layered Graph Traversal (1998)
Amos Fiat, Dean P. Foster, Howard Karloff, Yuval Rabani
.<F3.84e+05> A layered graph is a connected graph whose vertices are partitioned into sets<F3.379e+05> L<F2.724e+05> 0<F3.84e+05>...
Gruia Calinescu, Howard Karloff, Yuval Rabani
Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs (1998)
Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alexander Zelikovsky
We provide the first algorithm with a nontrivial approximation ratio for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-Hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This...
An improved approximation algorithm for multiway cut (1998)
Gruia Călinescu, Howard Karloff, Yuval Rabani
Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs (1997)
Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alexander Zelikovsky
We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-Hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This problem has...
A 7/8-Approximation Algorithm for MAX 3SAT? (Extended Abstract) (1997)
Howard Karloff Uri Zwick April 28, 1997 Modified: August 17, 1997 Abstract We describe a randomized approximation algorithm which takes an instance of MAX 3SAT as input.
A 7/8-Approximation Algorithm for MAX 3SAT? (1997)
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...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs (1997)
Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alexander Zelikovsky
We provide the rst nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-Hard problem of nding a heaviest planar subgraph in an edge-weighted graph G. This problem has...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs (1997)
Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alexander Zelikovsky
We provide the first nontrivial approximation algorithm for maximum weight planar subgraph, the NPhard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This problem has...
A Better Approximation Algorithm for Finding Planar Subgraphs (1996)
Gruia Calinescu Cristina, Cristina G. Fernandes, Ulrich Finkler, Howard Karloff
The MAXIMUM PLANAR SUBGRAPH problem---given a graph G, find a largest planar subgraph of G---has applications in circuit layout, facility layout, and graph drawing. No previous polynomialtime...
Randomized Robot Navigation Algorithms (1996)
Piotr Berman, Avrim Blum, Amos Fiat, Howard Karloff, Adi Rosén, Michael Saks
We consider the problem faced by a mobile robot that has to reach a given target by traveling through an unmapped region in the plane containing oriented rectangular obstacles. We assume the robot...
A Better Approximation Algorithm for Finding Planar Subgraphs (1996)
Gruia Calinescu, Cristina G. Fernandes, Ulrich Finkler, Howard Karloff
The MAXIMUM PLANAR SUBGRAPH problem---given a graph G, find a largest planar subgraph of G---has applications in circuit layout, facility layout, and graph drawing. No previous polynomialtime...
A Better Approximation Algorithm for Finding Planar Subgraphs (1996)
Gruia Calinescu, Cristina G. Fernandes, Ulrich Finkler, Howard Karloff
The MAXIMUM PLANAR SUBGRAPH problem---given a graph G, find a largest planar subgraph of G---has applications in circuit layout, facility layout, and graph drawing. No previous polynomial-time...
A Better Approximation Algorithm for Finding Planar Subgraphs (1996)
Gruia Calinescu, Cristina G. Fernandes, Ulrich Finkler, Howard Karloff
The MAXIMUM PLANAR SUBGRAPH problem---given a graph G, find a largest planar subgraph of G---has applications in circuit layout, facility layout, and graph drawing. No previous polynomialtime...
ARTICLE NO. AL970920 A Better Approximation Algorithm for Finding Planar Subgraphs (1996)
Gruia Calinescu, Cristina G. Fern, Ulrich Finkler, Howard Karloff
The MAXIMUM PLANAR SUBGRAPH problem�given a graph G, find a largest planar subgraph of G�has applications in circuit layout, facility layout, and graph drawing. No previous polynomial-time...
Symmetric Logspace is Closed under Complement (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.
[ii] Chicago Journal of Theoretical Computer Science 1995-3Rabin Measures (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
Published one article at a time in LATEX source form on the Internet. Pagination
A better lower bound for on-line scheduling (1994)
Yair Bartal, Howard Karloff, Yuval Rabani
We consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on the m machines so as to minimize the makespan, the...
On Construction of k-wise Independent Random Variables (1994)
Howard Karloff, Yishay Mansour
A 0-1 probability space is a probability space(\Omega ; 2\Omega ; P ), where the sample space\Omega ` f0; 1g n for some n. A probability space is k-wise independent if, when Y i is defined to be the...
New Results on the Old k-Opt Algorithm for the TSP (1994)
Barun Chandra, Howard Karloff, Craig Tovey
Local search with k-change neighborhoods is perhaps the oldest and most widely used heuristic method for the traveling salesman problem, yet almost no theoretical performance guarantees for it were...
On Construction of k-wise Independent Random Variables (1994)
Howard Karloff, Yishay Mansour
A 0-1 probability space is a probability space(\Omega ; 2\Omega ; P ), where the sample space\Omega ` f0; 1g n for some n. A probability space is k-wise independent if, when Y i is defined to be the...
Algebraic Methods for Interactive Proof Systems (1992)
Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan
We present a new algebraic technique for the construction of interactive proof systems. We use our technique to prove that every language in the polynomial-time hierarchy has an interactive proof...
Algebraic Methods for Interactive Proof Systems (1990)
Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan
We present a new algebraic technique for the construc-tion of interactive proof systems. We use our technique to prove that every language in the polynomial-time hierarchy has an interactive proof...