Theory and Applications of Models of Computation : 18th Annual Conference, TAMC 2024, Hong Kong, China, May 13-15, 2024, Proceedings

• Autore: Chen Xujin
• Pubblicazione: Singapore : , : Springer Singapore Pte. Limited, , 2024; ©2024
• Edizione: 1st ed.
• Descrizione fisica: 1 online resource (380 pages)
• Altri autori: LiBo
• Nota di contenuto: Intro -- Preface -- Organization -- Contents -- On Learning Families of Ideals in Lattices and Boolean Algebras -- 1 Introduction -- 2 Preliminaries -- 2.1 Algorithmic Learning -- 2.2 Lattices and Boolean Algebras -- 3 Learning Ideals of a Lattice -- 3.1 Applications and Examples -- 4 Learning Ideals of a Boolean Algebra -- 5 Conservative Learning, and Reverse Mathematics -- References -- Unambiguous and Co-nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters -- 1 Background and Challenging Questions -- 1.1 Two Important Open Questions in Nonuniform Polynomial State Complexity Theory -- 1.2 New Challenges and Main Contributions -- 2 Preliminaries: Notions and Notation -- 2.1 Numbers, Languages, and Pushdown Automata -- 2.2 Promise Problems and Nonuniform Families -- 2.3 Reducing the Number of Counters in Use -- 3 Reachability with No Polynomial Ceiling Bounds -- 4 Effects of Polynomial Ceiling Bounds -- 4.1 Elimination of Counters -- 4.2 Unambiguity of 2N and 2NPD -- 4.3 Complementation of 2N and 2NPD -- References -- A Gray Code of Ordered Trees -- 1 Introduction -- 2 Preliminaries -- 3 Algorithm -- 4 Conclusion -- References -- Mechanism Design with Predictions for Facility Location Games with Candidate Locations -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Contribution -- 2 Preliminaries -- 3 Single Facility Location Game -- 3.1 Maximum Cost -- 3.2 Social Cost -- 4 Single Obnoxious Facility Location Game -- 5 Conclusions and Open Problems -- References -- An Improved Approximation Algorithm for Metric Triangle Packing -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Results -- 2 Preliminaries -- 2.1 Paper Organization -- 3 The First Triangle Packing -- 3.1 The Algorithm -- 3.2 The Analysis -- 4 The Second Triangle Packing -- 4.1 The Algorithm -- 4.2 The Analysis. ; 4.3 The Randomized Matching Algorithm -- 5 The Third Triangle Packing -- 5.1 The Randomized Algorithm -- 5.2 The Analysis -- 5.3 The Derandomization -- 6 The Trade-Off -- 7 Conclusion -- References -- An Optimal and Practical Algorithm for the Planar 2-Center Problem -- 1 Introduction -- 1.1 Our Results -- 2 Preliminaries -- 2.1 Assumptions on Planar 2-Center Problems in the Convex Case -- 2.2 Two Basic Results on Sets of Points in Convex Position -- 3 The 2-Center of a Convex Polygon in the Plane -- 4 The 2-Center of a Set of Points in Convex Position -- 4.1 Algorithm for the Delaunay-Path 2-Center Problem -- 4.2 Algorithm for the Non-Delaunay-Path 2-Center Problem -- 5 The 2-Center of a Set of Arbitrarily Given Points -- References -- Endogenous Threshold Selection with Two-Interval Restricted Tests -- 1 Introduction -- 1.1 Related Works -- 2 Preliminaries -- 3 Endogenous Test Selection with Restricted Tests -- 3.1 The Properties of Bayes-Nash Equilibrium -- 3.2 The Closed Form of Bayes-Nash Equilibrium Distribution -- 3.3 Numerical Results of Inversion -- 4 Conclusion -- References -- An Improved Kernel and Parameterized Algorithm for Almost Induced Matching -- 1 Introduction -- 2 Preliminaries -- 3 Kernelization -- 4 A Parameterized Algorithm -- 4.1 Branching Rules -- 4.2 The Algorithm -- 5 Conclusion -- References -- A Tight Threshold Bound for Search Trees with 2-Way Comparisons -- 1 Introduction -- 2 Preliminaries -- 3 Proof of Theorem 1 -- References -- Kleene Theorems for Lasso Languages and -Languages -- 1 Introduction -- 2 Preliminaries -- 3 Rational Lasso Expressions -- 4 Rational Lasso Languages are Regular -- 5 Regular Lasso Languages are Rational -- 6 Rational Lasso and -Expressions -- 7 Conclusion -- References -- Tight Double Exponential Lower Bounds -- 1 Introduction -- 2 Preliminaries. ; 3 A _2^P-Complete Problem - Single-Exponential for Treewidth -- 4 Simpler Lower Bound Proofs -- 5 Discussion and Conclusion -- References -- Source-Oblivious Broadcast -- 1 Introduction -- 1.1 Context -- 1.2 Objective -- 1.3 Our Results -- 1.4 Related Work -- 2 Preliminaries -- 3 Broadcast Graphs -- 4 Minimum Broadcast Graphs -- 5 Conclusion -- References -- On the 3-Tree Core of Plane Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Construction of a 3-Tree Core -- 3.1 Sequence of Triangles -- 3.2 Pseudopath Augmented 3-Tree Core -- 4 Ortho-Path Visibility Drawing for Planar Graphs -- 5 Finding a Large 3-Tree Core in a Planar Triangulation -- 6 Ortho-Path Visibility Drawing for Triangulations -- 7 Conclusion -- References -- A Coq-Based Infrastructure for Quantum Programming, Verification and Simulation -- 1 Introduction -- 2 Related Work -- 3 Preliminaries -- 4 Powers-of-2 Matrix and Vector -- 4.1 Type and Operation Definition -- 4.2 Property Verification -- 5 PQIR -- 6 Quantum Program Verification and Simulation -- 6.1 QFT Algorithm -- 6.2 QFT Program and Verification -- 6.3 QFT Simulation -- 7 Conclusion -- References -- A Local Search Algorithm for Radius-Constrained k-Median -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Results -- 2 Preliminaries -- 2.1 Notations and Problem Definition -- 2.2 Basic Structures -- 2.3 Description of the Algorithm -- 3 Deal with Radius Constraint and Analyze Local Search Algorithm -- 4 Construction and Analysis of Graph G -- 4.1 Introduce the Concept of Capture -- 4.2 Partition of Solution S and Optimal Solution O -- 4.3 Construction of the Auxiliary Graph -- 4.4 Analysis of Local Search -- 5 Conclusion -- References -- Energy and Output Patterns in Boolean Circuits -- 1 Introduction -- 2 Preliminaries -- 3 Bound on the Number of Output Patterns -- 4 Three Applications of the Bound. ; 4.1 From Bounded-Energy Circuits to Depth-3 Circuits -- 4.2 FPT Algorithm for Counting Output Patterns -- 4.3 Size-Independent Lower Bound on Energy -- 5 Discussion and Open Problems -- References -- Approximation Algorithms for Robust Clustering Problems Using Local Search Techniques -- 1 Introduction -- 1.1 Our Techniques -- 2 Preliminaries -- 3 Local Search Approximation Algorithm for k-MedP/k-MeaP -- 3.1 The Analysis -- 4 Conclusions -- References -- On the Power of Counting the Total Number of Computation Paths of NPTMs -- 1 Introduction -- 2 Preliminaries -- 3 Classes Defined by Total Counting -- 3.1 The Class Gaptot P -- 3.2 The Classes UtotP, FewtotP, tot P, Modktot P, SPtotP, WPtotP, C=totP, and PtotP -- 4 Hardness Results for Problems Definable via TotP Functions -- 4.1 Problems Definable via the Difference of Counting Perfect Matchings -- 4.2 An Exponential Lower Bound for the Problem DiffPerfMatch=g -- 5 Conclusion -- References -- The Parameterized Complexity of Maximum Betweenness Centrality -- 1 Introduction -- 2 Preliminaries -- 3 The Problem -- 4 Natural Parameters -- 5 Structural Parameters -- 5.1 Vertex Cover Number -- 5.2 Distance to Clique -- 5.3 Twin-Cover Number -- 6 Conclusions -- References -- Offensive Alliances in Signed Graphs -- 1 Introduction -- 2 Some Combinatorial Results -- 3 Classical and Fine-Grained Complexity Results -- 4 Parameterized Complexity and Algorithms -- References -- Quantum Path Parallelism: A Circuit-Based Approach to Text Searching -- 1 Introduction -- 2 Quantum Path Parallelism -- 2.1 The Ideas Behind the General Algorithm -- 2.2 The General Quantum Algorithm -- 3 Solving Some Nonstandard Text Searching Problems -- References -- Space-Efficient Graph Kernelizations -- 1 Introduction -- 2 Path Contraction -- 3 Feedback Vertex Set -- References -- Counting on Rainbow k-Connections -- 1 Introduction. ; 2 Preliminaries -- 2.1 Graph Theoretic Terminology -- 2.2 Fixed-Parameter Tractability -- 2.3 Fully Polynomial-Time Randomized Approximation Scheme (FPRAS) -- 3 Treewidth Fixed-Parameter Tractability Results -- 4 Hardness Results -- References -- Some Combinatorial Algorithms on the Edge Cover Number of k-Regular Connected Hypergraphs -- 1 Introduction -- 1.1 Known Results -- 1.2 Our Results -- 2 The Upper Bound for Edge Cover Number -- 3 Extremal k-Regular Connected Hypergraphs -- References -- Time Efficient Implementation for Online K-Server Problem on Trees -- 1 Introduction -- 2 Preliminaries -- 2.1 Online Algorithms -- 2.2 Rooted Trees -- 2.3 k-Server Problem on Trees -- 3 Algorithm -- 3.1 Preprocessing -- 3.2 Query Processing -- 3.3 Moving a Server -- 4 Conclusion -- References -- Improved Approximation Algorithm for the Distributed Lower-Bounded k-Center Problem -- 1 Introduction -- 1.1 Our Result -- 2 Preliminaries -- 3 Distributed Algorithm for the Lower-Bounded k-Center Problem -- 3.1 The First Round -- 3.2 The Second Round -- 4 Conclusions -- References -- Parameterized Complexity of Weighted Target Set Selection -- 1 Introduction -- 1.1 Our Contributions -- 2 Preliminaries -- 3 Hardness -- 3.1 Split Graphs -- 3.2 Cographs -- 4 Polynomial-Time Algorithm for Complete Graphs -- 5 Parameterized Algorithms -- 5.1 FPT Algorithm Parameterized by nd+ -- 5.2 FPT Algorithm Parameterized by tw+ -- 5.3 FPT Algorithm Parameterized by ce -- 5.4 FPT Algorithm Parameterized by vc -- 6 Conclusion and Future Work -- References -- Mechanism Design for Building Optimal Bridges Between Regions -- 1 Introduction -- 1.1 Our Contribution -- 1.2 Related Work -- 2 Model -- 3 Social Cost -- 4 Maximum Cost -- 4.1 Deterministic Strategy-Proof Mechanisms -- 4.2 Randomized Strategy-Proof Mechanisms -- 5 Conclusion -- References -- Joint Bidding in Ad Auctions. ; 1 Introduction.
• Titolo autorizzato: Theory and Applications of Models of Computation
• ISBN: 981-9723-40-X
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 996601563803316
• Lo trovi qui: Univ. di Salerno
• Serie: Lecture Notes in Computer Science Series