@MISC{PRSUBSET.MIZ,
  AUTHOR = {Fujiwara, Hiroshi and Watari, Hokuto and Yamamoto, Hiroaki},
  TITLE = {Dynamic Programming for the Subset Sum Problem},
  NOTE = {This work was supported by KAKENHI (16K00033, 17K00013, and
                  17K00183).},
  ACKNOWLEDGEMENT = {We are very grateful to Prof. Yasunari Shidama
                  for his encouraging support.  We thank Prof. Pauline
                  N. Kawamoto, Dr. Hiroyuki Okazaki, and Dr. Hiroshi
                  Yamazaki for their helpful discussions.},
  SECTION1 = {Recurrence Relation of Dynamic Programming for the Subset Sum Problem},
  DAY = {13},
  MONTH = {January},
  YEAR = {2020},
  ADDRESS1 = {Shinshu University\\Nagano, Japan},
  ADDRESS2 = {Nagano Electronics Industrial Co., Ltd.\\Chikuma, Japan},
  ADDRESS3 = {Shinshu University\\Nagano, Japan},
  KEYWORDS = {dynamic programming; algorithm; subset sum problem;
                  complexity theory},
  SUMMARY = {The subset sum problem is a basic problem in the field of
                  theoretical computer science.  The input is a
                  sequence of positive integers and a target positive
                  integer.  The task is to determine if there exists a
                  subsequence of the input sequence with sum equal to
                  the target integer.  It is known that the problem is
                  NP-hard~\cite{Karp1972} and can be solved by dynamic
                  programming in pseudo-polynomial
                  time~\cite{Garey:1979:CIG:578533}.  In this article
                  we formalize the recurrence relation of the dynamic
                  programming.}}

@book{Garey:1979:CIG:578533,
 author = {Garey, M. R. and Johnson, D. S.},
 title = {Computers and Intractability: A Guide to the Theory of NP-Completeness},
 year = {1979},
 isbn = {0716710447},
 publisher = {W. H. Freeman \& Co.},
 address = {New York, NY, USA},
}
@inproceedings{Karp1972,
author="Karp, R. M.",
title="Reducibility among Combinatorial Problems",
year="1972",
pages="85--103",
isbn="978-1-4684-2001-2",
doi="10.1007/978-1-4684-2001-2_9",
url="https://doi.org/10.1007/978-1-4684-2001-2_9",
publisher="Springer US",
crossref  = "Complexity"
}
@proceedings{Complexity,
editor="Miller, R. E.
and Thatcher, J. W.
and Bohlinger, J. D.",
title="Complexity of Computer Computations",
booktitle="Complexity of Computer Computations",
year="1972",
publisher="Springer US",
pages="85--103",
isbn="978-1-4684-2001-2",
doi="10.1007/978-1-4684-2001-2_9",
url="https://doi.org/10.1007/978-1-4684-2001-2_9"
}
