scientific article; zbMATH DE number 7204473

DOI10.4230/LIPICS.ICALP.2017.21MaRDI QIDQ5111351zbMATH OpenFDO

Authors Marvin Künnemann, Ramamohan Paturi, Stefan Schneider

Publication date 27 May 2020

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

zbMATH Keywords

knapsackSETHfine-grained complexitysubquadratic algorithmsleast-weight subsequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On Problems Equivalent to (min,+)-Convolution
• The Least Weight Subsequence Problem
• Limitations of incremental dynamic programming
• On problems equivalent to \((\min,+)\)-convolution
• Multivariate fine-grained complexity of longest common subsequence

Cited in

(34)

• Tight conditional lower bounds for longest common increasing subsequence
• Fast convolutions for near-convex sequences
• Tight conditional lower bounds for longest common increasing subsequence
• scientific article; zbMATH DE number 7561512 (Why is no real title available?)
• scientific article; zbMATH DE number 7651168 (Why is no real title available?)
• The Orthogonal Vectors Conjecture for Branching Programs and Formulas
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• The Least Weight Subsequence Problem
• Faster minimization of tardy processing time on a single machine
• (1+1) EA on Generalized Dynamic OneMax
• Structured ( ,+)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
• Computing generalized convolutions faster than brute force
• Current algorithms for detecting subgraphs of bounded treewidth are probably optimal
• Knapsack and subset sum with small items
• Hamming Distance Completeness
• On the fine-grained complexity of parity problems
• A polyhedral perspective on tropical convolutions
• Faster minimization of tardy processing time on a single machine
• On problems equivalent to \((\min,+)\)-convolution
• More on change-making and related problems
• Even faster knapsack via rectangular monotone min-plus convolution and balancing
• Exploring the approximability landscape of 3SUM
• scientific article; zbMATH DE number 7122316 (Why is no real title available?)
• No polynomial kernels for knapsack
• Minimizing tardy processing time on a single machine in near-linear time
• Quantum complexity for vector domination problem
• Fine-Grained Complexity Theory (Tutorial)
• scientific article; zbMATH DE number 7561569 (Why is no real title available?)
• Approximating the geometric knapsack problem in near-linear time and dynamically
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• Tensor ranks and the fine-grained complexity of dynamic programming
• Minimizing tardy processing time on a single machine in near-linear time
• Computing generalized convolutions faster than brute force
• The fine-grained complexity of multi-dimensional ordering properties

This page was built for publication:

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