No polynomial kernels for knapsack

DOI10.4230/LIPICS.ICALP.2024.83MaRDI QIDQ6875113zbMATH OpenFDO

Authors Klaus Heeger, Danny Hermelin, Matthias Mnich, Dvir Shabtay

Publication date 14 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2024.83

zbMATH Keywords

compositionsknapsackpolynomial kernelsnumber of different profitsnumber of different weights

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 4213909 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 7561512 (Why is no real title available?)
• scientific article; zbMATH DE number 7561569 (Why is no real title available?)
• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• scientific article; zbMATH DE number 7122316 (Why is no real title available?)
• A knapsack-type public key cryptosystem based on arithmetic in finite fields
• An application of simultaneous diophantine approximation in combinatorial optimization
• Approximating Knapsack and partition via dense subset sums
• Bounding the running time of algorithms for scheduling and packing problems
• Clustering to minimize the maximum intercluster distance
• Cryptanalysis: a survey of recent results
• Efficient cryptographic schemes provably as secure as subset sum
• Fast algorithms for knapsack via convolution and prediction
• Faster 0-1-knapsack via near-convex min-plus-convolution
• Faster algorithms for bounded knapsack and bounded subset sum via fine-grained proximity results
• Faster knapsack algorithms via bounded monotone min-plus-convolution
• Hardness of approximation for knapsack problems
• Hiding information and signatures in trapdoor knapsacks
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Infeasibility of instance compression and succinct PCPs for NP
• Integer Programming with a Fixed Number of Variables
• Kernelization Lower Bounds by Cross-Composition
• Kernelization lower bounds through colors and IDs
• Kernelization. Theory of parameterized preprocessing
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Minkowski's Convex Body Theorem and Integer Programming
• New algorithms for minimizing the weighted number of tardy jobs on a single machine
• New limits to classical and quantum instance compression
• On problems equivalent to \((\min,+)\)-convolution
• On problems without polynomial kernels
• Parameterized algorithms
• Parameterizing by the number of numbers
• Polynomial kernels for weighted problems
• Reducibility among combinatorial problems
• SETH-based Lower Bounds for Subset Sum and Bicriteria Path
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Scheduling. Theory, algorithms, and systems
• Sensitivity theorems in integer linear programming
• Some consequences of non-uniform conditions on uniform classes
• The subspace flatness conjecture and faster integer programming

This page was built for publication: No polynomial kernels for knapsack

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