On problems equivalent to (,+)-convolution
From MaRDI portal
Recommendations
- On Problems Equivalent to (min,+)-Convolution
- On integer programming and convolution
- On some fine-grained questions in algorithms and complexity
- scientific article; zbMATH DE number 7204473
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
Cited in
(46)- More on change-making and related problems
- Faster minimization of tardy processing time on a single machine
- Approximating subset sum ratio via subset sum computations
- Tight conditional lower bounds for longest common increasing subsequence
- Bisection of bounded treewidth graphs by convolutions
- On the convex infimum convolution inequality with optimal cost function
- scientific article; zbMATH DE number 7617051 (Why is no real title available?)
- Bisection of bounded treewidth graphs by convolutions
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- scientific article; zbMATH DE number 7561569 (Why is no real title available?)
- scientific article; zbMATH DE number 7204473 (Why is no real title available?)
- On Problems Equivalent to (min,+)-Convolution
- Tight conditional lower bounds for longest common increasing subsequence
- On binary solutions to systems of equations
- scientific article; zbMATH DE number 7122316 (Why is no real title available?)
- scientific article; zbMATH DE number 7651168 (Why is no real title available?)
- Solving cut-problems in quadratic time for graphs with bounded treewidth
- On the complexity of scheduling problems with a fixed number of parallel identical machines
- Improved Merlin-Arthur protocols for central problems in fine-grained complexity
- Structured ( ,+)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
- A polyhedral perspective on tropical convolutions
- Computing generalized convolutions faster than brute force
- Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
- Approximating subset sum ratio via partition computations
- An FPTAS for budgeted laminar matroid independent set
- \((\min ,+)\) matrix and vector products for inputs decomposable into few monotone subsequences
- Faster minimization of tardy processing time on a single machine
- On the fine-grained complexity of parity problems
- Discrete effort distribution via regret-enabled greedy algorithm
- No polynomial kernels for knapsack
- Minimizing tardy processing time on a single machine in near-linear time
- Lower bounds for matroid optimization problems with a linear constraint
- Approximating the geometric knapsack problem in near-linear time and dynamically
- Minimizing tardy processing time on a single machine in near-linear time
- Fast convolutions for near-convex sequences
- Computing generalized convolutions faster than brute force
- Approximate min-sum subset convolution
- (, +) matrix and vector products for inputs decomposable into few monotone subsequences
- Knapsack and subset sum with small items
- Even faster knapsack via rectangular monotone min-plus convolution and balancing
- Exploring the approximability landscape of 3SUM
- Minimizing the weighted number of tardy jobs is W[1]-hard
- Does subset sum admit short proofs?
- Minimizing the weighted number of tardy jobs is W[1]-hard
- Convolution and knapsack in higher dimensions
- Weakly approximating knapsack in subquadratic time
This page was built for publication: On problems equivalent to \((\min,+)\)-convolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629984)
