Howard Karloff
Research Subjects
Howard Karloff has a total of 21 co-authors. Here are the top co-authors by number of shared publications:
- Moses Charikar
Computer Science Department Princeton University
2 shared publications Ankur Moitra
1 shared publication- Anna C. Gilbert
Department of Mathematics University of Michigan Ann Arbor Ann Arbor 48104 MI
1 shared publication - Ari Freund
Department of Computer Science, Technion, Haifa 32000, Israel
1 shared publication - Flip Korn
AT&T Labs–Research
1 shared publication Gruia Calinescu
1 shared publication
Latest Publications
- 1 February 2014
- Published by Elsevier in Computational Geometry
- Vol. 47 (2) , 141-148
Sequential dependency computation via geometric data structures
- 1 February 2014
- Published by Elsevier in Computational Geometry
- Vol. 47 (2) , 141-148
Sequential dependency computation via geometric data structures
- 3 February 2011
- Published by Springer Nature in Algorithmica
- Vol. 61 (1) , 190-206
Improved Approximation Algorithms for Label Cover Problems
- 3 February 2011
- Published by Springer Nature in Algorithmica
- Vol. 61 (1) , 190-206
Improved Approximation Algorithms for Label Cover Problems
- 23 January 2011
- Published by Society for Industrial & Applied Mathematics (SIAM)
Capacitated Metric Labeling
- 23 January 2011
- Published by Society for Industrial & Applied Mathematics (SIAM)
Capacitated Metric Labeling
- Open Access
On Parsimonious Explanations for 2-D Tree- and Linearly-Ordered Data
This paper studies the "explanation problem" for tree- and linearly-ordered array data, a problem motivated by database applications and recently solved for the one-dimensional tree-ordered case. In this paper, one is given a matrix A whose rows and columns have semantics: special subsets of the rows and special subsets of the columns are meaningful, others are not. A submatrix in A is said to be meaningful if and only if it is the cross product of a meaningful row subset and a meaningful column subset, in which case we call it an "allowed rectangle." The goal is to "explain" A as a sparse sum of weighted allowed rectangles. Specifically, we wish to find as few weighted allowed rectangles as possible such that, for all i,j, a_{ij} equals the sum of the weights of all rectangles which include cell (i,j). In this paper we consider the natural cases in which the matrix dimensions are tree-ordered or linearly-ordered. In the tree-ordered case, we are given a rooted tree T1 whose leaves are the rows of A and another, T2, whose leaves are the columns. Nodes of the trees correspond in an obvious way to the sets of their leaf descendants. In the linearly-ordered case, a set of rows or columns is meaningful if and only if it is contiguous. For tree-ordered data, we prove the explanation problem NP-Hard and give a randomized 2-approximation algorithm for it. For linearly-ordered data, we prove the explanation problem NP-Hard and give a 2.56-approximation algorithm. To our knowledge, these are the first results for the problem of sparsely and exactly representing matrices by weighted rectangles.
Open AccessOn Parsimonious Explanations for 2-D Tree- and Linearly-Ordered Data
This paper studies the "explanation problem" for tree- and linearly-ordered array data, a problem motivated by database applications and recently solved for the one-dimensional tree-ordered case. In this paper, one is given a matrix A whose rows and columns have semantics: special subsets of the rows and special subsets of the columns are meaningful, others are not. A submatrix in A is said to be meaningful if and only if it is the cross product of a meaningful row subset and a meaningful column subset, in which case we call it an "allowed rectangle." The goal is to "explain" A as a sparse sum of weighted allowed rectangles. Specifically, we wish to find as few weighted allowed rectangles as possible such that, for all i,j, a_{ij} equals the sum of the weights of all rectangles which include cell (i,j). In this paper we consider the natural cases in which the matrix dimensions are tree-ordered or linearly-ordered. In the tree-ordered case, we are given a rooted tree T1 whose leaves are the rows of A and another, T2, whose leaves are the columns. Nodes of the trees correspond in an obvious way to the sets of their leaf descendants. In the linearly-ordered case, a set of rows or columns is meaningful if and only if it is contiguous. For tree-ordered data, we prove the explanation problem NP-Hard and give a randomized 2-approximation algorithm for it. For linearly-ordered data, we prove the explanation problem NP-Hard and give a 2.56-approximation algorithm. To our knowledge, these are the first results for the problem of sparsely and exactly representing matrices by weighted rectangles.
- 21 May 2008
- Published by Springer Nature in Algorithmica
- Vol. 56 (4) , 577-604
ℓ 2 2 Spreading Metrics for Vertex Ordering Problems
- 21 May 2008
- Published by Springer Nature in Algorithmica
- Vol. 56 (4) , 577-604
ℓ 2 2 Spreading Metrics for Vertex Ordering Problems
- Open Access
Combining geometry and combinatorics: A unified approach to sparse signal recovery
There are two main algorithmic approaches to sparse signal recovery: geometric and combinatorial. The geometric approach starts with a geometric constraint on the measurement matrix and then uses linear programming to decode information about the signal from its measurements. The combinatorial approach constructs the measurement matrix and a combinatorial decoding algorithm to match. We present a unified approach to these two classes of sparse signal recovery algorithms. The unifying elements are the adjacency matrices of high-quality unbalanced expanders. We generalize the notion of Restricted Isometry Property (RIP), crucial to compressed sensing results for signal recovery, from the Euclidean norm to the l_p norm for p about 1, and then show that unbalanced expanders are essentially equivalent to RIP-p matrices. From known deterministic constructions for such matrices, we obtain new deterministic measurement matrix constructions and algorithms for signal recovery which, compared to previous deterministic algorithms, are superior in either the number of measurements or in noise tolerance.
Open AccessCombining geometry and combinatorics: A unified approach to sparse signal recovery
There are two main algorithmic approaches to sparse signal recovery: geometric and combinatorial. The geometric approach starts with a geometric constraint on the measurement matrix and then uses linear programming to decode information about the signal from its measurements. The combinatorial approach constructs the measurement matrix and a combinatorial decoding algorithm to match. We present a unified approach to these two classes of sparse signal recovery algorithms. The unifying elements are the adjacency matrices of high-quality unbalanced expanders. We generalize the notion of Restricted Isometry Property (RIP), crucial to compressed sensing results for signal recovery, from the Euclidean norm to the l_p norm for p about 1, and then show that unbalanced expanders are essentially equivalent to RIP-p matrices. From known deterministic constructions for such matrices, we obtain new deterministic measurement matrix constructions and algorithms for signal recovery which, compared to previous deterministic algorithms, are superior in either the number of measurements or in noise tolerance.
- 1 May 2005
- Published by Springer Nature in Combinatorica
- Vol. 25 (3) , 251-269
Approximating Directed Multicuts
- 1 May 2005
- Published by Springer Nature in Combinatorica
- Vol. 25 (3) , 251-269
Approximating Directed Multicuts
- 31 August 2002
- Published by Elsevier in Journal of Algorithms
- Vol. 44 (2) , 338-358
Thresholds and optimal binary comparison search trees
- 31 August 2002
- Published by Elsevier in Journal of Algorithms
- Vol. 44 (2) , 338-358
Thresholds and optimal binary comparison search trees
- 1 July 2000
- Published by Elsevier in Information Processing Letters
- Vol. 75 (1-2) , 43-50
A lower bound of on the integrality ratio of the Călinescu–Karloff–Rabani relaxation for multiway cut
- 1 July 2000
- Published by Elsevier in Information Processing Letters
- Vol. 75 (1-2) , 43-50
A lower bound of on the integrality ratio of the Călinescu–Karloff–Rabani relaxation for multiway cut