Complexity and algorithms for finding a subset of vectors with the longest sum

DOI10.1016/j.tcs.2018.04.018zbMath1433.68504OpenAlexW2801173338MaRDI QIDQ5918111

Vladimir Shenmaier

Publication date: 7 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.04.018

zbMATH Keywords

complexitynormed spacematrix normexact algorithmvector sum

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• The Vector Partition Problem for Convex Objective Functions
• Lattice problems and norm embeddings
• Solving some vector subset problems by Voronoi diagrams
• Constructing Arrangements of Lines and Hyperplanes with Applications
• On the Zone Theorem for Hyperplane Arrangements
• Semidefinite relaxation and nonconvex quadratic optimization
• Tight Hardness of the Non-commutative Grothendieck Problem
• A Polynomial Time Algorithm for Shaped Partition Problems
• An exact algorithm for finding a vector subset with the longest sum
• Some optimal inapproximability results
• Approximating the Cut-Norm via Grothendieck's Inequality

This page was built for publication: Complexity and algorithms for finding a subset of vectors with the longest sum