Yongho Shin

신용호 (yongho {at} cs {dot} uni {dot} wroc {dot} pl) [CV, last updated: Nov 2024]

Hi! I am a postdoctoral researcher at the Institue of Computer Science, University of Wrocław, mentored by Prof. Jarek Byrka. I received my Ph.D. degree in Computer Science from Yonsei University, advised by Prof. Hyung-Chan An. I received my B.S. degree in Computer Science from Yonsei University.

My major research interests belong to theoretical computer science. I am particularly interested in (but not limited to) online/approximation algorithms for combinatorial optimization problems.

I am eager to convey theoretical aspects of computer science to others, specifically in Korean. To this end, I am running a blog where I post several related topics including basics to recent work. Visit my blog 「Gazelle and Computer Science」 (in Korean) if interested.

I am a member of Yonsei CS theory student group. The group organizes seminar talks on the regular basis in order to study various interesting topics of theoretical computer science and to let people socialize and collaborate more easily. The group is open to any TCS lovers; contact me (or other organizers) if interested.

Research Papers

Journal Papers

• K. Kim, Y. Shin, and H.-C. An. Constant-factor approximation algorithms for parity-constrained facility location and k-center. Algorithmica 85, pages 1883–1911, 2023. [Link]

Conference Papers

• Y. Shin, C. Lee, G. Lee, and H.-C. An. Improved learning-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis. In ICML 2023: Proceedings of the 40th International Conference on Machine Learning, PMLR 202, pages 31539-31561, 2023. [Link]
• Y. Shin and H.-C. An. Making three out of two: Three-way online correlated selection. In ISAAC 2021: Proceedings of the 32nd International Symposium on Algorithms and Computation, pages 49:1-49:17, 2021. [Link]
• K. Kim, Y. Shin, and H.-C. An. Constant-factor approximation algorithms for the parity-constrained facility location problem. In ISAAC 2020: Proceedings of the 31st International Symposium on Algorithms and Computation, pages 21:1-21:17, 2020. [Link]

Preprints

• Y. Shin, C. Lee, and H.-C. An. On optimal consistency-robustness trade-off for learning-augmented multi-option ski rental. arXiv preprint arXiv:2312.02547, 2023. [Link]
• Y. Shin, K. Kim, S. Lee, and H.-C. An. Online graph matching problems with a worst-case reassignment budget. arXiv preprint arXiv:2003.05175, 2020. [Link]

Awards

• High honors at graduation, Yonsei University, 2018.

Research Experience

• Intern, Cornell University, Sept 2022 - Dec 2022.
  • Director: Prof. David Shmoys
• Undergraduate intern, Yonsei University, Feb 2017 - Feb 2018.
  • Advisor: Prof. Hyung-Chan An

Teaching Experience

• Teaching assistant, Yonsei University.
  • CSI2103/CCO2103 Data Structures, Spring 2018-2021, 2023, 2024.
  • CSI3108 Algorithm Analysis, Fall 2018-2021, 2023.
  • AIC2130 Computer Algorithms for AI Applications, Fall 2023.
  • GEK6205 Design and Analysis of Optimization Algorithms, Fall 2023.

• Undergraduate voluntary tutor, Yonsei University.
  • CSI3108 Algorithm Analysis, Fall 2016, 2017.
  • CSI2103 Data Structures, Spring 2017.

Other Experience

• Co-organizer of Yonsei CS theory student group, Yonsei University, Jan 2023 - Feb 2024.
• Web programmer, Republic of Korea Air Force, Nov 2013 - Aug 2015.