Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Sublinear Computation Paradigm [[electronic resource] ] : Algorithmic Revolution in the Big Data Era
| Sublinear Computation Paradigm [[electronic resource] ] : Algorithmic Revolution in the Big Data Era |
| Autore | Katoh Naoki |
| Pubbl/distr/stampa | Singapore, : Springer Singapore Pte. Limited, 2021 |
| Descrizione fisica | 1 online resource (403 p.) |
| Altri autori (Persone) |
HigashikawaYuya
ItoHiro NagaoAtsuki ShibuyaTetsuo SljokaAdnan TanakaKazuyuki UnoYushi |
| Soggetto topico |
Algorithms & data structures
Numerical analysis |
| Soggetto non controllato |
Sublinear Algorithms
polynomial time algorithms Constant-Time Algorithms Sublinear Computation Paradigm open access |
| ISBN | 981-16-4095-5 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Contents -- Part I Introduction -- 1 What Is the Sublinear Computation Paradigm? -- 1.1 We Are in the Era of Big Data -- 1.2 Theory of Computational Complexity and Polynomial-Time Algorithms -- 1.3 Polynomial-Time Algorithms and Sublinear-Time Algorithms -- 1.3.1 A Brief History of Polynomial-Time Algorithms -- 1.3.2 Emergence of Sublinear-Time Algorithms -- 1.3.3 Property Testing and Parameter Testing -- 1.4 Ways to Decrease Computational Resources -- 1.4.1 Streaming Algorithms -- 1.4.2 Compression -- 1.4.3 Succinct Data Structures
1.5 Need for the Sublinear Computation Paradigm -- 1.5.1 Sublinear and Polynomial Computation Are Both Important -- 1.5.2 Research Project ABD -- 1.5.3 The Organization of This Book -- References -- Part II Sublinear Algorithms -- 2 Property Testing on Graphs and Games -- 2.1 Introduction -- 2.2 Basic Terms and Definitions for Property Testing -- 2.2.1 Graphs and the Three Models for Property Testing -- 2.2.2 Properties, Distances, and Testers -- 2.3 Important Known Results in Property Testing on Graphs -- 2.3.1 Results for the Dense-Graph Model -- 2.3.2 Results for the Bounded-Degree Model 2.3.3 Results for the General-Graph Model -- 2.4 Characterization of Testability on Bounded-Degree Digraphs -- 2.4.1 Bounded-Degree Model of Digraphs -- 2.4.2 Monotone Properties and Hereditary Properties -- 2.4.3 Characterizations -- 2.4.4 An Idea to Extend the Characterizations Beyond Monotone and Hereditary -- 2.5 Testable EXPTIME-Complete Games -- 2.5.1 Definitions -- 2.5.2 Testers for Generalized Chess, Shogi, and Xiangqi -- 2.6 Summary -- References -- 3 Constant-Time Algorithms for Continuous Optimization Problems -- 3.1 Introduction -- 3.2 Graph Limit Theory 3.3 Quadratic Function Minimization -- 3.3.1 Proof of Theorem 3.1 -- 3.4 Tensor Decomposition -- 3.4.1 Preliminaries -- 3.4.2 Proof of Theorem 3.2 -- 3.4.3 Proof of Lemma 3.4 -- 3.4.4 Proof of Lemma 3.5 -- References -- 4 Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs -- 4.1 Packing and Covering Semidefinite Programs -- 4.2 Applications -- 4.2.1 SDP relaxation for Robust MaxCut -- 4.2.2 Mahalanobis Distance Learning -- 4.2.3 Related Work -- 4.3 General Framework for Packing-Covering SDPs -- 4.4 Scalar Algorithms 4.4.1 Scalar MWU Algorithm for (Packing-I)-(Covering-I) -- 4.4.2 Scalar Logarithmic Potential Algorithm For (Packing-I)-(Covering-I) -- 4.5 Matrix Algorithms -- 4.5.1 Matrix MWU Algorithm For (Covering-II)-(Packing-II) -- 4.5.2 Matrix Logarithmic Potential Algorithm For (Packing-I)-(Covering-I) -- 4.5.3 Matrix Logarithmic Potential Algorithm For (Packing-II)-(Covering-II) -- References -- 5 Almost Linear Time Algorithms for Some Problems on Dynamic Flow Networks -- 5.1 Introduction -- 5.2 Preliminaries -- 5.3 Objective Functions -- 5.3.1 Objective Functions for the 1-Sink Problem 5.3.2 Objective Functions for k-Sink |
| Record Nr. | UNISA-996464552103316 |
Katoh Naoki
|
||
| Singapore, : Springer Singapore Pte. Limited, 2021 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Sublinear Computation Paradigm : Algorithmic Revolution in the Big Data Era
| Sublinear Computation Paradigm : Algorithmic Revolution in the Big Data Era |
| Autore | Katoh Naoki |
| Pubbl/distr/stampa | Singapore, : Springer Singapore Pte. Limited, 2021 |
| Descrizione fisica | 1 online resource (403 p.) |
| Altri autori (Persone) |
HigashikawaYuya
ItoHiro NagaoAtsuki ShibuyaTetsuo SljokaAdnan TanakaKazuyuki UnoYushi |
| Soggetto topico |
Algorithms & data structures
Numerical analysis |
| Soggetto non controllato |
Sublinear Algorithms
polynomial time algorithms Constant-Time Algorithms Sublinear Computation Paradigm open access |
| ISBN | 981-16-4095-5 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Contents -- Part I Introduction -- 1 What Is the Sublinear Computation Paradigm? -- 1.1 We Are in the Era of Big Data -- 1.2 Theory of Computational Complexity and Polynomial-Time Algorithms -- 1.3 Polynomial-Time Algorithms and Sublinear-Time Algorithms -- 1.3.1 A Brief History of Polynomial-Time Algorithms -- 1.3.2 Emergence of Sublinear-Time Algorithms -- 1.3.3 Property Testing and Parameter Testing -- 1.4 Ways to Decrease Computational Resources -- 1.4.1 Streaming Algorithms -- 1.4.2 Compression -- 1.4.3 Succinct Data Structures
1.5 Need for the Sublinear Computation Paradigm -- 1.5.1 Sublinear and Polynomial Computation Are Both Important -- 1.5.2 Research Project ABD -- 1.5.3 The Organization of This Book -- References -- Part II Sublinear Algorithms -- 2 Property Testing on Graphs and Games -- 2.1 Introduction -- 2.2 Basic Terms and Definitions for Property Testing -- 2.2.1 Graphs and the Three Models for Property Testing -- 2.2.2 Properties, Distances, and Testers -- 2.3 Important Known Results in Property Testing on Graphs -- 2.3.1 Results for the Dense-Graph Model -- 2.3.2 Results for the Bounded-Degree Model 2.3.3 Results for the General-Graph Model -- 2.4 Characterization of Testability on Bounded-Degree Digraphs -- 2.4.1 Bounded-Degree Model of Digraphs -- 2.4.2 Monotone Properties and Hereditary Properties -- 2.4.3 Characterizations -- 2.4.4 An Idea to Extend the Characterizations Beyond Monotone and Hereditary -- 2.5 Testable EXPTIME-Complete Games -- 2.5.1 Definitions -- 2.5.2 Testers for Generalized Chess, Shogi, and Xiangqi -- 2.6 Summary -- References -- 3 Constant-Time Algorithms for Continuous Optimization Problems -- 3.1 Introduction -- 3.2 Graph Limit Theory 3.3 Quadratic Function Minimization -- 3.3.1 Proof of Theorem 3.1 -- 3.4 Tensor Decomposition -- 3.4.1 Preliminaries -- 3.4.2 Proof of Theorem 3.2 -- 3.4.3 Proof of Lemma 3.4 -- 3.4.4 Proof of Lemma 3.5 -- References -- 4 Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs -- 4.1 Packing and Covering Semidefinite Programs -- 4.2 Applications -- 4.2.1 SDP relaxation for Robust MaxCut -- 4.2.2 Mahalanobis Distance Learning -- 4.2.3 Related Work -- 4.3 General Framework for Packing-Covering SDPs -- 4.4 Scalar Algorithms 4.4.1 Scalar MWU Algorithm for (Packing-I)-(Covering-I) -- 4.4.2 Scalar Logarithmic Potential Algorithm For (Packing-I)-(Covering-I) -- 4.5 Matrix Algorithms -- 4.5.1 Matrix MWU Algorithm For (Covering-II)-(Packing-II) -- 4.5.2 Matrix Logarithmic Potential Algorithm For (Packing-I)-(Covering-I) -- 4.5.3 Matrix Logarithmic Potential Algorithm For (Packing-II)-(Covering-II) -- References -- 5 Almost Linear Time Algorithms for Some Problems on Dynamic Flow Networks -- 5.1 Introduction -- 5.2 Preliminaries -- 5.3 Objective Functions -- 5.3.1 Objective Functions for the 1-Sink Problem 5.3.2 Objective Functions for k-Sink |
| Record Nr. | UNINA-9910504285203321 |
|
Katoh Naoki
|
||
| Singapore, : Springer Singapore Pte. Limited, 2021 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||