Publication list
List of Selected Publications
Journals
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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.Hamada, K., Iwama, K. and Miyazaki, S.
The Hospitals/Residents Problem with Lower Quotas,
Algorithmica, Volume 74, Issue 1, pp. 440-465, January 2016.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.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.Jose C. Nacher, Masayuki Ishitsuka, Shuichi Miyazaki, Tatsuya Akutsu,
Finding and analysing the minimum set of driver nodes required to control multilayer networks,
Scientific Reports, volume 9, Article number: 576, January 2019.Shuichi Miyazaki, Kazuya Okamoto,
Jointly Stable Matchings,
Journal of Combinatorial Optimization, Volume 38, Issue 2, pp. 646-665, August 2019.Takumu Shirayama, Takuto Shigemura, Yota Otachi, Shuichi Miyazaki, Ryuhei Uehara,
On Computational Complexity of Pipe Puzzles,
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences,
Vol. E102-A, No. 9, pp. 1134-1141, Sep. 2019.Yoshiyuki Mihara, Shuichi Miyazaki, Yasuo Okabe, Tetsuya Yamaguchi, Manabu Okamoto,
Identifying Link Layer Home Network Topologies Using HTIP,
IEICE TRANSACTIONS on Information and Systems,
Volume E103-D,No.03, pp. 566-577, March 2020.Yuki Matsuyama and Shuichi Miyazaki,
Hardness of Instance Generation with Optimal Solutions for the Stable Marriage Problem,
Journal of Information Processing, Vol. 29, pp. 166-173, February 2021.Koki Hamada, Shuichi Miyazaki, Kazuya Okamoto,
Strongly Stable and Maximum Weakly Stable Noncrossing Matchings,
Algorithmica, Volume 83, Issue 9, pp. 2678–2696, September 2021.Toshiya Itoh, Shuichi Miyazaki, and Makoto Satake,
Competitive Analysis for Two Variants of Online Metric Matching Problem,
Discrete Mathematics, Algorithms and Applications, Vol. 13, No. 06, 2150156, December 2021.Kazuo Iwama and Shuichi Miyazaki,
Marriage and Roommate,
International Journal of Foundations of Computer Science, Vol. 34, No. 07, pp. 853-873, November 2023.
Koki Hamada and Shuichi Miyazaki,
Refined Computational Complexities of Hospitals/Residents Problem with Regional Caps,
Theoretical Computer Science, Vol. 989, Article 114389, March, 2024.Tsubasa Harada, Toshiya Itoh, and Shuichi Miyazaki,
Capacity-insensitive Algorithms for Online Facility Assignment Problems on a Line,
Discrete Mathematics, Algorithms and Applications, Vol. 16, No. 05, 2350057, July 2024.
Conferences and Workshops
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, August-September 1994. (Hamburg, Germany)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, August 1995. (Xi'an, China)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, December 1996. (Kyoto, Japan)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)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)Shuichi Miyazaki, Kazuya Okamoto,
Jointly Stable Matchings,
Proc. 28th International Symposium on Algorithms and Computation (ISAAC 2017)
pp. 56:1-56:12, Dec., 2017. (Phuket, Thailand)Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki,
An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number,
Proc. the 30th International Workshop on Combinatorial Algorithms (IWOCA 2019),
(Lecture Notes in Computer Science 11638),
pp. 327-338, July 2019. (Pisa, Italy)Koki Hamada, Shuichi Miyazaki and Hiroki Yanagisawa,
Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists,
Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019)
pp. 9:1-9:14, Dec., 2019. (Shanghai, China)Koki Hamada, Shuichi Miyazaki and Kazuya Okamoto,
Strongly Stable and Maximum Weakly Stable Noncrossing Matchings,
Proc. the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020),
(Lecture Notes in Computer Science 12126),
pp. 304-315, June 2020. (Bordeaux, France, Online)Toshiya Itoh, Shuichi Miyazaki, and Makoto Satake,
Competitive Analysis for Two Variants of Online Metric Matching Problem,
Proc. the 14th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2020),
(Lecture Notes in Computer Science 12577),
pp. 486-498, December 2020. (Dallas, Texas, USA, Online)Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki, and Yu Yokoi,
Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties,
Proc. 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
pp. 31:1--31:20, March 2022. (Marseille, France, Online)Kazuhisa Makino, Shuichi Miyazaki, and Yu Yokoi,
Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas,
Proc. the 15th International Symposium on Algorithmic Game Theory (SAGT 2022),
(Lecture Notes in Computer Science 13584),
pp. 544-561, September 2022. (Colchester, UK)Koki Hamada, Shuichi Miyazaki,
Refined Computational Complexities of Hospitals/Residents Problem with Regional Caps,
Proc. the 28th International Computing and Combinatorics Conference (COCOON 2022),
(Lecture Notes in Computer Science 13595),
pp. 333–344, October 2022. (Shenzhen, China; attended online)Taro Abe, Yuya Higashikawa, and Shuichi Miyazaki,
Online Exploration of Rectilinear Polygons by Multiple Searchers,
33rd European Conference on Operational Research (EURO 2024), WD-25-1, July 2024. (Copenhagen, Denmark)
Technical Reports
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.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.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
Iwama, K. and Miyazaki, S.
Stable Marriage with Ties and Incomplete Lists
Encyclopedia of Algorithms, Springer, pp. 883-885, June 2008.Shuichi Miyazaki, "Stable Marriage Problem",
Chapter 17 of Handbook of Graph Theory, Combinatorial Optimization, and Algorithms,
Edited by Krishnaiyan "KT" Thulasiraman, Subramanian Arumugam, Andreas Brandstadt, and Takao Nishizeki,
CRC Press, pp. 403-418, December 2015.Iwama, K. and Miyazaki, S.
Stable Marriage with Ties and Incomplete Lists
Encyclopedia of Algorithms (2nd Edition), Springer, pp. 2071-2075, May 2016.Tsubasa Harada, Toshiya Itoh, Shigeo Matsubara, Shuichi Miyazaki, and Makoto Yokoo,
Mechanism Design for Mobility,
Chapter 10 of Advanced Mathematical Science for Mobility Society, pp. 187-215, March, 2024.