The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye

Michael A. Bender, Ritwik Bose, Rezaul Alam Chowdhury, Samuel McCauley

Abstract

This paper introduces the kissing problem: given a rectangular room with n people in it, what is the most efficient way for each pair of people to kiss each other goodbye? The room is viewed as a set of pixels that form a subset of the integer grid. At most one person can stand on a pixel at once, and people move horizontally or vertically. In order to move into a pixel in time step t, the pixel must be empty in time step t − 1. The paper gives one algorithm for kissing everyone goodbye. (1) This algorithm is a 4 + o(1)-approximation algorithm in a crowded room (e.g., only one unoccupied pixel). (2) It is a 10 + o(1)-approximation algorithm for kissing in a comfortable room (e.g., at most half the pixels are empty). (3) It is a 25+o(1)-approximation for kissing in a sparse room.
BibTeX
@inproceedings{bender2014kissing,
  author = {Michael A. Bender and Ritwik Bose and Rezaul Alam Chowdhury and Samuel McCauley},
  title = {{The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye}},
  booktitle = {Theory Comput. Syst},
  year = {2014},
  url = {https://openreview.net/forum?id=_2n26Ptyte},
}

Loading related content...

Figure