이 글에서는 cost function이 metric인 경우에 대해서만 논의한다.

이 글에서는 parallelism과 관련하여 최근에 제시된 두 계산 모델에 대해 간단히 알아본다. 또한, 그 계산 모델 상에서 돌아가는 잘 알려진 (그러면서도 이론적으로 중요한) 문제에 대한 알고리즘 및 계산 이론적 결과를 알아본다.

본인은 최근 들어 Theoretical Computer Science 분야 중에서도 Computational Hardness에 관련한 결과들을 다루는 스터디에 참여하고 있고, Unique Games Conjecture와 관련하여 발표할 일이 있었다. 나름 의미가 있는 주제임에도 불구하고, 이와 관련한 국문 자료는 (본인이 검색해본 한에서는) 전혀 찾아볼 수 없었어서 이 글을 작성하게 되었다.

이 글은 L. Cai와 C. Thomas의 논문 The Short-Side Advantage in Random Matching Markets 의 결과를 간략하게 정리한 것이다.

1. 서론

1. Introduction

1. 2-SAT 문제란?

이 글에서는 Pinyan Lu 외 3인의 논문 “Generalized Sorting with Predictions”에 대해 소개합니다. (글이 발행된 이후에 koosaga님의 project_tcs에 영상 및 자료가 올라갈 예정입니다.)

이 글에서는 매트로이드 상에서의 submodular maximization과 관련한 여러 연구의 결과들을 소개합니다. 보다 구체적으로는, 매트로이드와 submodular function 등 여러 개념의 정의를 소개하고, 매트로이드 상에서 submodular function을 최적화 하는 것이 실생활의 어떤 문제에 관련이 있는지 먼저 살펴봅니다. 그 후, 이 문제와 관련한 여러 연구 결과들을 살펴봅니다. 특히, 그 중에서도 (이 글에서는) 결정론적인 알고리즘들을 다룹니다.