Algorithms and Complexity

Name: Algorithms and Complexity | 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings

Dimitris Fotakis Aris Pagourtzis Vangelis Th. Paschos(Editor)

Springer (Publisher)

Published on 12. April 2017

XX, 486 pages

E-Book

PDF with digital watermarking

System requirements

978-3-319-57586-5 (ISBN)

€53.49incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

Intro
Preface
Organization
Invited Talks
TFNP: An Update
2-Edge and 2-Vertex Connectivity in Directed Graphs
New Algorithmic Results for Bin Packing and Scheduling
Contents
Extended Abstracts
TFNP: An Update
1 Introduction
2 Recent Developments
3 Open Problems
References
New Algorithmic Results for Bin Packing and Scheduling
1 Introduction
2 Scheduling Problems
2.1 Known Results
2.2 New Results
3 Bin Packing
3.1 Known Results
3.2 New Results
References
Regular Papers
Scheduling Maintenance Jobs in Networks
1 Introduction
2 Preemptive Scheduling
3 Non-preemptive Scheduling
4 Power of Preemption
5 Mixed Scheduling
6 Conclusion
References
Paths to Trees and Cacti
1 Introduction
2 Preliminaries
3 Kernel for Bounded Out-Tree Contraction
4 Kernel Lower Bounds
4.1 Lower bound for Bounded OTC
References
Temporal Flows in Temporal Networks
1 Introduction and Motivation
1.1 Our Model, the Problem, and Our Results
1.2 Previous Work
1.3 Formal Definitions
2 LP for the MTF Problem with or Without Bounded Buffers
3 Temporal Networks with Unbounded Buffers at Nodes
3.1 Basic Remarks
3.2 The Time-Extended Flow Network and Its Simplification
4 Mixed Temporal Networks and Their Hardness
4.1 Temporal Networks with Random Availabilities that are Flow Cutters
4.2 The Complexity of Computing the Expected Maximum Temporal Flow
References
Completeness Results for Counting Problems with Easy Decision
1 Introduction
1.1 Related Work
2 Preliminaries
3 #Monotone-Circuit-Sat is TotP -complete Under Karp Reductions
3.1 #Monotone-Circuit-Sat is TotP -hard
3.2 #Monotone-Circuit-Sat Is in TotP
4 More TotP -complete Problems
5 Discussion on Approximability Implications
6 Conclusion and Open Problems
References
Tracking Paths
1 Introduction
2 Hardness Results
3 Tracking Paths in Planar Graphs
4 Catching the Intruder
References
On the Complexity of Finding a Potential Community
1 Introduction
2 Preliminaries
3 Complexity Jump from Planar Graphs to Apex Graphs
4 Graph Classes with Polynomial-Time Algorithms
5 NP-hardness and Non-approximability
6 Conclusion
References
Improved Lower Bounds for Graph Embedding Problems
1 Introduction
2 Preliminaries
3 String Crafting and Orthogonal Vector Crafting
4 Lower Bounds for Graph Embedding Problems
5 Tree and Path Decompositions with Few Bags
6 Intervalizing Coloured Graphs
7 Conclusions
References
Collaboration Without Communication: Evacuating Two Robots from a Disk
1 Introduction
1.1 Related Work
1.2 Model
1.3 Notation
2 Determining the Worst-Case Placement of the Exit
3 Evacuating from a Disk
3.1 The Algorithm A(y,,d)
3.2 The Evacuation Time for y=2.62843, =/4 and d=0.48793
4 Conclusion
References
Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
1 Introduction
1.1 Problem Definitions
1.2 Local Search
1.3 Related Work
1.4 Our Contribution
2 Preliminaries
3 The Facility Location Reduction
3.1 Construction of and
3.2 (,) Is a PLS-Reduction
3.3 Proof of Lemma6
3.4 (,) Is a Tight Reduction
4 The K-means Reduction
4.1 Modifications to (,)
4.2 Correctness of the DKM Reduction
4.3 Proof of Lemma13
4.4 Embedding C into 22
5 Related Problems and Future Work
References
Assessing the Computational Complexity of Multi-layer Subgraph Detection
1 Introduction
2 Hereditary Graph Properties
3 Non-hereditary Graph Properties
4 Matchings, c-Factors, and Hamiltonian Subgraphs
5 Conclusion
References
Almost Optimal Cover-Free Families
1 Introduction
1.1 Cover-Free Families
1.2 Previous Results
1.3 New Result
2 Applications of Result
2.1 Application to Learning Hypergraphs
2.2 Application to r-Simple k-Path
3 Proof Overview
4 The First Construction
4.1 Preliminary Results for the First Construction
4.2 Construction I
4.3 Size of Construction I
References
On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
1 Introduction
2 Polynomial Time Algorithms
3 Conclusion
References
Parameterized Resiliency Problems via Integer Linear Programming
1 Introduction
2 ILP Resiliency
3 Resiliency in Access Control
3.1 Definition of the Problem
3.2 Fixed-Parameter Tractability of RCP
4 Closest String Problem
4.1 Adding Resiliency
5 Resilient Scheduling
6 Resilient Swap Bribery
7 Discussion
References
Push-Pull Block Puzzles are Hard
1 Introduction
2 Push-Pull Block Puzzles are NP-hard
3 PSPACE
3.1 Toggles
3.2 Locks
3.3 Quantifiers
3.4 Clause Gadget
3.5 Beginning and End Conditions
4 Conclusion
A Additional Details on 2D Push-Pull Block Puzzles Proof
B 3D Push-Pull is NP-hard
C Additional Details on PSPACE-Completeness Proof
References
Weak Coverage of a Rectangular Barrier
1 Introduction
1.1 Notation and Problem Definition
1.2 Our Results
1.3 Related Work
2 MinNum-WCR Problem
2.1 Hardness Result
2.2 An Efficient Algorithm for Integer Configurations
3 MinSum-WCR Problem
4 MinMax-WCR Problem
5 Conclusion
References
Minimum Cost Perfect Matching with Delays for Two Sources
1 Introduction
1.1 Model
1.2 Related Work
1.3 Our Contribution
2 An Online 2-MPMD Algorithm
2.1 Algorithm DM2
2.2 Analysis
3 A Lower Bound for Deterministic Algorithms
4 Memoryless Online Algorithms
References
Congestion Games with Complementarities
1 Introduction
1.1 Related Work
1.2 Our Contribution
1.3 Model/Preliminaries
2 Existence and Efficiency of Pure Nash Equilibria
3 Existence of Approximate Pure Nash Equilibria
4 Computation of Approximate Equilibria
5 General Aggregation Functions in Matroid Games
6 Conclusion
References
Approximating Bounded Degree Deletion via Matroid Matching
1 Introduction
1.1 Our Work and Contributions
1.2 Notations and Definitions
2 Formulation and Submodular Optimization
2.1 BDD and Matroid Matching
2.2 BDD as Submodular Set Cover
3 Analysis
3.1 Proof of Lemma 1
References
Multi-agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds
1 Introduction
1.1 Background
2 Model
2.1 Reformulation of the MAPF Problem
3 Necessary and Sufficient Combinatorial Criteria for Solvability
3.1 The Combinatorial Conditions in Theorem1 are Necessary
3.2 The Combinatorial Conditions in Theorem1 are Sufficient
3.3 Solvable Problems on Not Generally Solvable Graphs
4 Algorithms, Lower and Upper Bounds
4.1 Complexity Measures
4.2 The Algorithm
4.3 Upper Bound on Number of Operations
4.4 Lower Bound on Number of Operations
5 Conclusion
References
On the Combinatorial Power of the Weisfeiler-Lehman Algorithm
1 Introduction
1.1 Weisfeiler-Lehman Method
1.2 Graph Invariants
1.3 The Graph Isomorphism Problem
1.4 Summary of Main Results
2 Positive Results
3 WL[2] Does Not Count 4-Cliques
4 Difficult Cycles
References
Cost-Sharing in Generalised Selfish Routing
1 Introduction
1.1 Our Results
1.2 Related Work
1.3 Preliminaries
2 Existence of Pure Nash Equilibria
2.1 Alternative Cost-Sharing Based on Commodity Weights
3 The POA and POS of Multi-commodity Games
4 Splittable Games
References
Cache Oblivious Minimum Cut
1 Introduction
2 A Simple Minimum Cut Algorithm for Dense Graphs
3 Simulating Random Access Datastructures
3.1 Monotone RAM simulation
3.2 Minimum Path
4 A Minimum Cut Algorithm for Sparse Graphs
5 Conclusion
References
Enumeration of Maximal Irredundant Sets for Claw-Free Graphs
1 Introduction
2 Preliminaries
3 Enumeration of Maximal Irredundant Sets for Claw-Free Graphs
4 Conclusions
References
Approximate Maximin Share Allocations in Matroids
1 Introduction
2 Set Systems and Maximin Share Fairness
2.1 Basic Notions of Matroids
2.2 The Matroidal Set System Model
3 A 12-Approximation for Any Number of Agents
4 A (1-)-Approximation for Two Agents
5 A (8/9-)-Approximation for Three Agents
6 Conclusion
References
Space-Efficient Euler Partition and Bipartite Edge Coloring
1 Introduction
1.1 Related Work and New Results and Techniques
2 The Representation of Input Graphs
3 Computing Euler Partitions
3.1 Hierholzer's Algorithm
3.2 The Trail Structures
3.3 Hierholzer's Algorithm with Trail Structures
3.4 The Realization of the Trail Structures
4 Bipartite Edge Coloring
4.1 Recursion on Subgraphs
4.2 Reduction to Top Matching
4.3 Reduction to Perfect Matching in Regular Bipartite Graphs
4.4 Alon's Perfect Matching in Weight-Regular Bipartite Graphs
References
Minimum Point-Overlap Labeling
1 Introduction
1.1 Related Work
2 Problem Formulation and a 4-Approximation Algorithm
3 A Faster Combinatorial 8-Approximation Algorithm for Unit Square Labels
3.1 Algorithm
4 Conclusion
References
Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
1 Introduction
2 Preliminaries
3 Upper Bounds
3.1 Small No-Certificates
3.2 Bounded Treedepth
4 Lower Bounds
4.1 No Universal Constant for Independent+kv Graphs
4.2 No Nontrivial Runtime Bound for Path+kv Graphs
5 A Tighter Treedepth Boundary
6 Conclusion
References
Structural Parameters for Scheduling with Assignment Restrictions
1 Introduction
2 Preliminaries
3 Treewidth Results
4 Rankwidth Results
References
On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs
1 Introduction
2 Algorithm for Hamiltonian Cycle in Bounded-Ratio Disk Graphs
3 Lower Bound for Hamiltonian Cycle in Unit Disk Graphs
4 Colouring Disk Graphs
5 Conclusions
References
Tight Inefficiency Bounds for Perception-Parameterized Affine Congestion Games
1 Introduction
2 Our Model, Applications and Related Work
3 Price of Anarchy
4 Price of Stability
References
Perpetually Dominating Large Grids
1 Introduction
2 Preliminaries
3 Eternally Dominating an Infinite Grid
3.1 A First Eternal Domination Strategy
3.2 Empty Squares
3.3 The Rotate-Square Strategy
4 Eternally Dominating Finite Grids
5 Conclusions
References
Rooted Uniform Monotone Minimum Spanning Trees
1 Introduction
2 Definitions and Preliminaries
3 The Rooted y-Monotone Minimum Spanning Tree (rooted y--MMST) Problem
4 Rooted Uniform Monotone Graphs: Minimum Spanning Tree Construction, and Recognition
4.1 Building the Rooted UMMST
4.2 Recognizing Rooted Uniform Monotone Graphs
5 Rooted Uniform 2D-Monotone Graphs: Minimum Spanning Tree Production, and Recognition
6 Conclusions and Future Work
References
Existence of Evolutionarily Stable Strategies Remains Hard to Decide for a Wide Range of Payoff Values
1 Introduction
1.1 Concepts of Evolutionary Games and Stable Strategies
1.2 Previous Work
1.3 Our Results
1.4 Definitions and Notation
2 Robust Reductions
2.1 A Robust Reduction from the Complement of CLIQUE to ESS
3 Our Main Result
4 Conclusions and Further Work
References
Linear Search with Terrain-Dependent Speeds
1 Introduction
1.1 Our Results
1.2 Related Work
2 Two-Speed Models of Linear Search
2.1 The Tailwind Model
2.2 The Beacon Model
2.3 The Exploration History Model
3 Searching with Constant Acceleration
3.1 Constant Acceleration in both Directions
3.2 Moving on an Inclined Line
3.3 Starting at the Top of a Hill
3.4 Starting at the Bottom of a Valley
4 Discussion
References
Linear-Time Generation of Random Chordal Graphs
1 Introduction
2 Background, Terminology and Existing Algorithms
3 Generating Chordal Graphs Using Subtrees of a Tree
4 Experimental Results
5 Concluding Remarks and Future Work
References
Population Protocols with Faulty Interactions: The Impact of a Leader
1 Introduction
1.1 Framework
1.2 Main Contributions
1.3 Related Work
2 Model and Terminology
2.1 Interacting Entities
2.2 Omissions
2.3 Simulation of Two-Way Protocols
3 Simulation with a Leader in Omissive Models: Impossibility
3.1 Impossibility with Finite Memory
3.2 Impossibility with Infinite Memory
4 Simulation in Omissive Models
4.1 Naming Algorithm with Infinite Memory
4.2 Naming Algorithms with Knowledge on Omissions
5 Simulation for IT
References
Paper Dedicated to Stathis Zachos on the Occasion of his 70th Birthday
Stathis Zachos at 70!
1 Introduction
2 Playing Games with Generalized Quantifiers (by Martin Fürer)
3 On the Power of Counting -- and Friendship (by Christos Papadimitriou)
4 An Advisor that Counts (by Aris Pagourtzis)
5 Logic, History, Politics and Basketball (by Costas Koutras)
6 A Colorful Time (by Christos Nomikos)
7 On Art and Increased Visibility (by Euripides Markou)
8 Teaching Programming Through Problem Solving (by Nikos Papaspyrou)
9 Saving Colors and Memories (by Katerina Potika)
10 Combinatory Logic and Graph Coloring (by Panagiotis Cheilaris)
11 An Amazing Teacher (by Dimitris Fotakis)
12 Completeness, at Last! (by Eleni Bakali)
13 Epilogue
References
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Algorithms and Complexity

Description

More details

Other editions

Additional editions

Content

System requirements