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

DOI10.1134/S1990478918040154zbMATH Open1438.90402OpenAlexW2902511478WikidataQ128896689 ScholiaQ128896689MaRDI QIDQ4973237FDOQ4973237

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

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

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)

Cites Work

• Approximating the Cut-Norm via Grothendieck's Inequality
• Title not available (Why is that?)
• Semidefinite relaxation and nonconvex quadratic optimization
• Title not available (Why is that?)
• Lattice problems and norm embeddings
• Title not available (Why is that?)
• The problem of finding a subset of vectors with maximal total weight
• Approximation algorithms and semidefinite programming.
• Tight hardness of the non-commutative Grothendieck problem
• The vector partition problem for convex objective functions.
• A Polynomial Time Algorithm for Shaped Partition Problems
• Polynomial algorithms for solving the vector sum problem
• Complexity and approximation of the longest vector sum problem
• Complexity and approximation of finding the longest vector sum
• On complexity of the problem of choosing a vector subset with maximal sum length
• 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 (5)

• 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
• Complexity and approximation of finding the longest vector sum
• Solving some vector subset problems by Voronoi diagrams

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)