Combinatorial Optimization and Applications

1. Front Matter

   Pages I-XIII

   PDF

2. Classic Combinatorial Optimization

   1. Front Matter

      Pages 1-1

      PDF

   2. Improved Algorithms for the Evacuation Route Planning Problem

      • Gopinath Mishra, Subhra Mazumdar, Arindam Pal

      Pages 3-19

   3. Improved MaxSAT Algorithms for Instances of Degree 3

      • Chao Xu, Jianer Chen, Jianxin Wang

      Pages 20-30

   4. Directed Pathwidth and Palletizers

      • Frank Gurski, Jochen Rethmann, Egon Wanke

      Pages 31-44

   5. Black and White Bin Packing Revisited

      • Jing Chen, Xin Han, Wolfgang Bein, Hing-Fung Ting

      Pages 45-59

   6. Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties

      • Yishui Wang, Dachuan Xu, Donglei Du, Chenchen Wu

      Pages 60-71

   7. A \((5.83+\epsilon )\)-Approximation Algorithm for Universal Facility Location Problem with Linear Penalties

      • Yicheng Xu, Dachuan Xu, Donglei Du, Chenchen Wu

      Pages 72-81

   8. Variants of Multi-resource Scheduling Problems with Equal Processing Times

      • Hamed Fahimi, Claude-Guy Quimper

      Pages 82-97

3. Geometric Optimization

   1. Front Matter

      Pages 99-99

      PDF

   2. The Discrete and Mixed Minimax 2-Center Problem

      • Yi Xu, Jigen Peng, Yinfeng Xu, Binhai Zhu

      Pages 101-109

   3. Approximation Algorithms for Generalized MST and TSP in Grid Clusters

      • Binay Bhattacharya, Ante Ćustić, Akbar Rafiey, Arash Rafiey, Vladyslav Sokol

      Pages 110-125

   4. Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line

      • Apurva Mudgal, Supantha Pandit

      Pages 126-137

   5. Optimal Self-assembly of Finite Shapes at Temperature 1 in 3D

      • David Furcy, Scott M. Summers

      Pages 138-151

   6. Line Segment Covering of Cells in Arrangements

      • Matias Korman, Sheung-Hung Poon, Marcel Roeloffzen

      Pages 152-162

   7. An Improved On-line Strategy for Exploring Unknown Polygons

      • Xuehou Tan, Qi Wei

      Pages 163-177

   8. Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem

      • Michael Khachay, Helen Zaytseva

      Pages 178-190

4. Network Optimization

   1. Front Matter

      Pages 191-191

      PDF

   2. A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks

      • Gennaro Cordasco, Luisa Gargano, Marco Mecchia, Adele A. Rescigno, Ugo Vaccaro

      Pages 193-208

   3. An Efficient Shortest-Path Routing Algorithm in the Data Centre Network DPillar

      • Alejandro Erickson, Abbas Eslami Kiasari, Javier Navaridas, Iain A. Stewart

      Pages 209-220

This book constitutes the refereed proceedings of the 9th International Conference on Combinatorial Optimization and Applications, COCOA 2015, held in Houston, TX, USA, in December 2015. The 59 full papers included in the book were carefully reviewed and selected from 125 submissions. Topics covered include classic combinatorial optimization; geometric optimization; network optimization; applied optimization; complexity and game; and optimization in graphs.

• combinatorial optimization
• complexity
• dynamic programming
• game theory
• network optimization
• applied optimization
• approximation algorithms
• complex network
• computational complexity
• computational geometry
• covering
• directed pathwidth
• exact solution
• graph theory
• integer programming
• partition
• scheduling
• social network
• steiner tree
• algorithm analysis and problem complexity

• Dept. of Mathematics and Computer Science, Marywood University, Scranton, USA

  Zaixin Lu

• North Carolina Central University, Durham, USA

  Donghyun Kim

• University of Texas at Dallas, Richardson, USA

  Weili Wu, Ding-Zhu Du

• Texas Southern University, Houston, USA

  Wei Li

Policies and ethics