Algorithms, Probability, Networks, and Games

Name: Algorithms, Probability, Networks, and Games | Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday

Christos Zaroliagis Grammati Pantziou Spyros Kontogiannis(Herausgeber*in)

Springer (Verlag)

Erschienen am 7. September 2015

XVI, 409 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-24024-4 (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

Intro
Preface
Acknowledgements
List of Contributors
Contents
Part I
A Glimpse at Paul G. Spirakis
1 Introduction
2 Childhood, Education and Career
3 Teaching, Mentoring, and Publications
4 Awards and Distinctions
5 Research
5.1 Probabilistic and Randomized Algorithms
5.2 Parallel Algorithms and Complexity
5.3 Networks and Distributed Computing
5.4 Internet, Mobile, and Evolution Networks
5.5 Algorithmic Game Theory
5.6 Population Protocols and Temporal Graphs
6 Other Professional Activities
7 Contributions to the Scientific Community
8 Personal
9 Epilogue
References
The Reality Game Theory Imposes (Short Summary)
References
On Neural Networks and Paul Spirakis
Concurrency, Parallelism, Asynchrony and Life
Invited Talks
Rationality Authority for Provable Rational Behavior
1 Introduction
2 Preliminaries
3 Verifying a Nash Equilibrium Using Coq
4 Provable Rationality Using Interactive Proofs
5 Equilibrium Consultant with Provable Advices
6 On-line Network Congestion Games
7 Discussions
References
Weighted Boolean Formula Games
1 Introduction
1.1 Succinct Games and Equilibria Problems
1.2 Weighted Boolean Formula Games
1.3 Summary of Results and Significance
1.4 Related Work and Comparison
1.5 Road Map
2 Framework and Background
2.1 Notation
2.2 Games and Equilibria
2.3 Isomorphisms and Monomorphisms
2.4 Potential Games and Classes of Congestion Games
2.5 Complexity Theory
3 Weighted Boolean Formula Games
3.1 Definition
3.2 Decision and Search Problems
4 Mutual Weighted Boolean Formula Games
5 Pure Equilibria
6 Payoff-Dominant Equilibria
6.1 Upper Bounds
6.2 Completeness Results
7 Open Problems
References
On the Implementation of Combinatorial Algorithms for the Linear Exchange Market
1 Introduction
2 The Algorithm
3 A Glimpse of the Analysis
4 Questions
References
Regular Contributions
On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-completeness and Approximations
1 Introduction, Our Results and Related Work
1.1 Motivation
1.2 Summary of Our Results
1.3 Related Work and Comparison
2 Preliminaries
3 The Complexity of the Radiocoloring Problem
3.1 The NP-Completeness of RCP for Planar Graphs
3.2 The PSPACE-Completeness of RCP for Hierarchical Planar Graphs
4 Approximations to RCP for WS Fully Planar Graphs
4.1 A 10/3-Approximation Algorithm RC_Approx
4.2 A 3-Approximation Algorithm RC_Levels
5 Discussion and Open Problems
References
Performance Evaluation of Routing Mechanisms for VANETs in Urban Areas
1 Introduction
2 Overview of Routing in MANETs and VANETs
2.1 Routing Protocols
2.2 Challenges
3 Proposed Enhancement to GPSR
3.1 Overview of the Proposed Enhancement
3.2 Algorithm and Architecture
4 Simulation Settings
4.1 Reference Scenario
4.2 Experiments and Parameters
5 Results and Discussion
6 Conclusions and Future Work
References
Pioneering the Establishment of the Foundations of the Internet of Things
1 The Internet of Things and Intermittent Connectivity
2 Modeling Mobile and Dynamic Networks
3 A Network Organization Framework for Dynamic Mobile Networks
4 Basic Communication Algorithms for Dynamic Mobile Networks
4.1 Alternative Implementations of the Support
5 Exploiting the Theoretical and Practical Dimensions of Research in Parallel
6 Closing Remarks
References
An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs
1 Introduction
2 Preliminaries
3 The Algorithm
4 Finding a (c,f(c))-Connector in a Degree-3 Graph
5 Extensions of Our Results
6 Conclusions
References
Weighted Random Sampling over Data Streams
1 Introduction
2 Weighted Random Sampling (WRS)
3 The Two Core Algorithms
3.1 A-Chao
3.2 A-ES
3.3 Algorithm A-Chao with Jumps
4 Algorithms for WRS Problems
4.1 Basic Problems
4.2 Sampling with a Bounded Number of Replacements
4.3 Sampling Problems in the Presence of Stream Evolution
5 An Abstract Data Structure for WRS
6 The Role of Weights
7 Discussion
References
Random Instances of Problems in NP -- Algorithms and Statistical Physics
1 Introduction
1.1 Algorithms for rCSP
2 Predictions from Statistical Physics - ``Cavity Method''
2.1 Rigorous Results
3 Satisfiability Thresholds
4 Algorithm Dynamics
4.1 Convergence of Glauber Dynamics
4.2 Dynamics and Optimization
5 Algorithms Beyond Dynamics
5.1 Combinatorial Algorithms
5.2 Numerical Algorithms - Message Passing
References
A Selective Tour Through Congestion Games
1 Introduction
1.1 Organization
2 Congestion Games and Nash Equilibria
2.1 Price of Anarchy and Price of Stability
2.2 Potential Functions and Best Responses
2.3 Non-atomic Congestion Games
3 Potential Functions for Weighted Players
4 Reaching a Pure Nash Equilibrium
4.1 Series-Parallel Networks
4.2 Extension-Parallel Networks
5 The Price of Anarchy and How to Deal with It
5.1 The Price of Anarchy for Extension-Parallel Networks
5.2 Optimal Tolls for Atomic Congestion Games
5.3 Stackelberg Routing
5.4 Approximate Network Design for Non-Atomic Games
References
Data-Streaming and Concurrent Data-Object Co-design: Overview and Algorithmic Challenges
1 Introduction
2 Concurrent object Algorithmic Implementations - Preliminaries
3 Data Streaming - Preliminaries
3.1 Parallel Data Streaming and Deterministic Processing
4 Inter-thread Communication in SPEs Architecture
5 Leveraging Concurrent Data Structures in SPEs
6 ScaleGate: A Novel, Concurrency- and Streaming-Aware Data Object
7 Evaluation Study
8 Conclusions
References
Stability in Heterogeneous Dynamic Multimedia Networks
1 Introduction
2 Related Work
3 Theoretical Framework
4 Instability of FIFO Protocol Compositions Under AQMDS Model
5 Instability of a FIFO Composition with Other Protocols Under AQMDC Model
6 Experimental Evaluation
7 Conclusions
References
Advances in the Parallelization of the Simplex Method
1 Introduction
2 Background
2.1 The Primal Revised Simplex Method
2.2 The Dual Revised Simplex Method
3 Overview of Simplex Parallelization
3.1 Parallelizing the Standard Simplex Method
3.2 Parallelizing the Revised Simplex Method
4 Recent Advances on the Parallelization of the Dual Revised Simplex Method
4.1 Design and Implementation (Key Issues)
4.2 Experimental Results
5 Parallel Distributed-Memory Simplex for Large-Scale Stochastic LP Problems
5.1 Design and Implementation (Key Issues)
5.2 Experimental Results
6 Revisiting the Parallelization of Standard Full Tableau Simplex Method
6.1 Design and Implementation (Key Issues)
6.2 Experimental Results
7 GPU-Based Simplex Parallelization Efforts
8 Conclusion
References
An Introduction to Temporal Graphs: An Algorithmic Perspective
1 Introduction
2 Modeling and Basic Properties
2.1 Journeys
3 Connectivity and Menger's Theorem
4 Dissemination and Gathering of Information
5 Design Problems
6 Temporal Versions of Other Standard Graph Problems: Complexity and Solutions
7 Linear Availabilities
8 Random Temporal Graphs
References
Random Surfing Without Teleportation
1 Introduction and Motivation
2 NCDawareRank Model
2.1 Notation
2.2 Definitions
3 Necessary and Sufficient Conditions for Random Surfing Without Teleportation
3.1 Preliminaries
3.2 NCDawareRank Primitivity Criterion
4 Generalizing the NCDawareRank Model
4.1 The Case of Overlapping Blocks
5 Discussion and Future Work
References
Of Concurrent Data Structures and Iterations
1 Introduction
2 System Model
3 Framework of Consistency Definitions for Concurrent Iterations
4 An Overview of Iteration Algorithms and Implementations
5 Possible Applications and Research Questions
References
On Some Combinatorial Properties of Random Intersection Graphs
1 Introduction and Motivation
1.1 Definitions and a First Look at RIGs
2 An Overview of Selected Combinatorial Problems
2.1 Independent Sets
2.2 Hamilton Cycles
2.3 Coloring
2.4 Expansion and Random Walks
3 Maximum Cliques
4 Epilogue
References
Efficient Equilibrium Concepts in Non-cooperative Network Formation
1 Introduction
2 Notation and Graph-Theoretic Background
3 The Basic Network Creation Game
4 The Asymmetric Basic Network Creation Game
5 The Greedy Buy Basic Network Creation Game
6 The Local Cost Basic Network Creation Game
7 Dynamics of Equilibria
7.1 Symmetric, Asymmetric, and Greedy Swap Equilibria
7.2 Local Cost Swap Equilibria
8 Conclusions and Open Issues
References
Simple Parallel Algorithms for Dynamic Range Products
1 Introduction
1.1 The Problem
1.2 Applications
1.3 Our Contribution and Related Work
2 Tree Partitioning
3 Dynamic Range Products
4 Conclusions
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken