The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye
Coauthors: Michael A. Bender, Ritwik Bose, and Rezaul Chowdhury
We introduce the kissing problem: given a rectangular room
with n people in it, what is the most efficient way to schedule
movements so that each pair of peoples kisses 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.
We 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.