Online removable knapsack with limited cuts

DOI10.1016/j.tcs.2010.08.009zbMath1234.68469OpenAlexW2026640149MaRDI QIDQ410717

Kazuhisa Makino, Xin Han

Publication date: 3 April 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.009

zbMATH Keywords

online algorithmscompetitive ratioknapsack problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)

Related Items (9)

Packing a Knapsack of Unknown Capacity ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ 2D knapsack: packing squares ⋮ Online minimization knapsack problem ⋮ The online knapsack problem: advice and randomization ⋮ Online Knapsack Problem Under Concave Functions ⋮ Online unweighted knapsack problem with removal cost ⋮ Online knapsack problem under concave functions ⋮ Online generalized assignment problem with historical information

Uses Software

• Knapsack

Cites Work

• Stochastic on-line knapsack problems
• Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem
• Online Minimization Knapsack Problem
• Optimal Resource Augmentations for Online Knapsack
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Finite-State Online Algorithms and Their Automated Competitive Analysis
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Online removable knapsack with limited cuts