日時
2013年3月1日(金) 15:00 ～ 17:00
場所
東北大，東大理学部7号館007号室（地下１階）およびNIIでポリコム中継
15:00～
講演者
LAU Hoong Chuin 先生 (Singapore Management University)
タイトル
Dynamic Experience Management in Theme Parks via Coordination and Incentives
アブストラクト
Mobile computing has changed the way businesses engage with consumers. At the individual levels, smart mobile devices are equipped with GPS sensors that enable user locations to be tracked in real-time, which enable personalized location-based services to be provided. Consequently, there is an increasing trend toward use of mobile apps to plan and manage activities. At the corporate levels, such digital traces can be aggregated and analysed to accurate determine/predict demand patterns and congestion.
In this talk, I will present computational problems relating to the operation of theme parks. From the visitors’ perspective, the most important aspect is in maximizing their enjoyment in the park; while from the operator’s perspective, one aspect is in congestion management (relieving long wait-times for rides and shows). The key in satisfying both aspects lie in effective coordination of visitors through proper dynamic guidance and well-timed incentives.
This talk discusses two problems arising from visitor flow coordination. I will first present the problem relating to single-agent dynamic stochastic route guidance, which is a generalization of the Orienteering Problem (Prize-Collecting Traveling Salesman). I will present an efficient and effective search method, and a mobile application developed for a large theme park operator. I then describe the problem of smoothing out demands/congestion through the use of incentives which are communicated via mobile devices. Here, we consider a network where each agent (i.e. visitor) maximizes his utility of pleasure seeking. Since incentives themselves are resources that are limited, they need to be carefully allocated in order to achieve the desired outcome of reducing congestion. More precisely, given a certain incentive budget level, the goal is to distribute the incentives to different agents at different time points so that certain congestion thresholds are satisfied at equilibrium. We present a mathematical model on how a solution might be computed.
16:00～
講演者
Matias Korman 先生
タイトル
On the Complexity of Barrier Resilience for Fat Regions
アブストラクト
In the \emph {barrier resilience} problem (introduced Kumar {\em et al.}, Wireless Networks 2007), we are given a collection of regions of the plane, acting as obstacles, and we would like to remove the minimum number of regions so that two fixed points can be connected without crossing any region. In this paper, we show that the problem is NP-hard when the regions are fat (even when they are axis-aligned rectangles of aspect ratio $1 : (1 + \eps)$). We also show that the problem is fixed-parameter tractable (FPT) for such regions. Using our FPT algorithm, we show that if the regions are $\beta$-fat and their arrangement has bounded ply $\ply$, there is a $(1+\eps)$-approximation that runs in $O(2^{f(\Delta, \eps,\beta)}n^7)$ time, where $f\in O(\frac{\ply^2\beta^6}{\eps^4}\log(\beta\ply/\eps))$.
