scientific article; zbMATH DE number 7204473

DOI10.4230/LIPICS.ICALP.2017.21MaRDI QIDQ5111351zbMATHFDO

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

(21)

• The fine-grained complexity of multi-dimensional ordering properties
• Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
• scientific article; zbMATH DE number 7122316 (Why is no real title available?)
• Computing generalized convolutions faster than brute force
• On problems equivalent to \((\min,+)\)-convolution
• Quantum complexity for vector domination problem
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• More on change-making and related problems
• Faster minimization of tardy processing time on a single machine
• A polyhedral perspective on tropical convolutions
• Tight conditional lower bounds for longest common increasing subsequence
• Fine-Grained Complexity Theory (Tutorial)
• 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?)
• (1+1) EA on Generalized Dynamic OneMax
• Hamming Distance Completeness
• The Orthogonal Vectors Conjecture for Branching Programs and Formulas
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• The Least Weight Subsequence Problem
• scientific article; zbMATH DE number 7561569 (Why is no real title available?)

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)