On the complexity and approximability of some Euclidean optimal summing problems

DOI10.1134/S0965542516100080zbMATH Open1400.68248OpenAlexW2533199277MaRDI QIDQ506239FDOQ506239

Artem Pyatkin, Anton Valentinovich Eremeev, A. V. Kel'manov

Publication date: 31 January 2017

Published in: Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0965542516100080

Recommendations

• On the complexity of some Euclidean optimal summing problems
• The problem of finding a subset of vectors with maximal total weight
• On the complexity of some Euclidean problems of partitioning a finite set of points
• scientific article; zbMATH DE number 6004969
• scientific article

zbMATH Keywords

cluster analysisNP-hardnessEuclidean spacediscrete optimization problemsnorm of sumpseudopolynomial solvabilitysearch for a subset

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of certain problems of choosing subset of vectors
• Title not available (Why is that?)
• Title not available (Why is that?)
• Trading Hubs Construction for Electricity Markets
• On complexity of some problems of cluster analysis of vector sequences
• On the complexity of a search for a subset of ``similar vectors
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (2)

• Complexity and approximation of the longest vector sum problem
• An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture

This page was built for publication: On the complexity and approximability of some Euclidean optimal summing problems

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