A meeting scheduling problem respecting time and space |
| |
Authors: | Florian Berger Rolf Klein Doron Nussbaum Jörg-Rüdiger Sack Jiehua Yi |
| |
Affiliation: | (1) Institute of Computer Science, University of Bonn, 53117 Bonn, Germany;(2) School of Computer Science, Carleton University, Ottawa, Canada, K1S 5B6 |
| |
Abstract: | We consider the problem of determining suitable meeting times and locations for a group of participants wishing to schedule
a new meeting subject to already scheduled meetings possibly held at a number of different locations. Each participant must
be able to reach the new meeting location, attend for the entire duration, and reach the next meeting location on time. In
particular, we give two solutions to the problem instance where each participant has two scheduled meetings separated by a
free time interval. We present an O(n logn) algorithm for n participants obtained by purely geometrical arguments. Our second approach uses the concept of LP-type problems and leads
to a randomized algorithm with expected running time O(n). We also consider a graph-based model where participants belong to different groups and can travel along the edges of a
graph. For the meeting, only one member out of each group is required. The resulting problem can be solved using furthest
color Voronoi diagrams on graphs.
|
| |
Keywords: | Geographic information system Computational geometry Algorithms Meeting schedule |
本文献已被 SpringerLink 等数据库收录! |
|