Efficient randomized algorithm for a vector subset problem

DOI10.1007/978-3-319-44914-2_12MaRDI QIDQ3133208zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(7)

• Complexity and approximation of finding the longest vector sum
• Easy NP-hardness Proofs of Some Subset Choice Problems
• 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
• Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
• An approximation scheme for a problem of search for a vector subset

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)