Narendra Karmarkar

ICML Conference 2000 Conference Paper

An Approach to Data Reduction and Clustering with Theoretical Guarantees

• Partha Niyogi
• Narendra Karmarkar

STOC Conference 1984 Conference Paper

A New Polynomial-Time Algorithm for Linear Programming

• Narendra Karmarkar

We present a new polynomial-time algorithm for linear programming. The running-time of this algorithm is O ( n 3-5 L 2 ), as compared to O ( n 6 L 2 ) for the ellipsoid algorithm. We prove that given a polytope P and a strictly interior point a ε P , there is a projective transformation of the space that maps P , a to P' , a' having the following property. The ratio of the radius of the smallest sphere with center a' , containing P' to the radius of the largest sphere with center a' contained in P' is O ( n ). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial-time.

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.

FOCS Conference 1982 Conference Paper

Probabilistic Analysis of Some Bin-Packing Problems

• Narendra Karmarkar

We analyze the average-case behaviour of the Next-Fit algorithm for bin-packing, and obtain closed-form expressions for distributions of interest. Our analysis is based on a novel technique of partitioning the interval (0, 1) suitably and then formulating the problem as a matrix-differential equation. We compare our analytic results with previously known simulation results and show that there is an excellent agreement between the two. We also explain a certain empirically observed anomaly in the behaviour of the algorithm. Finally we establish that asymptotically perfect packing is possible when input items are drawn from a monotonically decreasing density function.