Conference Program (Tentative)


Download Here. [PDF, DOC]


December 19

Session Time Title and Speaker/Authors
Registration 8:00-10:00
Opening 10:00-10:15
Keynote 10:15-11:15 Heterogenous Interdependent Networks: Critical Elements and Cascades Analysis
My T. Thai
Session 1
Classic Combinatorial Optimization
(Chair: Lidong Wu)
11:15-11:30 An Exact Algorithm for Non-Preemptive Peak Demand Job Scheduling
Sean Yaw and Brendan Mumey
11:30-11:45 An Asymptotic Competitive Scheme for Online Bin Packing
Lin Chen, Deshi Ye and Guochuan Zhang
11:45-12:00 Randomized Online Algorithms for Set Cover Leasing Problems
Christine Markarian, Sebastian Abshoff and Friedhelm Meyer auf der Heide
Lunch 12:00-13:00
Session 2
Geometric Optimization
(Chair: Ovidiu Daescu)
13:00-13:15 Optimizing Squares Covering a Set of Points
Binay Bhattacharya, Das Sandip, Tsunehiko Kameda, Priya Ranjan Sinha Mahapatra and Zhao Song
13:15-13:30 Algorithms for Fair Partitioning of Convex Polygons
Bogdan Armaselu and Ovidiu Daescu
13:30-13:45 A Quasi-Polynomial Time Approximation Scheme for Euclidean CVRPTW
Liang Song, Hejiao Huang and Hongwei Du
13:45-14:00 On-line Strategies for Evacuating from a Convex Region in the Plane
Qi Wei, Xuehou Tan, Bo Jiang and Lijuan Wang
14:00-14:15 Rectilinear Duals Using Monotone Staircase Polygons
Yi-Jun Chang and Hsu-Chun Yen
14:15-14:30 Optimal Strategy for Walking in Streets with Minimum Number of Turns for a Simple robot
Azadeh Tabatabaei and Mohammad Ghodsi
14:30-14:45 Guarding Monotone Art Galleries with Sliding Cameras in Linear Time
Mark de Berg, Stephane Durocher and Saeed Mehrabi
Coffee Break 14:45-15:00
Session 3
Network Optimization
(Chair: Hsu-Chun Yen)
15:00-15:15 Information Gathering in Ad-Hoc Radio Networks with Tree Topology
Marek Chrobak, Kevin Costello, Leszek Gasieniec and Darek Kowalski
15:15-15:30 Improved Algorithms for Computing Minmax Regret 1-Sink and 2-Sink on Path Network
Binay Bhattacharya and Tsunehiko Kameda
15:30-15:45 Approximate Aggregation for Tracking Quantiles in Wireless Sensor Networks
Zaobo He, Zhipeng Cai, Siyao Cheng and Xiaoming Wang
15:45-16:00 Interference-free k-barrier Coverage in Wireless Sensor Networks
Hongwei Du, haiming luo, Jing Zhang, Rongrong Zhu and Qiang Ye
16:00-16:15 Performance Analysis and Improvement for the Construction of MCDS Problem in 3D Space
Jun Li, Xiaofeng Gao, Guihai Chen, Fengwei Gao and Ling Ding
16:15-16:30 A Practical Greedy Approximation for the Directed Steiner Tree Problem
Dimitri Watel and Marc-Antoine Weisser
16:30-16:45 Spanning Properties of Theta-Theta Graphs
Mirela Damian and Dumitru Voicu
16:45-17:00 A Bicriteria Approximation Algorithm for DVRP with Time Windows
Hao Gu, Liang Song, Hejiao Huang and Hongwei Du

December 20

Session Time Title and Speaker/Authors
Session 4
Optimization in Graphs (I)
(Chair: Liying Kang)
8:30-8:45 Data-Oblivious Graph Algorithms in Outsourced External Memory
Michael Goodrich and Joseph Simons
8:45-9:00 A Dichotomy for Upper Domination in Monogenic Classes
Hassan AbouEisha, Shahid Hussain, Vadim Lozin, Jerome Monnot and Bernard Ries
9:00-9:15 Algorithms for the Maximum Weight Connected k-Induced Subgraph Problem
Ernst Althaus, Markus Blumenstock, Alexej Disterhoft, Andreas Hildebrandt and Markus Krupp
9:15-9:30 Algorithms for Cut Problems on Trees
Iyad Kanj, Guohui Lin, Tian Liu, Weitian Tong, Ge Xia, Jinhui Xu, Boting Yang, Fenghui Zhang, Peng Zhang and Binhai Zhu
9:30-9:45 The Minimum Vulnerability Problem on Graphs
Yusuke Aoki, Bjarni V. Halldorsson, Magnus M. Halldorsson, Takehiro Ito, Christian Konrad and Xiao Zhou
9:45-10:00 The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou
Coffee Break 10:00-10:15
Session 5
Optimization in Graphs (II)
(Chair: Minming Li)
10:15-10:30 Two paths location of a tree with pos/neg weight
Jianjie Zhou and Liying Kang
10:30-10:45 Approximation Algorithms for Optimization Problems in Random Power-Law Graphs
Yilin Shen, Xiang Li and My T. Thai
10:45-11:00 A Comparison between the Zero Forcing Number and the Strong Metric Dimension of Graphs
Cong X. Kang and Eunjeong Yi
11:00-11:15 Optimal Trees for Minimizing Average Individual Updating Cost
Sicen Guo, Minming Li and Yingchao Zhao
11:15-11:30 Cascading Critical Nodes Detection with Load Redistribution in Complex Systems
Subhankar Mishra, My Thai, Xiang Li and Jungtaek Seo
11:30-11:45 The Power of Rejection in Online Bottleneck Matching
Barbara Anthony and Christine Chung
11:45-12:00 The Generalized 3-Edge-Connectivity of Lexicographic Product Graphs
Xueliang Li, Jun Yue and Yan Zhao
Lunch 12:00-13:00
Session 6
Applied Optimization
(Chair: Hejiao Huang)
13:00-13:15 Integer Programming Methods for Special College Admissions Problems
Péter Biró and Iain McBride
13:15-13:30 On the Width of Ordered Binary Decision Diagrams
Beate Bollig
13:30-13:45 Tight Analysis of Priority Queuing for Egress Traffic
Jun Kawahara, Koji Kobayashi and Tomotaka Maeda
13:45-14:00 Optimally Bracing Grid Frameworks with Holes
Yoshihiko Ito, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh, Sheung-Hung Poon and Maria Saumell
14:00-14:15 Top-K Query Retrieval of Combinations with the Sum-of-Subsets Ranking
Subhashis Majumder, Biswajit Sanyal, Prosenjit Gupta, Soumik Sinha, Shiladitya Pande and Wing-Kai Hon
14:15-14:30 Efficient Group Testing Algorithms with a Constrained Number of Positive Responses
Annalisa De Bonis
14:30-14:45 Maximizing Revenues for On-Line Dial-a-Ride
Ananya Christman and William Forcier
Coffee Break 14:45-15:00
Session 7
CSoNet
(Chair: Thang N. Dinh)
15:00-15:15 Global Internet Connectedness: 2002-2011
Hyunjin Seo, Stuart Thorson
15:15-15:30 Optimal Containment of Misinformation in Social Media: A Scenario-based Approach
Yongjia Song and Thang Dinh
15:30-15:45 Multivariate Heavy Tails in Complex Networks
Golshan Golnari, Zhi-Li Zhang
15:45-16:00 Mixed Degree-Degree Correlations in Directed Social Networks
Michael Mayo, Ahmed Abdelzaher and Preetam Ghosh
16:00-16:15 Social and economic network formation: a dynamic model
Omid Atabati, Babak Farzad
16:15-16:30 A Region Growing Algorithm for Detecting Critical Nodes
Mario Ventresca and Dionne Aleman
16:30-16:45 A Fast Greedy Algorithm for the Critical Node Detection Problem
Mario Ventresca and Dionne Aleman
16:45-17:00 Integer Programming Formulations for Minimum Spanning Forests and Connected Components in Sparse Graphs
Neng Fan, Mehdi Golari

December 21

Session Time Title and Speaker/Authors
Session 8
Complexity, Crypotography and Game
(Chair: Zhenhua Duan)
8:30-8:45 On the Parameterized Complexity of Dynamic Problems with Connectivity Constraints
Faisal Abu-Khzam, Judith Egan, Michael Fellows, Frances Rosamond and Peter Shaw
8:45-9:00 Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications
Iyad Kanj and Stefan Szeider
9:00-9:15 Kolmogorov Structure Functions for Automatic Complexity in Computational Statistics
Bjørn Kjos-Hanssen
9:15-9:30 An Improved Even Order Magic Square Construction Algorithm and Its Application
Zhenhua Duan, Jin Liu, Jie Li and Cong Tian
9:30-9:45 The Complexity of the Positive Semidefinite Zero Forcing
Shaun Fallat, Karen Meagher and Boting Yang
9:45-10:00 A Potential Reduction Algorithm for Ergodic Two-person Zero-sum Limiting Average Payoff Stochastic Game
Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Kazuhisa Makino
Coffee Break 10:00-10:15
Session 9
Miscellaneous
(Chair: Wen Xu)
10:15-10:30 The Popular Matching and Condensation Problems under Matroid Constraints
Naoyuki Kamiyama
10:30-10:45 Incremental Computation of Pseudo-Inverse of Laplacian
Gyan Ranjan, Zhi-Li Zhang and Dan Boley
10:45-11:00 Optimal Tracking of Multiple Targets Using UAVs
David Hay, Shahrzad Shirazipourazad and Arun Sen
11:00-11:15 Approximation Algorithm for the Minimum Connected k-Path Vertex Cover Problem
Xiaosong Li, Zhao Zhang
Closing 11:15-11:30