Inverse Fractional Knapsack Problem with Profits and Costs Modification

2017/04/01 by Nguyen, Kien Trung, Quoc, Huynh Duc
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1704.00145

Abstract

We address in this paper the problem of modifying both profits and costs of a fractional knapsack problem optimally such that a prespecified solution becomes an optimal solution with prespect to new parameters. This problem is called the inverse fractional knapsack problem. Concerning the l₁-norm, we first prove that the problem is NP-hard. The problem can be however solved in quadratic time if we only modify profit parameters. Additionally, we develop a quadratic-time algorithm that solves the inverse fractional knapsack problem under l_∞-norm.

Related

• The Product Knapsack Problem: Approximation and Complexity
• Dynamic programming algorithms, efficient solution of the LP-relaxation\n and approximation schemes for the Penalized Knapsack Problem
• Packing Linear Programs and Fractional Knapsack using Comparison Oracles
• Heuristic and exact fixation-based approaches for the discounted 0-1 knapsack problem
• Weakly Approximating Knapsack in Subquadratic Time