scientific article; zbMATH DE number 7122316

DOI10.4230/OASIcs.SOSA.2018.5zbMath1433.68613MaRDI QIDQ5240419

Timothy M. Chan

Publication date: 25 October 2019

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

optimizationknapsack problemapproximation algorithms\((\min+)\)-convolution

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (9)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Approximation schemes for subset-sums ratio problems ⋮ Unnamed Item ⋮ A faster FPTAS for knapsack problem with cardinality constraint ⋮ \(\ell_1\)-sparsity approximation bounds for packing integer programs ⋮ Strongly polynomial FPTASes for monotone dynamic programs ⋮ A faster FPTAS for knapsack problem with cardinality constraint ⋮ Approximation schemes for multiperiod binary knapsack problems ⋮ An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem

Cites Work

• Unnamed Item
• Necklaces, convolutions, and \(X+Y\)
• A new fully polynomial time approximation scheme for the Knapsack problem
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• A faster FPTAS for the unbounded knapsack problem
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Clustered Integer 3SUM via Additive Combinatorics
• 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
• Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
• On Problems Equivalent to (min,+)-Convolution
• Faster all-pairs shortest paths via circuit complexity

This page was built for publication: