Efficient randomized algorithm for a vector subset problem

DOI10.1007/978-3-319-44914-2_12zbMATH Open1380.68436OpenAlexW2557632260MaRDI QIDQ3133208FDOQ3133208

Authors: Eh. Kh. Gimadi, I. A. Rykov 

Publication date: 13 February 2018

Published in: Discrete Optimization and Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-44914-2_12

Recommendations

• A randomized algorithm for finding a subset of vectors with the maximum Euclidean norm of their sum
• A randomized algorithm for two-cluster partition of a set of vectors
• Complexity and approximation of the longest vector sum problem
• An approximation algorithm for solving the problem of the search of a subset of vectors
• An approximation scheme for a problem of search for a vector subset

zbMATH Keywords

randomized algorithmperformance guaranteesasymptotically exact algorithmvector subset

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Randomized algorithms (68W20) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (7)

• A randomized algorithm for two-cluster partition of a set of vectors
• An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors
• A randomized algorithm for finding a subset of vectors with the maximum Euclidean norm of their sum
• Complexity and approximation of finding the longest vector sum
• An approximation scheme for a problem of search for a vector subset
• Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
• Easy NP-hardness Proofs of Some Subset Choice Problems

This page was built for publication: Efficient randomized algorithm for a vector subset problem

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