Geodesic
On the complexity and approximability of some Euclidean optimal summing problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 10, pp. 1831-1836 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The complexity status of several well-known discrete optimization problems with the direction of optimization switching from maximum to minimum is analyzed. The task is to find a subset of a finite set of Euclidean points (vectors). In these problems, the objective functions depend either only on the norm of the sum of the elements from the subset or on this norm and the cardinality of the subset. It is proved that, if the dimension of the space is a part of the input, then all these problems are strongly $\mathrm{NP}$-hard. Additionally, it is shown that, if the space dimension is fixed, then all the problems are $\mathrm{NP}$-hard even for dimension $2$ (on a plane) and there are no approximation algorithms with a guaranteed accuracy bound for them unless $\mathrm{P=NP}$. It is shown that, if the coordinates of the input points are integer, then all the problems can be solved in pseudopolynomial time in the case of a fixed space dimension. 
@article{ZVMMF_2016_56_10_a13,
     author = {A. V. Eremeev and A. V. Kel'manov and A. V. Pyatkin},
     title = {On the complexity and approximability of some {Euclidean} optimal summing problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1831--1836},
     year = {2016},
     volume = {56},
     number = {10},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_10_a13/}
}
TY  - JOUR
AU  - A. V. Eremeev
AU  - A. V. Kel'manov
AU  - A. V. Pyatkin
TI  - On the complexity and approximability of some Euclidean optimal summing problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2016
SP  - 1831
EP  - 1836
VL  - 56
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_10_a13/
LA  - ru
ID  - ZVMMF_2016_56_10_a13
ER  - 
%0 Journal Article
%A A. V. Eremeev
%A A. V. Kel'manov
%A A. V. Pyatkin
%T On the complexity and approximability of some Euclidean optimal summing problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2016
%P 1831-1836
%V 56
%N 10
%U http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_10_a13/
%G ru
%F ZVMMF_2016_56_10_a13
A. V. Eremeev; A. V. Kel'manov; A. V. Pyatkin. On the complexity and approximability of some Euclidean optimal summing problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 10, pp. 1831-1836. http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_10_a13/

[1] Kelmanov A. V., Khamidullin S. A., Kelmanova M. A., “Sovmestnoe obnaruzhenie i otsenivanie povtoryayuschegosya fragmenta v zashumlennoi chislovoi posledovatelnosti pri zadannom chisle kvaziperiodicheskikh povtorov”, Diskretnyi analiz i issledovanie operatsii, Tez. dokl. Rossiiskoi konf. DAOR-4 (Novosibirsk, 2004), 185

[2] Gimadi E. Kh., Kelmanov A. V., Kelmanova M. A., Khamidullin S. A., “Aposteriornoe obnaruzhenie v chislovoi posledovatelnosti kvaziperiodicheskogo fragmenta pri zadannom chisle povtorov”, Sib. zhurnal industr. matem., 9:1(25) (2006), 55–74

[3] Baburin A. E., Gimadi E. Kh., Glebov N. I., Pyatkin A. V., “Zadacha otyskaniya podmnozhestva vektorov s maksimalnym summarnym vesom”, Diskretnyi analiz i issledovanie operatsii. Ser. 2, 14:1 (2007), 32–42 | Zbl

[4] Gimadi E. Kh., Kel'manov A. V., Kel'manova M. A., Khamidullin S. A., “A posteriori detecting a quasiperiodic fragment in a numerical sequence”, Pattern Recognit. and Image Analysis, 18:1 (2008), 30–42 | DOI | MR

[5] Kelmanov A. V., Pyatkin A. V., “O slozhnosti odnogo iz variantov zadachi vybora podmnozhestva “pokhozhikh” vektorov”, Dokl. RAN, 421:5 (2008), 590–592 | Zbl

[6] Kelmanov A. V., Pyatkin A. V., “Ob odnom variante zadachi vybora podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 15:5 (2008), 20–34

[7] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh zadach vybora podposledovatelnosti vektorov”, Zh. vychisl. matem. i matem. fiz., 52:12 (2012), 2284–2291 | Zbl

[8] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh zadach klasternogo analiza vektornykh posledovatelnostei”, Diskretnyi analiz i issledovanie operatsii, 20:2 (2013), 47–57 | MR

[9] Kadets M. I., “Ob odnom svoistve vektornykh lomanykh v $n$-mernom prostranstve”, Uspekhi matem. nauk, 8:1 (1953), 139–143 | MR | Zbl

[10] Pyatkin A. V., “O slozhnosti zadachi vybora podmnozhestva vektorov maksimalnoi summarnoi dliny”, Diskretnyi analiz i issledovanie operatsii, 16:6 (2009), 68–73 | Zbl

[11] Vazirani V. V., Approximation algorithms, Springer, New York, 2001

[12] Baburin A. E., Pyatkin A. V., “O polinomialnykh algoritmakh resheniya odnoi zadachi summirovaniya vektorov”, Diskretnyi analiz i issledovanie operatsii. Seriya 1, 13:2 (2006), 3–10 | MR

[13] Gimadi E. Kh., Glazkov Yu. V., Rykov I. A., “O dvukh zadachakh vybora podmnozhestva vektorov s tselochislennymi koordinatami v evklidovom prostranstve s maksimalnoi normoi summy razmernosti”, Diskretnyi analiz i issledovanie operatsii, 15:4 (2008), 30–43 | MR | Zbl

[14] Sevastyanov S. V., “O zadache kompaktnogo summirovaniya vektorov”, Metody diskretnogo analiza v reshenii ekstremalnykh zadach, Sb. trudov In-ta matem. SO RAN, Izd-vo IM SO RAN, Novosibirsk, 1979, 77–89

[15] Sevastyanov S. V., Geometricheskie metody i effektivnye algoritmy v teorii raspisanii, Dis. ... dokt. fiz.-matem. nauk, In-t matem. SO RAN, Novosibirsk, 2000, 283 pp.

[16] Borisovsky P. A., Eremeev A. V., Grinkevich E. B., Klokov S. A., Vinnikov A. V., “Trading hubs construction for electricity markets”, Optimizat. Energy Industry, eds. Kallrath J., Pardalos P. M., Rebennack S., Scheidt M., Springer, Berlin, 2009, 29–58 | DOI | MR

[17] Garey M. R., Johnson D. S., Computers and intractability: A guide to the theory of NP-Completeness, Freeman, San Francisco, 1979, 314 pp. | MR | Zbl