Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Polynomial in time nonnegative integer solutions of knapsacks and similar problems in R: P=NP?
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2018 (Engelska)Ingår i: Mathematical Journal, ISSN 1682-0525, Vol. 18, nr 2, s. 47-58Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

A new result is the well forgotten old one"(A Russian proverb) Annotation. An R-package "nilde" [1] for the enumeration of all existing nonnegative integer solutions of linear Diophantine equations and inequalities and related problems is presented. The software uses the approach based on a generating function of Hardy and Littlewood [2] introduced in 1966 and the algorithm proposed by Voinov and Nikulin [3] in 1997. The package proves to be useful for solving 0-1, bounded and unbounded knapsacks, subset sum problems, integer linear programs, partitioning of natural numbers, etc. The main advantage of the proposed software is that it solves all the above problems in polynomial time. Numerous examples illustrate applications of the package. Strong theoretical and empirical arguments in favor of equality P=NP are presented.

Ort, förlag, år, upplaga, sidor
2018. Vol. 18, nr 2, s. 47-58
Nationell ämneskategori
Naturvetenskap Sannolikhetsteori och statistik
Identifikatorer
URN: urn:nbn:se:umu:diva-160058OAI: oai:DiVA.org:umu-160058DiVA, id: diva2:1323507
Tillgänglig från: 2019-06-12 Skapad: 2019-06-12 Senast uppdaterad: 2019-06-13Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

https://www.researchgate.net/profile/Vassilly_Voinov/publication/327135851_POLYNOMIAL_IN_TIME_NONNEGATIVE_INTEGER_SOLUTIONS_OF_KNAPSACKS_AND_SIMILAR_PROBLEMS_IN_R_PNP/links/5b7ba50c4585151fd123e757/POLYNOMIAL-IN-TIME-NONNEGATIVE-INTEGER-SOLUTIONS-OF-KNAPSACKS-AND-SIMILAR-PROBLEMS-IN-R-PNP.pdf?origin=publication_detail

Person

Pya Arnqvist, Natalya

Sök vidare i DiVA

Av författaren/redaktören
Pya Arnqvist, Natalya
Av organisationen
Institutionen för matematik och matematisk statistik
NaturvetenskapSannolikhetsteori och statistik

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 319 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf