Approximability of the problem of finding a vector subset with the longest sum

DOI10.1134/S1990478918040154MaRDI QIDQ4973237zbMATH OpenOpenAlexWikidataFDO

Authors V. V. Shenmaier

Publication date 2 December 2019

Published in Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s1990478918040154

zbMATH Keywords

approximation algorithminapproximability boundsum vectorsearch of a vector subset

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Complexity and approximation of finding the longest vector sum
• Complexity and approximation of the longest vector sum problem
• Complexity and algorithms for finding a subset of vectors with the longest sum
• Complexity and algorithms for finding a subset of vectors with the longest sum
• An exact algorithm for finding a vector subset with the longest sum

Cites work

• scientific article; zbMATH DE number 3124239 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 6783411 (Why is no real title available?)
• A Polynomial Time Algorithm for Shaped Partition Problems
• An exact algorithm for finding a vector subset with the longest sum
• Approximating the Cut-Norm via Grothendieck's Inequality
• Approximation algorithms and semidefinite programming.
• Complexity and algorithms for finding a subset of vectors with the longest sum
• Complexity and approximation of finding the longest vector sum
• Complexity and approximation of the longest vector sum problem
• Lattice problems and norm embeddings
• On complexity of the problem of choosing a vector subset with maximal sum length
• Polynomial algorithms for solving the vector sum problem
• Semidefinite relaxation and nonconvex quadratic optimization
• Solving some vector subset problems by Voronoi diagrams
• The problem of finding a subset of vectors with maximal total weight
• The vector partition problem for convex objective functions.
• Tight hardness of the non-commutative Grothendieck problem

Cited in

(5)

• Complexity and approximation of finding the longest vector sum
• Complexity and algorithms for finding a subset of vectors with the longest sum
• Complexity and algorithms for finding a subset of vectors with the longest sum
• Solving some vector subset problems by Voronoi diagrams
• Complexity and approximation of the longest vector sum problem

This page was built for publication: Approximability of the problem of finding a vector subset with the longest sum

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