Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings

Front Matter....Pages I-XIII
Front Matter....Pages 1-1
Improved Algorithms for the Evacuation Route Planning Problem....Pages 3-19
Improved MaxSAT Algorithms for Instances of Degree 3....Pages 20-30
Directed Pathwidth and Palletizers....Pages 31-44
Black and White Bin Packing Revisited....Pages 45-59
Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties....Pages 60-71
Variants of Multi-resource Scheduling Problems with Equal Processing Times....Pages 72-81
Front Matter....Pages 82-97
The Discrete and Mixed Minimax 2-Center Problem....Pages 99-99
Approximation Algorithms for Generalized MST and TSP in Grid Clusters....Pages 101-109
Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line....Pages 110-125
Optimal Self-assembly of Finite Shapes at Temperature 1 in 3D....Pages 126-137
Line Segment Covering of Cells in Arrangements....Pages 138-151
An Improved On-line Strategy for Exploring Unknown Polygons....Pages 152-162
Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem....Pages 163-177
Front Matter....Pages 178-190
A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks....Pages 191-191
An Efficient Shortest-Path Routing Algorithm in the Data Centre Network DPillar....Pages 193-208
A Sensor Deployment Strategy in Bus-Based Hybrid Ad-Hoc Networks....Pages 209-220
New Insight into 2-Community Structures in Graphs with Applications in Social Networks....Pages 221-235
WDCS: A Weight-Based Distributed Coordinate System....Pages 236-250
Adaptive Scheduling Over a Wireless Channel Under Constrained Jamming....Pages 251-260
Front Matter....Pages 261-278
Metric and Distributed On-Line Algorithm for Minimizing Routing Interference in Wireless Sensor Networks....Pages 191-191
Distributed Algorithm for Mending Barrier Gaps via Sensor Rotation in Wireless Sensor Networks....Pages 279-292
Front Matter....Pages 293-304
A Hybrid Large Neighborhood Search for Dynamic Vehicle Routing Problem with Time Deadline....Pages 305-305
Indoor Localization via Candidate Fingerprints and Genetic Algorithm....Pages 307-318
On Clustering Without Replication in Combinatorial Circuits....Pages 319-333
On Replica Placement in High-Availability Storage Under Correlated Failure....Pages 334-347
Observing the State of a Smart Grid Using Bilevel Programming....Pages 348-363
Optimizing Static and Adaptive Probing Schedules for Rapid Event Detection....Pages 364-376
Front Matter....Pages 377-391
Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation....Pages 393-393
On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs....Pages 395-408
Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems....Pages 409-423
Multicast Network Design Game on a Ring....Pages 424-438
Extreme Witnesses and Their Applications....Pages 439-451
Orbital Independence in Symmetric Mathematical Programs....Pages 452-466
Symbolic Model Checking for Alternating Projection Temporal Logic....Pages 467-480
Front Matter....Pages 481-495
An I/O Efficient Algorithm for Minimum Spanning Trees....Pages 497-497
The Connected p-Centdian Problem on Block Graphs....Pages 499-509
Searching for (near) Optimal Codes....Pages 510-520
Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs....Pages 521-536
Trees, Paths, Stars, Caterpillars and Spiders....Pages 537-550
Front Matter....Pages 551-565
Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset....Pages 497-497
Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth....Pages 566-573
Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems....Pages 574-585
The Influence of Preprocessing on Steiner Tree Approximations....Pages 586-600
Approximating the Restricted 1-Center in Graphs....Pages 601-616
The Disjunctive Bondage Number and the Disjunctive Total Bondage Number of Graphs....Pages 617-632
Edge-Disjoint Packing of Stars and Cycles....Pages 633-646
Dynamic Minimum Bichromatic Separating Circle....Pages 647-659
Front Matter....Pages 660-675
Searching Graph Communities by Modularity Maximization via Convex Optimization....Pages 676-687
A New Tractable Case of the QAP with a Robinson Matrix....Pages 688-697
An Online Model of Berth and Quay Crane Integrated Allocation in Container Terminals....Pages 699-699
On the Minimal Constraint Satisfaction Problem: Complexity and Generation....Pages 701-708
Algebraic Theory on Shortest Paths for All Flows....Pages 709-720
The Minimum Acceptable Violation Ranking of Alternatives from Voters’ Ordinal Rankings....Pages 721-730
Listing Center Strings Under the Edit Distance Metric....Pages 731-745
Online Scheduling for Electricity Cost in Smart Grid....Pages 746-757
Proportional Cost Buyback Problem with Weight Bounds....Pages 758-770
Back Matter....Pages 771-782
....Pages 783-793