List of Selected Publications
(See also complete version including Japanese)

DBLP
Google Scholar

Journals

  1. Miyazaki, S. and Iwama, K.
    Approximation of coNP Sets by NP-complete Sets and Its Applications
    Systems and Computers in Japan, Vol. 30, No. 7, pp.47-54. June, 1999.

  2. Manlove, D. F., Irving, R. W., Iwama, K., Miyazaki, S. and Morita, Y.
    Hard Variants of Stable Marriage
    Theoretical Computer Science, Vol. 276, Issue 1-2, pp. 261-279, April, 2002.

  3. Halldorsson, M. M., Iwama, K., Miyazaki, S. and Taketomi, S.
    Online Independent Sets
    Theoretical Computer Science, Vol. 289, Issue 2, pp. 953-962, October, 2002.

  4. Iwama, K., Kawai, D., Miyazaki, S., Okabe, Y. and Umemoto, J.
    Parallelizing Local Search for CNF Satisfiability Using Vectorization and PVM
    The ACM Journal of Experimental Algorithmics, Volume 7, Article 2, 2002.

  5. Halldorsson, M. M., Irving, R. W., Iwama, K., Manlove, D. F., Miyazaki, S., Morita, Y. and Scott, S.
    Approximability Results for Stable Marriage Problems with Ties
    Theoretical Computer Science, Vol. 306, pp. 431-447, Sept. 2003.

  6. Halldorsson, M. M., Iwama, K., Miyazaki, S. and Yanagisawa, H.,
    Randomized Approximation of the Stable Marriage Problem
    Theoretical Computer Science, Vol. 325, No. 3, pp. 439-465, Oct., 2004.

  7. Iwama, K., Miyazaki, S. and Okamoto, K.
    A (2-c log N/N)-Approximation Algorithm for the Stable Marriage Problem
    IEICE TRANSACTIONS on Information and Systems, Volume E89-D No.8
    pp.2380-2387, August 2006.

  8. Halldorsson, M. M., Iwama, K., Miyazaki, S. and Yanagisawa, H.
    Improved Approximation Results for the Stable Marriage Problem
    ACM Transactions on Algorithms, Vol. 3, Issue 3, Article No. 30, Aug., 2007.

  9. Iwama, K., Miyazaki, S. and Yamauchi, N.
    A (2-c 1 / \sqrt{N})-Approximation Algorithm for the Stable Marriage Problem
    Algorithmica, Volume 51, Issue 3, pp. 902-914, July 2008.

  10. Koji Kobayashi, Shuichi Miyazaki and Yasuo Okabe,
    A Tight Bound on Online Buffer Management for Two-Port Shared-Memory Switches
    IEICE TRANSACTIONS on Information and Systems, Volume E91-D No.8
    pp.2105-2114, August 2008.

  11. Koji Kobayashi, Shuichi Miyazaki and Yasuo Okabe,
    A Tight Upper Bound on Online Buffer Management for Multi-Queue Switches with Bicodal Buffers
    IEICE TRANSACTIONS on Information and Systems, Volume E91-D No.12
    pp.2757-2769, December 2008.

  12. Naoyuki Kamiyama, Yuuki Kiyonari, Eiji Miyano, Shuichi Miyazaki, and Katsuhisa Yamanaka
    Computational Complexities of University Interview Timetabling
    IEICE TRANSACTIONS on Information and Systems, Volume E92-D No.2
    pp.130-140, February 2009.

  13. Shuichi Miyazaki and Kazuya Okamoto,
    Improving the Competitive Ratio of the Online OVSF Code Assignment Problem,
    MDPI Algorithms, Vol. 2, Issue 3, pp. 953-972, July 2009.

  14. Hamada, K., Iwama, K. and Miyazaki, S.
    An Improved Approximation Lower Bound for Finding Almost Stable Maximum Matchings
    Information Processing Letters, Vol.109, Issue 18, pp. 1036-1040 , August 2009.

  15. S. Miyazaki, N. Morimoto and Y. Okabe
    The Online Graph Exploration Problem on Restricted Graphs
    IEICE TRANSACTIONS on Information and Systems, Volume E92-D No.9
    pp.1620-1627, September 2009.

  16. Asahiro, Y., Miyano, E., Miyazaki, S. and Yoshimuta, T.
    Weighted Nearest Neighbor Algorithms for the Graph Exploration Problem on Cycles
    Information Processing Letters, Vol.110, Issue 3, pp. 93-98, January 2010.

  17. Iwama, K., Miyazaki, S. and Yanagisawa, H.
    Approximation Algorithms for the Sex-Equal Stable Marriage Problem
    ACM Transactions on Algorithms, Vol. 7, Issue 1, Article No. 2, November 2010.

  18. Iwama, K., Miyazaki, S. and Yanagisawa, H.
    Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects
    Journal of Discrete Algorithms, Vol. 13, pp. 59-66, May 2012.

  19. Takao Inoshita, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, Takashi Nagase
    Improving Man-Optimal Stable Matchings by Minimum Change of Preference Lists
    MDPI Algorithms, Vol. 6, Issue 2, pp. 371-382, May 2013.

  20. Iwama, K., Miyazaki, S. and Yanagisawa, H.
    A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
    Algorithmica, Volume 68, Issue 3, pp. 758-775, March 2014.

  21. Miyazaki, S.
    On the Advice Complexity of Online Bipartite Matching and Online Stable Marriage
    Information Processing Letters, Vol.114, Issue 12, pp. 714-717, December 2014.

  22. Minseon Lee, Shuichi Miyazaki, and Kazuo Iwama,
    Finding Witnesses for Stability in the Hospitals/Residents Problem,
    Journal of Information Processing, Vol. 23, No. 2, pp. 202-209, March 2015.

  23. Hamada, K., Iwama, K. and Miyazaki, S.
    The Hospitals/Residents Problem with Lower Quotas,
    Algorithmica, Volume 74, Issue 1, pp. 440-465, January 2016.

  24. Jun Kawahara, Koji M. Kobayashi, and Shuichi Miyazaki,
    Better Bounds for Online k-frame Throughput Maximization in Network Switches
    Theoretical Computer Science, Vol. 657, pp. 173-190, January, 2017.

  25. Koji M. Kobayashi, Shuichi Miyazaki, and Yasuo Okabe,
    Competitive Buffer Management for Multi-queue Switches in QoS Networks Using Packet Buffering Algorithms
    Theoretical Computer Science, Vol. 675, pp. 27-42, May, 2017.

Conferences and Workshops

  1. Iwama, K. and Miyazaki, S.,
    SAT-Variable Complexity of Hard Combinatorial Problems
    Proceedings of the IFIP 13th World Computer Congress, Vol.1, pp. 253-258, 1994. (Hamburg, Germany)

  2. Iwama, K. and Miyazaki, S.
    Approximation of coNP Sets by NP-complete Sets
    Proc. the First Annual International Computing and Combinatorics Conference (COCOON'95)
    (Lecture Notes in Computer Science 959)
    pp.11-20, 1995. (Xi'an, China)

  3. Miyazaki, S., Iwama, K. and Kambayashi, Y.,
    Database Queries as Combinatorial Optimization Problems
    Proc. International Symposium on Cooperative Database Systems for
    Advanced Applications (CODAS'96), pp.448-454, 1996. (Kyoto, Japan)

  4. Cha, B., Iwama, K., Kambayashi, Y. and Miyazaki, S.
    Local Search Algorithms for Partial MAXSAT
    Proc. Fourteenth National Conference on Artificial Intelligence (AAAI 97)
    pp. 263-268, Jul, 1997. (Providence, USA)

  5. Iwama, K., Manlove, D. F., Miyazaki, S. and Morita, Y.
    Stable Marriage with Incomplete Lists and Ties
    Proc. 26th International Colloquium on Automata, Languages, and Programming (ICALP'99)
    (Lecture Notes in Computer Science 1644),
    pp. 443-452, July, 1999. (Prague, Czech Republic)

  6. Iwama, K. and Miyazaki, S.
    Tree-Like Resolution Is Superpolynomially Slower Than DAG-Like Resolution for the Pigeonhole Principle
    Proc. 10th International Symposium on Algorithms and Computation (ISAAC'99)
    (Lecture Notes in Computer Science 1741), pp. 133-142, Dec., 1999. (Madras, India)

  7. Halldorsson, M. M., Iwama, K., Miyazaki, S. and Taketomi, S.
    Online Independent Sets
    Proceedings of the Sixth Annual International Computing and Combinatorics Conference (COCOON 2000 )
    (Lecture Notes in Computer Science 1858),
    pp. 202-209, July 2000. (Sydney, Australia)

  8. Iwama, K., Kawai, D., Miyazaki, S., Okabe, Y. and Umemoto, J.
    Parallelizing Local Search for CNF Satisfiability Using PVM
    Proc. The AAAI-2000 workshop on parallel and distributed search for reasoning , July 2000. (Austin, USA)

  9. Iwama, K., Kawai, D., Miyazaki, S., Okabe, Y. and Umemoto, J.
    Parallelizing Local Search for CNF Satisfiability Using Vectorization and PVM
    Proc. Workshop on Algorithm Engineering (WAE 2000),
    (Lecture Notes in Computer Science 1982),
    pp.123-134, Sept., 2000. (Saarbrucken, Germany)

  10. Halldorsson, M. M., Iwama, K., Miyazaki, S. and Morita, Y.
    Inapproximability Results on Stable Marriage Problems
    Proc. 5th Latin American Theoretical INformatics (LATIN 2002)
    (Lecture Notes in Computer Science 2286)
    pp. 554-568, April 2002. (Cancun, Mexico)

  11. Halldorsson, M. M., Iwama, K., Miyazaki, S. and Yanagisawa, H.
    Randomized Approximation of the Stable Marriage Problem
    Proceedings of the ninth Annual International Computing and Combinatorics Conference (COCOON 2003)
    (Lecture Notes in Computer Science 2697)
    pp. 339-350, July 2003. (Big Sky, USA)

  12. Halldorsson, M. M., Iwama, K., Miyazaki, S. and Yanagisawa, H.
    Improved Approximation of the Stable Marriage Problem
    Proceedings of the 11th Annual European Symposium on Algorithms (ESA 2003)
    (Lecture Notes in Computer Science 2832)
    pp. 266-277, Sep. 2003. (Budapest, Hungary)

  13. Iwama, K., Miyazaki, S. and Okamoto, K.
    A (2-c log N/N)-Approximation Algorithm for the Stable Marriage Problem
    Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT 2004)
    (Lecture Notes in Computer Science 3111)
    pp. 349-361, July 2004. (Humlebaek, Denmark)

  14. Iwama, K., Miyazaki, S. and Yamauchi, N.
    A (2-c 1 / \sqrt{N})-Approximation Algorithm for the Stable Marriage Problem
    Proc. 16th International Symposium on Algorithms and Computation (ISAAC 2005)
    (Lecture Notes in Computer Science 3827),
    pp. 902-914, Dec., 2005. (Sanya, Hainan, China)

  15. Kato, S., Miyazaki, S., Nishimura, Y. and Okabe, Y.
    Cheat-proof Serverless Network Games
    5th International Conference on Computers and Games (CG 2006)
    (Lecture Notes in Computer Science 4630),
    pp. 234-243, May 2006. (Turin, Italy)

  16. Kiyonari, Y., Miyano, E. and Miyazaki, S.
    Computational Complexity Issues in University Interview Timetabling
    Proc. of The 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2006).
    pp. 448-453, August 2006. (Brno, Czech Republic)

  17. Iwama, K., Miyazaki, S. and Yamauchi, N.
    A 1.875-Approximation Algorithm for the Stable Marriage Problem
    Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)
    pp. 288-297, Jan., 2007. (New Orleans, USA)

  18. Asahiro, Y., Miyano, E., Miyazaki, S. and Yoshimuta, T.
    Weighted Nearest Neighbor Algorithms for the Graph Exploration Problem on Cycles
    Proc. 33rd Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2007)
    (Lecture Notes in Computer Science 4362),
    pp. 164-175, Jan., 2007. (Harrachov, Czech Republic)

  19. Koji Kobayashi, Shuichi Miyazaki, Yasuo Okabe
    A Tight Bound on Online Buffer Management for Two-port Shared-Memory Switches
    Proc. 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2007)
    pp. 358-364, June 2007. (San Diego, USA)

  20. Iwama, K., Miyazaki, S. and Yanagisawa, H.,
    Approximation Algorithms for the Sex-Equal Stable Marriage Problem
    Proc. 10th Workshop on Algorithms and Data Structures (WADS 2007)
    (Lecture Notes in Computer Science 4619),
    pp. 201-213, Aug., 2007. (Halifax, Canada)

  21. Toshihiro Takagi, Takaaki Komura, Shuichi Miyazaki and Yasuo Okabe,
    Privacy Oriented Attribute Exchange in Shibboleth Using Magic Protocols
    The 2008 International Symposium on Applications and the Internet (SAINT 2008)
    Workshop on Middleware Architecture in the Internet, pp. 293-296
    August 2008. (Turku, Finland)

  22. Miyazaki, S. and Okamoto, K.
    Improving the Competitive Ratio of the Online OVSF Code Assignment Problem
    Proc. 19th International Symposium on Algorithms and Computation (ISAAC 2008)
    (Lecture Notes in Computer Science 5369),
    pp. 64-76, Dec. 2008. (Gold Coast, Australia)

  23. Keita Shimizu, Shuichi Miyazaki, and Yasuo Okabe,
    Design and Implementation of a Certified Mail Exchange System Using Simultaneous Secret Exchange,
    The 2009 International Symposium on Applications and the Internet (SAINT 2009),
    pp. 37-42, July 2009. (Seattle, USA)

  24. Koji Kobayashi, Shuichi Miyazaki, Yasuo Okabe
    Competitive buffer management for multi-queue switches in qos networks using packet buffering algorithms
    Proc. 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2009)
    pp. 328-336, August 2009. (Calgary, Canada)

  25. Iwama, K., Miyazaki, S. and Yanagisawa, H.
    A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
    Proceedings of the 18th Annual European Symposium on Algorithms (ESA 2010)
    (Lecture Notes in Computer Science 6347)
    pp. 135-146, Sep. 2010. (Liverpool, UK)

  26. Miyazaki, S. and Okamoto, K.,
    Improving the Competitive Ratios of the Seat Reservation Problem
    Proceedings of the 6th IFIP TC1/WG2.2, International Conference (IFIP/TCS 2010)
    pp. 328-339, Sep., 2010. (Brisbane, Australia)

  27. Iwama, K., Miyazaki, S. and Yanagisawa, H.
    Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects
    Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011)
    (Lecture Notes in Computer Science 6648)
    pp. 440-451, May 2011. (Tokyo, Japan)

  28. Satoshi Ishibashi, Shuichi Miyazaki, and Yasuo Okabe,
    Design and Implementation of a Certified Document Delivery System without a Trusted Intermediate Authority,
    The 2011 International Symposium on Applications and the Internet (SAINT 2011),
    pp. 20-26, July 2011. (Munich, Germany)

  29. Hamada, K., Iwama, K. and Miyazaki, S.
    The Hospitals/Residents Problem with Quota Lower Bounds
    Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011)
    (Lecture Notes in Computer Science 6942)
    pp. 180-191, Sep., 2011. (Saarbrucken, Germany)

  30. Yoshiharu Tsuzaki, Ryosuke Matsumoto, Daisuke Kotani, Shuichi Miyazaki, Yasuo Okabe,
    A Mail Transfer System Selectively Restricting a Huge Amoount of E-mails
    Workshop on Resilient Internet based Systems (REIS 2013), pp. 896-900, Dec. 2013. (Kyoto, Japan)

  31. Jun Kawahara, Koji M. Kobayashi, Shuichi Miyazaki,
    Better Bounds for Online k-Frame Throughput Maximization in Network Switches,
    Proc. 24th International Symposium on Algorithms and Computation (ISAAC 2013)
    (Lecture Notes in Computer Science 8283),
    pp. 218-228, Dec., 2013. (Hong-Kong)

  32. Shuichi Miyazaki, Naoyuki Morimoto and Yasuo Okabe,
    Approximability of Two Variants of Multiple Knapsack Problems,
    Proc. 9th International Conference on Algorithms and Complexity (CIAC 2015)
    (Lecture Notes in Computer Science 9079),
    pp. 365-376, May, 2015. (Paris, France)

  33. Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa,
    A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties,
    Proc. the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015),
    pp. 361-380, August 2015. (Princeton, USA)

  34. Sushmita Gupta, Kazuo Iwama, and Shuichi Miyazaki
    Total Stability in Stable Matching Games
    Proc. the 15th Scandinavian Symposium and Workshops on Algorithm Theory, (SWAT 2016),
    pp. 23:1-23:12, June 2016. (Reykjavik, Iceland)

  35. Yoshiyuki Mihara, Shuichi Miyazaki, Yasuo Okabe, Tetsuya Yamaguchi, and Manabu Okamoto
    Identifying Link Layer Home Network Topologies Using HTIP,
    14th Annual IEEE Consumer Communications & Networking Conference (CCNC 2017),
    pp. 892-899, Jan. 2017. (Las Vegas, USA)

Technical Reports

  1. Manlove, D. F., Irving, R. W., Iwama, K., Miyazaki, S. and Morita, Y.
    Hard Variants of Stable Marriage
    Technical Report no. TR-1999-43 of the Computing Science Department of Glasgow University,
    Sept., 1999.

  2. Halldorsson, M. M., Irving, R. W., Iwama, K., Manlove, D. F., Miyazaki, S., Morita, Y. and Scott, S.
    Approximability Results for Stable Marriage Problems with Ties
    Technical Report TR-2002-121 of the Computing Science Department of Glasgow University,
    October, 2002.

  3. K. Iwama, S. Miyazaki, and H. Yanagisawa,
    A 25/17-approximation Algorithm for the Stable Marriage Problem with One-sided Ties,
    IBM Research Report RT0913, 2010.

Book Chapters

  1. Iwama, K. and Miyazaki, S.
    Stable Marriage with Ties and Incomplete Lists
    Encyclopedia of Algorithms, Springer, pp. 883-885, June 2008.

  2. Shuichi Miyazaki, "Stable Marriage Problem",
    Chapter 17 of Handbook of Graph Theory, Combinatorial Optimization, and Algorithms,
    Editted by Krishnaiyan "KT" Thulasiraman, Subramanian Arumugam, Andreas Brandstadt, and Takao Nishizeki,
    CRC Press, pp. 403-418, December 2015.

  3. Iwama, K. and Miyazaki, S.
    Stable Marriage with Ties and Incomplete Lists
    Encyclopedia of Algorithms (2nd Edition), Springer, pp. 2071-2075, May 2016.