Combinatorial Optimization and Applications

Name: Combinatorial Optimization and Applications | 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012, Proceedings

Guohui Lin(Herausgeber*in)

Springer (Verlag)

Erschienen am 26. Juli 2012

XI, 398 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-31770-5 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title
Preface
Organization
Table of Contents
Load-Balanced Virtual Backbone Construction for Wireless Sensor Networks
Introduction
Problem Formulation
Network Model
Problem Definition
Load Balanced Virtual Backbone Problem
INP Formulation of MDMIS
Approximation Algorithm
Connected Virtual Backbone
MinMax Valid-Degree Non Backbone Node Allocation
ILP Formulation of MVBA
Randomized Approximation Algorithm
Conclusion
References
Maximum Matching in Multi-Interface Networks
Introduction
Definitions and Notation
Polynomial Time Algorithms
Hardness
Conclusion
References
Stretch Factor inWireless Sensor Networks with Directional Antennae
Introduction
Related Work
Outline and Results of the Paper
Preliminaries and Notation
Orientating Small Groups of Sensors
Merging k-Orientations
Stretch Factor of k-Orientations
Forming k-Orientations from Small Groups of Sensors
Orienting Antennae with Constant Stretch Factor
Orienting Antennae of Beam Width with Constant Stretch Factor
Orienting Antennae of Beam Width /2 & with Constant Stretch Factor
Conclusion
References
On the Minimum Diameter Cost-Constrained Steiner Tree Problem
Introduction
Related Works
Our Contribution
Preliminaries
Illustrate the Realization of Objective Tree
The Problems and NP-Hardness
A Pseudo-polynomial-Time Algorithm for MCDCRP
A Weakly FPTAS for MDCCRP
Auxiliary Graphs
Polynomial Time Approximate Testing
Weakly Fully Polynomial Time Approximation Schemes
Concluding Remarks
References
The Edge-Centered Surface Area of the Arrangement Graph
Introduction
Arrangement Graph and Its Vertex Structures
Derivation of the Surface Area Expression
Concluding Remarks
References
On Zero Forcing Number of Permutation Graphs
Introduction
Z(G) versus Z(G)
Zero Forcing Number of Permutation Graphs on Nearly Complete Graphs and on Complete k-Partite Graphs
Zero Forcing Number of Permutation Graphs on Cycles
Zero Forcing Number of Permutation Graphs on Paths
Open Problems
References
Complexity Results for the Empire Problem in Collection of Stars
Introduction
Definitions
The 4-Coloring Problem in 5-Regular Graphs
Complexity Results for the Empire Problem
Conclusion
References
Hamiltonian Paths and Cycles in Planar Graphs
Introduction
Preliminaries
Hamiltonian Paths in Outerplanar Graphs
Hamiltonian Cycles in Planar Graphs
Conclusion
References
Feedback Vertex Sets on Tree Convex Bipartite Graphs
Introduction
Tree Convex Bipartite Graphs versus Chordal Bipartite Graphs
Intractability of FVS on Tree Convex Bipartite Graphs
References
Crossing Angles of Geometric Graphs
Introduction
Graphs with Bounded Crossing Angle Numbers
Globally Angle-Rigid Graphs with Bounded Degree
References
Multicut on Graphs of Bounded Clique-Width
Introduction
Preliminaries
Complexity Results
Algorithms
Vertex Multicut with cw(G)+|H| as Parameter
RVMC with cw(G u H) as Parameter
Edge Multicut with cw(G)+|H| as Parameter
Conclusion and Future Work
References
Radiation Hybrid Map Construction Problem Parameterized
Introduction
Preliminaries
A Linear Kernel for p-RHMC3
Good Patterns
Kernelization Algorithm
An FPT Algorithm for p-RHMC2
Conclusing Remarks
References
On the Central Path Problem
Introduction
Preliminaries
Algorithms for the Central Path Problem
References
On the Generalized Multiway Cut in Trees Problem
Introduction
Motivation
Related Work
Our Results
An FPT Algorithm
Data Reduction Rules
Problem Kernel and the Algorithm
Some Observations
About the Complexity of GMWC(T)
A Special Case of GMWC(T)
Counterexamples for Some Heuristics
Conclusions
References
Algorithms for Forest Local Similarity
Introduction
Preliminaries
Forest Edit Similarity
Sub-Forests Definitions
Previous Work
Our Results
Algorithms for the Local Forest Similarity Problem
An Algorithm for Finding Two Most Similar Sibling Subforests
An Algorithm for Finding Two Most Similar Closed Subforests
Conclusion
References
Speedup of RNA Pseudoknotted Secondary Structure Recurrence Computation with the Four-Russians Method
Introduction
The Basic Optimal Folding Problem
Rivas&Eddy Algorithm
Rivas&Eddy Recurrences
Rivas&Eddy Algorithm
Conceptual Speedup of Rivas&Eddy
Breaking Up S and W into q Size Vectors
Encoding
Precomputing the R Table
Fast R&E Algorithm
Asymptotic Analysis of Fast R&E Algorithm
References
An Improved Approximation Algorithm for the Bandpass-2 Problem
Introduction
Two Useful Lemmas
The New Algorithm
Performance Analysis
References
The b-Matching Problem in Hypergraphs: Hardness and Approximability
Introduction
Definitions and Preliminaries
Main Result
Approximation Result
References
Resource Scheduling with Supply Constraint and Linear Cost
Introduction
Our Results
Related Work
Basic Definitions and Notation
Analysis of Complexity
Characterizations of the Optimal Schedule
2-Approximation Algorithm
Jobs with Limited Sizes
Conclusions and Discussions
References
On Certain Geometric Properties of the Yao-Yao Graphs
Introduction
Preliminaries
YYk Is a Spanner for Civilized UDG
YY4 Is Not a Spanner
YY4 Is Not Plane
Concluding Remarks
References
Distance-d Independent Set Problems for Bipartite and Chordal Graphs
Introduction
Preliminaries
Bipartite Graphs
Planar Bipartite Graphs
Chordal Bipartite Graphs
Chordal Graphs
References
Domatic Partition on Several Classes of Graphs
Introduction
NP-Hardness
Domatic Partition Algorithms
Domatic Partition on P4-Sparse Graphs
Domatic Partition on Tree-Cographs
3-Domatic Partition on Maximal Planar Graphs
References
Online Bottleneck Matching
Introduction
Preliminaries
Analysis of Greedy
Analysis of Permutation
Bicriteria Analysis of Greedy
Bicriteria Analysis of Balance
Bicriteria Analysis of Permutation
Conclusion
References
Streaming with Minimum Space: An Algorithm for Covering by Two Congruent Balls
Introduction
Streaming with Minimum Space
Related Work
Some Intuition
Some Notations and the Algorithm
Analysis for the 1d Case
Analysis for the d-Dimensional Case
The Invariants
An Upper Bound of 5.708
Lower Bounds for the Problems
Concluding Remarks and Open Problems
References
Online Joint Pricing and Booking Policies in Airline Revenue Management
Introduction
Online Joint Pricing and Booking Policies
Optimal Online Policy for Case k=1
Optimal Online Policy for Case k&1
Conclusion
References
Minimizing Total Weighted Completion Time with Unexpected Machine Unavailability
Introduction
Related Work
New Contribution
Organization
Notations and Preliminary Results
Lower Bounds of Competitive Ratios
Competitive Ratio of LPT
Breakdown Model
Emergent Job Model
First Fit LPT as Offline Algorithms
Numerical Experiments
LPT Algorithm
Summary of FF-LPT
Conclusion
References
Characterizing Mechanisms in Obnoxious Facility Game
Introduction
Preliminaries
Mechanisms in the Line Metric
2-Candidate SP/GSP Mechanisms in the General Metric
Approximation Ratio of 2-Candidate Mechanisms
Concluding Remarks
References
Efficiency of Dual Equilibria in Selfish Task Allocation to Selfish Machines
Introduction
Related Works and Our Contribution
Model Specification
Efficiency Analysis
Small [1,4/3)
Large [4/3, 5/2)
Concluding Remark
References
Fast-Mixed Searching on Graphs
Introduction
Characterizations
Relations to the Induced-Path Cover
Lower Bounds
Relations to Fast Searching and Mixed Searching
Special Classes of Graphs
NP-Completeness
Conclusions
References
Inapproximability after Uniqueness Phase Transition in Two-Spin Systems
Introduction
Proof of the Main Theorems
Proof of Lemma 2
References
Dynamic Programming for a Biobjective Search Problem in a Line
Introduction
Problem Formulations
Formulation (BSPL-1)
Formulation (BSPL-2)
Formulation (BSPL-3)
Complexity Results
Algorithms
Notation and Definitions
Algorithm for Formulation (BSPL-1)
Algorithm for Formulation (BSPL-2)
Algorithm for Formulation (BSPL-3)
Experimental Analysis
Conclusions
References
Characterizing Graphs of Small Carving-Width
Introduction
Preliminaries
The Main Result
Conclusions
References
Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
Introduction
Dominating Set Problem
Connectivity Constraints of Subgraphs
Miller-Tucker-Zemlin Constraints
Martin Constraints
Single-Commodity Flow Constraints
Multi-commodity Flow Constraints
Power Dominating Set Problem and Connected Power Dominating Set Problem
Numerical Experiments
Conclusions
References
Measuring Structural Similarities of Graphs in Linear Time
Introduction
Related Work
Random Walker Termination Similarity Measurement
Random Walks on Graphs
RWT Algorithm
Numerical Experiments
Graph Models
Self-similarity Stability
Graph Edge Rerouting
Cross Model Test
Conclusion
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken