The kissing problem: How to end a gathering when everyone kisses everyone else goodbye

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 45 + 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 (more than half the pixels are empty) with two people abutting the far walls of the room. This paper gives optimal solutions for small cases, which were found using a heuristic state space search (IDA*).