Complexity and approximation of finding the longest vector sum

DOI10.1134/S0965542518060131zbMATH Open1409.90160OpenAlexW2835227094MaRDI QIDQ1785063FDOQ1785063

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

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

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)

Cites Work

• Title not available (Why is that?)
• Convex Analysis
• Random walks in a convex body and an improved volume algorithm
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Title not available (Why is that?)
• Lattice problems and norm embeddings
• 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
• The problem of finding a subset of vectors with maximal total weight
• A probabilistic approach to the geometry of the \(\ell^n_p\)-ball
• A Polynomial Time Algorithm for Shaped Partition Problems
• Efficient randomized algorithm for a vector subset problem
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• 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
• Solving some vector subset problems by Voronoi diagrams

Cited In (12)

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

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)