Complexity and approximation of finding the longest vector sum

DOI10.1134/S0965542518060131MaRDI QIDQ1785063zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• 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
• Approximability of the problem of finding a vector subset with the longest sum
• A randomized algorithm for finding a subset of vectors with the maximum Euclidean norm of their sum

Cites work

• scientific article; zbMATH DE number 5546942 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A Polynomial Time Algorithm for Shaped Partition Problems
• A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
• A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence
• A probabilistic approach to the geometry of the \(\ell^n_p\)-ball
• An exact algorithm for finding a vector subset with the longest sum
• Complexity and algorithms for finding a subset of vectors with the longest sum
• Convex Analysis
• Efficient randomized algorithm for a vector subset problem
• Lattice problems and norm embeddings
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• Random walks in a convex body and an improved volume algorithm
• Solving some vector subset problems by Voronoi diagrams
• Some optimal inapproximability results
• The problem of finding a subset of vectors with maximal total weight

Cited in

(12)

• scientific article; zbMATH DE number 7711611 (Why is no real title available?)
• Polynomial algorithms for solving the vector sum problem
• Easy NP-hardness Proofs of Some Subset Choice Problems
• Adaptive reachability algorithms for nonlinear systems using abstraction error analysis
• Greedy algorithm fails in compact vector summation
• 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
• A randomized algorithm for finding a subset of vectors with the maximum Euclidean norm of their sum
• On the Complexity of Approximate Sum of Sorted List
• On the co-NP-completeness of the zonotope containment problem
• Complexity and approximation of the longest vector sum problem
• Approximability of the problem of finding a vector subset with the longest sum

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

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