Graphs and Combinatorial Optimization: from Theory to Applications: CTW 2023, Garmisch-Partenkirchen, Germany, June 20–22 (AIRO Springer Series, 13)

CTW 2023 Program Committee
Preface
Contents
The Algorithmic Complexity of the Paired Matching Problem
	1 Introduction
	2 Classical Complexity
	3 Solving Large Instances with Few Task Vertices
	4 Conclusion and Discussion
	References
Edge Contraction and Forbidden Induced Subgraphs
	1 Introduction
		1.1 The H-Split Graphs
		1.2 Critically H-Exist Graphs
	2 Special Graph Classes
		2.1 The 2 upper K 22K2-Free Graphs
		2.2 The upper C 4C4-Free Graphs
		2.3 The upper C 5C5-Free Graphs
		2.4 Split Graphs
	References
Exact Approaches for the Connected Vertex Cover Problem
	1 Introduction
		1.1 Preliminaries
	2 Mixed-Integer Programming Formulations
		2.1 A Smaller Mixed-Integer Formulation
	3 A Branch & Bound Algorithm
	4 Numerical Results
	5 Conclusion
	References
Rigidity of Frameworks on Spheres
	1 Introduction
	2 Rigidity on Non-concentric Spheres
	3 Rigidity of Nearly Monochrome Graphs
	4 Concluding remarks
	References
Managing Time Expanded Networks: The Strong Lift Problem
	1 Introduction
	2 A Reference TEN Relocation Model
		2.1 A TEN Relocation Commodity Flow Model
		2.2 The Projected IRP Model
	3 The Strong Lift Issue
		3.1 The Strong Lift Model
		3.2 A Necessary Condition for the Feasibility of the Strong Lift Problem: Enhancing the PIRP Model
	4 A MILP Formulation of the Strong Lift Problem
		4.1 Solving the Strong Lift Problem in an Exact Way
		4.2 Numerical Experiments
	References
kk-Slow Burning: Complexity and Upper Bounds
	1 Introduction
	2 Complexity
		2.1 Connecting the Paths
		2.2 kk-Slow Burning is Harder Than Graph Burning
		2.3 Checking Burning Sequences
	3 Upper Bounds
	4 Concluding Remarks
	References
Discrepancies of Subtrees
	1 Introduction
	2 Multicolour Discrepancy
	3 Oriented Discrepancy
	4 High Dimensional Discrepancy
	References
Handling Sub-symmetry in Integer Programming using Activation Handlers
	1 Introduction
	2 Sub-symmetry in Integer Programming
	3 Activation Handler
	4 Application
		4.1 Multiple Knapsack Problem
		4.2 Unit Commitment Problem
	5 Experimental Results
	6 Conclusion
	References
A Multivariate Complexity Analysis of the Generalized Noah\'s Ark Problem
	1 Introduction
	2 Preliminaries
		2.1 Problem Definitions, Parameters, and Results Overview
		2.2 Observations for GNAP
	3 Multiple-Choice Knapsack
	4 The Generalized Noah\'s Ark Problem
	5 Restriction to Two Projects per Taxon
	6 Discussion
	References
Comparing Ad-Hoc and MIP-Based Algorithms for the Online Facility Location Problem
	1 Introduction
	2 Problem Statement and Background
	3 Ad-Hoc OFLP Algorithms
	4 MIP-Based Algorithms for BOFLP
		4.1 Follow The Uniformly Perturbed Leader
		4.2 Follow The Clustered Leader
	5 Experimental Setting and Results
		5.1 Experimental Test Bed
		5.2 Evaluation of the Algorithms
	6 Conclusions
	References
Data-Driven Feasibility for the Resource Constrained Shortest Path Problem
	1 Introduction
	2 Problem Definition
	3 Feature Engineering
	4 Computational Experiments
	5 Conclusions
	References
Monte-Carlo Integration on a Union of Polytopes
	1 Introduction
	2 Preliminaries
	3 Monte-Carlo Integration on a Union of Polytopes
		3.1 Extending Markov Chain Monte Carlo
		3.2 Extending Multiphase Monte Carlo
	4 Evaluation
	5 Conclusion
	References
Achieving Long-Term Fairness in Submodular Maximization Through Randomization
	1 Introduction
	2 Preliminaries and Problem Statement
	3 Near Feasible Deterministic Algorithms
		3.1 Algorithm Design
		3.2 Performance Analysis
		3.3 A Fast Greedy Algorithm
	4 A Feasible left parenthesis 1 minus 1 divided by e right parenthesis(1-1/e)-Approximation Randomized Algorithm
	References
On Syntactical Graphs-of-Words
	1 Introduction
		1.1 Ranking Functions for Text
		1.2 Graph-of-Words
		1.3 Syntax Trees
	2 Graph-of-Words Construction Algorithms
		2.1 Proximity Gows
		2.2 Dependency
		2.3 Constituency
	3 Computational Experiments
		3.1 The Literary Dataset
		3.2 The Technical Dataset
	4 Conclusion
	References
On the Optimality Gap of Full Airport Slot Assignments: Capacity-Limited Packing with Pareto Optimality Constraints
	1 Introduction
	2 Notation, Preliminaries, and Main Results
	3 Computational Complexity
	4 Gap Potential at the German Level 3 Airports
	5 Final Remarks
	References
Author Index