Packing a Knapsack of Unknown Capacity

DOI10.1137/16M1070049zbMath1370.68329arXiv1307.2806WikidataQ57399715 ScholiaQ57399715MaRDI QIDQ5275439

Nicole Megow, Yann Disser, Max Klimm, Sebastian Stiller

Publication date: 14 July 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.2806

zbMATH Keywords

robustnessknapsackapproximation guaranteesunknown capacity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (6)

A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs ⋮ Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows ⋮ Submodular Maximization with Uncertain Knapsack Capacity ⋮ Online knapsack problem under concave functions ⋮ Fractionally subadditive maximization under an incremental knapsack constraint ⋮ General bounds for incremental maximization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The online knapsack problem with incremental capacity
• Online removable knapsack with limited cuts
• Randomized algorithms for online knapsack problems
• Recoverable robust knapsacks: the discrete scenario case
• Universal classes of hash functions
• Robust discrete optimization and network flows
• Online knapsack with resource augmentation
• Randomized strategies for cardinality robustness in the knapsack problem
• Stochastic on-line knapsack problems
• The online knapsack problem: advice and randomization
• Online removable knapsack problem under convex function
• The Dynamic and Stochastic Knapsack Problem
• Optimization over Integers with Robustness in Cost and Few Constraints
• Universal Sequencing on an Unreliable Machine
• Packing a Knapsack of Unknown Capacity
• Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints
• Recoverable Robustness by Column Generation
• Computing Knapsack Solutions with Cardinality Robustness
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• Cache-Oblivious Algorithms
• Survey on Oblivious Routing Strategies
• Universal approximations for TSP, Steiner tree, and set cover
• A Knapsack Secretary Problem with Applications
• The Dynamic and Stochastic Knapsack Problem with Random Sized Items
• Sometimes Travelling is Easy: The Master Tour Problem
• Finite Horizon Stochastic Knapsacks with Applications to Yield Management
• Robust Matchings
• On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications
• An Incremental Model for Combinatorial Maximization Problems
• Robust randomized matchings
• On the Robust Knapsack Problem
• Hiding information and signatures in trapdoor knapsacks
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Packing a Knapsack of Unknown Capacity