Karmarkar–Karp bin packing algorithms

<p>The Karmarkar–Karp (KK) bin packing algorithms are several related <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithm</a> for the <a href="/facts/Bin_packing_problem/T67Qe934">bin packing problem</a>. The bin packing problem is a problem of packing items of different sizes into bins of identical capacity, such that the total number of bins is as small as possible. Finding the optimal solution is <a href="/facts/NP-hardness/mQeNPv4R">computationally hard</a>. <a href="/facts/Narendra_Karmarkar/NVB6kg95">Karmarkar</a> and <a href="/facts/Richard_M._Karp/XtYCL0nA">Karp</a> devised an algorithm that runs in <a href="/facts/Polynomial-time/77T62gmf">polynomial time</a> and finds a solution with at most 
  
    
      
        
          O
          P
          T
        
        +
        
          
            O
          
        
        (
        
          log
          
            2
          
        
        ⁡
        (
        O
        P
        T
        )
        )
      
    
    {\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}(OPT))}
  
 bins, where OPT is the number of bins in the optimal solution. They also devised several other algorithms with slightly different approximation guarantees and run-time bounds.
</p><p>The KK algorithms were considered a breakthrough in the study of bin packing: the previously-known algorithms found multiplicative approximation, where the number of bins was at most 
  
    
      
        r
        ⋅
        
          O
          P
          T
        
        +
        s
      
    
    {\displaystyle r\cdot \mathrm {OPT} +s}
  
 for some constants 
  
    
      
        r
        >
        1
        ,
        s
        >
        0
      
    
    {\displaystyle r>1,s>0}
  
, or at most 
  
    
      
        (
        1
        +
        ε
        )
        
          O
          P
          T
        
        +
        1
      
    
    {\displaystyle (1+\varepsilon )\mathrm {OPT} +1}
  
. The KK algorithms were the first ones to attain an additive approximation.
</p>

Karmarkar–Karp bin packing algorithms open-in-new

Karmarkar–Karp bin packing algorithms