TY - BOOK AU - Steffen,Bernhard AU - Woeginger,Gerhard TI - Computing and software science: state of the art and perspectives T2 - Lecture notes in computer science SN - 9783319919089 AV - QA76 U1 - 004 23 PY - 2019/// CY - Cham, Switzerland PB - Springer KW - Computer science KW - Software engineering KW - Artificial intelligence KW - Electronic Data Processing KW - Algorithms KW - Artificial Intelligence KW - Informatique KW - Génie logiciel KW - Algorithmes KW - Intelligence artificielle KW - algorithms KW - aat KW - artificial intelligence KW - fast N1 - Includes bibliographical references and author index; Intro; Geleitwort; References; Preface; Organization; Contents; Computation and Complexity; Computation and Complexity; References; Some Estimated Likelihoods for Computational Complexity; 1 Introduction; 1.1 Some Estimated Likelihoods for Some Major Open Problems; 2 Thoughts on Various Separations; 2.1 EXP with an NP Oracle Versus BPP; 2.2 NEXP vs P/poly; 2.3 LOGSPACE vs NP; 2.4 NP Does Not Have Fixed Polynomial-Size Circuits; 2.5 BPP is in Sub-Exponential Time; 2.6 P vs PSPACE; 2.7 P vs NP; 2.8 ETH: The Exponential Time Hypothesis; 2.9 NC1 versus TC0; 2.10 EXP vs NEXP; 2.11 SETH: The Strong Exponential Time Hypothesis2.12 NEXP vs CoNEXP; 2.13 NSETH: Nondeterministic SETH; 2.14 L vs RL; References; Computing in Combinatorial Optimization; 1 In the Beginning was n Factorial; 2 Dantzig, Linear Programming, and Cutting Planes; 3 Edmonds, Matchings, and Polynomial Time; 4 Sixty-Three Years of Progress; 5 Wish List of Research Directions; 5.1 Improving the Simplex Method; 5.2 Language of Algorithms; 5.3 Understanding Heuristic Algorithms; 5.4 Analysis of Exact Algorithms for Hard Problems; 5.5 Complexity of Cutting-Plane Methods; References; Computational Social Choice: The First Ten Years and Beyond1 Introduction; 2 Restricted Preference Domains; 3 Voting Equilibria and Iterative Voting; 4 Multiwinner Voting; 5 Probabilistic Social Choice; 6 Random Assignment; 7 Computer-Aided Theorem Proving; 8 Further Reading; References; Geometric Optimization Revisited; 1 Introduction; 2 Geometric Set Cover; 2.1 Greedy Algorithms; 2.2 Iterative Reweighing Scheme and -Nets; 2.3 Extensions; 3 Geometric Independent Set; 4 Maps Between Point Sets; 4.1 Transportation Maps; 4.2 Order Preserving Maps; 4.3 Extensions; 5 Discussion; References; 10 Reasons to Get Interested in Graph Drawing1 Introduction; 2 Basic Research; 2.1 Computational Geometry; 2.2 Graph Theory: Canonical Orderings; 2.3 Complexity: A Real Analogue of NP in Graph Drawing; 2.4 Data Structures: SPQR-Tree; 3 Applications; 3.1 Information Visualization; 3.2 Software Engineering; 3.3 Model-Based Design; 3.4 Automated Cartography; 3.5 Social Sciences; 3.6 Molecular Biology; References; Sublinear-Time Algorithms for Approximating Graph Parameters; 1 Introduction; 1.1 Average Degree and Higher Moments of the Degree Distribution; 1.2 The Number of Connected Components; 1.3 Minimum Vertex Cover and Related Parameters1.4 Minimum Weight Spanning Tree; 1.5 Distance to Properties; 1.6 Organization; 2 Preliminaries; 3 Moments of the Degree Distribution; 3.1 Average Degree; 3.2 Higher Moments; 4 Minimum Vertex Cover and Maximum Matching; 4.1 Building on a Distributed Algorithm; 4.2 Building on a Random Ordering; 5 Minimum Weight Spanning Tree; References; Dynamic Erdős-Rényi Graphs; 1 Introduction; 2 Erdős-Rényi Graphs Under Regime Switching; 2.1 Generating Function; 2.2 Moments; 2.3 Diffusion Results Under Scaling; 2.4 Large Deviations Results Under Scaling N2 - The papers of this volume focus on the foundational aspects of computer science, the thematic origin and stronghold of LNCS, under the title "Computing and Software Science: State of the Art and Perspectives". They are organized in two parts: The first part, Computation and Complexity, presents a collection of expository papers on fashionable themes in algorithmics, optimization, and complexity. The second part, Methods, Languages and Tools for Future System Development, aims at sketching the methodological evolution that helps guaranteeing that future systems meet their increasingly critical requirements. -- UR - https://link.springer.com/10.1007/978-3-319-91908-9 ER -