(See also complete version including Japanese)

Google Scholar

- 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.

- 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) - 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) - 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) - 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)

- 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.

- 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,

Editted 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.