Reoptimizing the 0-1 knapsack problem

DOI10.1016/j.dam.2010.08.003zbMath1206.90132OpenAlexW2088181319MaRDI QIDQ608266

Sumit K. Garg

Publication date: 25 November 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.08.003

zbMATH Keywords

worst-case analysis

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (19)

A survey on combinatorial optimization in dynamic environments ⋮ Reoptimization of constraint satisfaction problems with approximation resistant predicates ⋮ Reoptimization of maximum weight induced hereditary subgraph problems ⋮ Robust reoptimization of Steiner trees ⋮ Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications ⋮ Steiner tree reoptimization in graphs with sharpened triangle inequality ⋮ Unnamed Item ⋮ Reoptimization of the shortest common superstring problem ⋮ A theory and algorithms for combinatorial reoptimization ⋮ Reoptimization of max \(k\)-cover: approximation ratio threshold ⋮ On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field ⋮ A note on the traveling salesman reoptimization problem under vertex insertion ⋮ Knowing All Optimal Solutions Does Not Help for TSP Reoptimization ⋮ Reoptimization of set covering problems ⋮ Tolerance analysis for 0-1 knapsack problems ⋮ Reoptimization of the metric deadline TSP ⋮ Reallocation problems in scheduling ⋮ Reoptimization of the Shortest Common Superstring Problem ⋮ REOPTIMIZATION UNDER VERTEX INSERTION: MAX P_k-FREE SUBGRAPH AND MAX PLANAR SUBGRAPH

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new fully polynomial time approximation scheme for the Knapsack problem
• Approximation algorithms for knapsack problems with cardinality constraints
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Approximate Algorithms for the 0/1 Knapsack Problem
• Reoptimizing the traveling salesman problem
• On the Hardness of Reoptimization
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Scheduling with forbidden sets

This page was built for publication: Reoptimizing the 0-1 knapsack problem