TY - GEN
T1 - The kissing problem
T2 - 6th International Conference on Fun with Algorithms, FUN 2012
AU - Bender, Michael A.
AU - Bose, Ritwik
AU - Chowdhury, Rezaul
AU - McCauley, Samuel
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84861969746
U2 - 10.1007/978-3-642-30347-0_6
DO - 10.1007/978-3-642-30347-0_6
M3 - Conference contribution
AN - SCOPUS:84861969746
SN - 9783642303463
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 28
EP - 39
BT - Fun with Algorithms - 6th International Conference, FUN 2012, Proceedings
Y2 - 4 June 2012 through 6 June 2012
ER -