Complexity and approximation of finding the longest vector sum

DOI10.1134/S0965542518060131zbMath1409.90160OpenAlexW2835227094MaRDI QIDQ1785063

V. V. Shenmaier

Publication date: 27 September 2018

Published in: Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

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

zbMATH Keywords

normed spaceapproximation schemeinapproximability boundvector sumfinding a vector subset

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (4)

Easy NP-hardness Proofs of Some Subset Choice Problems ⋮ Approximability of the Problem of Finding a Vector Subset with the Longest Sum ⋮ On the co-NP-completeness of the zonotope containment problem ⋮ Adaptive reachability algorithms for nonlinear systems using abstraction error analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic approach to the geometry of the \(\ell^n_p\)-ball
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• Lattice problems and norm embeddings
• Solving some vector subset problems by Voronoi diagrams
• Efficient Randomized Algorithm for a Vector Subset Problem
• A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
• Random walks in a convex body and an improved volume algorithm
• A Polynomial Time Algorithm for Shaped Partition Problems
• An exact algorithm for finding a vector subset with the longest sum
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Convex Analysis
• Complexity and algorithms for finding a subset of vectors with the longest sum

This page was built for publication: Complexity and approximation of finding the longest vector sum