The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye |
| |
Authors: | Michael A Bender Ritwik Bose Rezaul Chowdhury Samuel McCauley |
| |
Affiliation: | 1. Department of Computer Science, Stony Brook University, Stony Brook, NY, 11794-4400, USA 2. Tokutek, Inc., Lexington, MA, 02421, USA 3. Department of Computer Science, University of Rochester, Rochester, NY, 14627, USA
|
| |
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. - This algorithm is a 4+o(1)-approximation algorithm in a crowded room (e.g., only one unoccupied pixel).
- It is a 45+o(1)-approximation algorithm for kissing in a comfortable room (e.g., at most half the pixels are empty).
- 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*). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|