Removable online knapsack problems

DOI10.1007/3-540-45465-9_26MaRDI QIDQ4737165zbMATH OpenFDO

Authors Shiro Taketomi, Kazuo Iwama

Publication date 11 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2380/23800293.htm

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27)

Recommendations

• Randomized algorithms for removable online knapsack problems
• Online knapsack revisited
• Online knapsack revisited
• Online knapsack problem with removal cost
• Randomized algorithms for online knapsack problems

Cited in

(49)

• Priority algorithms for the subset-sum problem
• Online knapsack with resource augmentation
• On extensions of the deterministic online model for bipartite matching and max-sat
• Buyback problem with discrete concave valuation functions
• Online budgeted maximum coverage
• Improved online algorithms for knapsack and GAP in the random order model
• Improved online algorithm for fractional knapsack in the random order model
• Online algorithms for the maximum \(k\)-interval coverage problem
• Online generalized assignment problem with historical information
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• Lower bounds on the performance of online algorithms for relaxed packing problems
• Online knapsack problem under concave functions
• Unit cost buyback problem
• Online knapsack of unknown capacity. How to optimize energy consumption in smartphones
• Proportional cost buyback problem with weight bounds
• The online knapsack problem: advice and randomization
• Online removable knapsack problem under convex function
• Online knapsack revisited
• The online knapsack problem with incremental capacity
• 2D knapsack: packing squares
• Online removable knapsack with limited cuts
• Online Knapsack Problem Under Concave Functions
• Randomized algorithms for online knapsack problems
• Online unweighted knapsack problem with removal cost
• Online submodular maximization with preemption
• Online maximum matching with recourse
• A theory of auto-scaling for resource reservation in cloud services
• Packing a knapsack of unknown capacity
• Improved Online Algorithms for Knapsack and GAP in the Random Order Model
• Online knapsack with removal and recourse
• Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem
• An optimal algorithm for online multiple knapsack
• Online general knapsack with reservation costs
• Online simple knapsack with bounded predictions
• Removable online knapsack and advice
• A survey of online knapsack problems
• Online knapsack with removal and recourse
• Average sensitivity of the knapsack problem
• Online unbounded knapsack
• Online simple knapsack with reservation costs
• Online knapsack problems with estimates
• Lower bounds on the performance of online algorithms for relaxed packing problems
• Online multiple resource allocation problems with departures via the primal-dual approach
• Removable online knapsack: exploiting recourse and bounded item sizes
• Online maximum matching with recourse
• Online minimization knapsack problem
• Online removable square packing
• On the sum minimization version of the online bin covering problem
• Competitive analysis of online real-time scheduling algorithms under hard energy constraint

This page was built for publication: Removable online knapsack problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4737165)