LEADER 12801nam 22008895 450 001 996466450603316 005 20230330012523.0 010 $a3-319-24024-2 024 7 $a10.1007/978-3-319-24024-4 035 $a(CKB)4340000000001103 035 $a(SSID)ssj0001584838 035 $a(PQKBManifestationID)16263783 035 $a(PQKBTitleCode)TC0001584838 035 $a(PQKBWorkID)14865537 035 $a(PQKB)11495407 035 $a(DE-He213)978-3-319-24024-4 035 $a(MiAaPQ)EBC6301901 035 $a(MiAaPQ)EBC5586432 035 $a(Au-PeEL)EBL5586432 035 $a(OCoLC)921140937 035 $a(PPN)190528338 035 $a(EXLCZ)994340000000001103 100 $a20150904d2015 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aAlgorithms, Probability, Networks, and Games$b[electronic resource] $eScientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday /$fedited by Christos Zaroliagis, Grammati Pantziou, Spyros Kontogiannis 205 $a1st ed. 2015. 210 1$aCham :$cSpringer International Publishing :$cImprint: Springer,$d2015. 215 $a1 online resource (XVI, 409 p. 64 illus. in color.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v9295 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-319-24023-4 327 $aIntro -- 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. 327 $aOn 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. 327 $a4 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. 327 $a3 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. 327 $aRandom 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. 330 $aThis Festschrift volume is published in honor of Professor Paul G. Spirakis on the occasion of his 60th birthday. It celebrates his significant contributions to computer science as an eminent, talented, and influential researcher and most visionary thought leader, with a great talent in inspiring and guiding young researchers. The book is a reflection of his main research activities in the fields of algorithms, probability, networks, and games, and contains a biographical sketch as well as essays and research contributions from close collaborators and former PhD students. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v9295 606 $aAlgorithms 606 $aComputer networks 606 $aComputer science 606 $aArtificial intelligence?Data processing 606 $aApplication software 606 $aSoftware engineering 606 $aAlgorithms 606 $aComputer Communication Networks 606 $aTheory of Computation 606 $aData Science 606 $aComputer and Information Systems Applications 606 $aSoftware Engineering 615 0$aAlgorithms. 615 0$aComputer networks. 615 0$aComputer science. 615 0$aArtificial intelligence?Data processing. 615 0$aApplication software. 615 0$aSoftware engineering. 615 14$aAlgorithms. 615 24$aComputer Communication Networks. 615 24$aTheory of Computation. 615 24$aData Science. 615 24$aComputer and Information Systems Applications. 615 24$aSoftware Engineering. 676 $a519.3 702 $aZaroliagis$b Christos$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aPantziou$b Grammati$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aKontogiannis$b Spyros$4edt$4http://id.loc.gov/vocabulary/relators/edt 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996466450603316 996 $aAlgorithms, Probability, Networks, and Games$92830543 997 $aUNISA