Matematicheskie Zametki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Zametki:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Matematicheskie Zametki, 2001, Volume 70, Issue 6, Pages 845–853
DOI: https://doi.org/10.4213/mzm797
(Mi mzm797)
 

This article is cited in 1 scientific paper (total in 1 paper)

The Frobenius Problem for Classes of Polynomial Solvability

I. D. Kan

M. V. Lomonosov Moscow State University
Full-text PDF (200 kB) Citations (1)
References:
Abstract: The Frobenius problem is to find a method ($=$ algorithm) for calculating the largest “sum of money” that cannot be given by coins whose values $b_0,b_1,\dots,b_w$ are coprime integers. As admissible solutions (algorithms), it is common practice to study polynomial algorithms, which owe their name to the form of the dependence of time expenditure on the length of the original information. The difficulty of the Frobenius problem is apparent from the fact that already for $w=3$ the existence of a polynomial solution is still an open problem. In the present paper, we distinguish some classes of input data for which the problem can be solved polynomially; nevertheless, argumentation in the spirit of complexity theory of algorithms is kept to a minimum.
Received: 20.03.2000
Revised: 25.12.2000
English version:
Mathematical Notes, 2001, Volume 70, Issue 6, Pages 771–778
DOI: https://doi.org/10.1023/A:1012907800738
Bibliographic databases:
UDC: 511.216+511.218
Language: Russian
Citation: I. D. Kan, “The Frobenius Problem for Classes of Polynomial Solvability”, Mat. Zametki, 70:6 (2001), 845–853; Math. Notes, 70:6 (2001), 771–778
Citation in format AMSBIB
\Bibitem{Kan01}
\by I.~D.~Kan
\paper The Frobenius Problem for Classes of Polynomial Solvability
\jour Mat. Zametki
\yr 2001
\vol 70
\issue 6
\pages 845--853
\mathnet{http://mi.mathnet.ru/mzm797}
\crossref{https://doi.org/10.4213/mzm797}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1887251}
\zmath{https://zbmath.org/?q=an:1037.11017}
\transl
\jour Math. Notes
\yr 2001
\vol 70
\issue 6
\pages 771--778
\crossref{https://doi.org/10.1023/A:1012907800738}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000173100200021}
Linking options:
  • https://www.mathnet.ru/eng/mzm797
  • https://doi.org/10.4213/mzm797
  • https://www.mathnet.ru/eng/mzm/v70/i6/p845
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математические заметки Mathematical Notes
    Statistics & downloads:
    Abstract page:473
    Full-text PDF :246
    References:60
    First page:1
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024