Approximation of the Quadratic Knapsack Problem

2015/09/06 by Richard Taylor, Taylor, Richard
Computer Science · Mathematics · #68W25 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #cs.DM #cs.DS #math.CO #msc:68W25

paper · pdf · doi:10.48550/arxiv.1509.01866

8 pages one figure

arxiv created 2016/05/23 · arxiv updated 2016/05/24

Abstract

For any given ε>0 we provide an algorithm for the Quadratic Knapsack Problem that has an approximation ratio within O(n^2/5+ε) and a run time within O(n^9/ε).

Related

• A Nearly Quadratic-Time FPTAS for Knapsack
• (1-ε)-Approximation of Knapsack in Nearly Quadratic Time
• Fast Approximation Algorithms for Knapsack Problems
• 0-1 Knapsack in Nearly Quadratic Time
• Knapsack with Small Items in Near-Quadratic Time