Theory and applications of models of computation : 17th annual conference, TAMC 2022, Tianjin, China, September 16-18, 2022, proceedings / / Ding-Zhu Du [and three others], (editors)

• Pubblicazione: Cham, Switzerland : , : Springer, , [2022]; ©2022
• Descrizione fisica: 1 online resource (427 pages)
• Disciplina: 511.3
• Soggetto topico: Computational complexity; Computer science - Mathematics
• Persona (resp. second.): DuDingzhu
• Nota di contenuto: Intro -- Preface -- Organization -- Contents -- Maximization of k-Submodular Function with a Matroid Constraint -- 1 Introduction -- 2 Preliminaries -- 3 Main Results for nMkSM -- 3.1 A Deterministic Algorithm for nMkSM -- 3.2 A Random Algorithm for nMkSM -- References -- Maximizing Approximately Non-k-Submodular Monotone Set Function with Matroid Constraint -- 1 Introduction -- 2 Preliminaries -- 3 Greedy Algorithm and Analysis -- 3.1 Greedy Algorithm -- 4 Discussion -- References -- Time-of-Use Scheduling Problem with Equal-Length Jobs -- 1 Introduction -- 1.1 Related Works -- 1.2 Problem Definition -- 1.3 Our Contribution -- 2 Preliminaries -- 3 General Instance -- 4 Agreeable Deadlines Jobs -- 5 Conclusion -- References -- Online Weakly DR-Submodular Optimization with Stochastic Long-Term Constraints*-12pt -- 1 Introduction -- 2 Preliminaries -- 3 Problem Statement -- 4 Algorithm and Performance Analysis -- 5 Conclusion -- References -- Physical ZKP for Makaro Using a Standard Deck of Cards -- 1 Introduction -- 1.1 Zero-Knowledge Proof -- 1.2 Related Work -- 1.3 Our Contribution -- 2 Preliminaries -- 2.1 Pile-Shifting Shuffle -- 2.2 Pile-Scramble Shuffle -- 3 Main Protocol -- 3.1 Cell Cards -- 3.2 Verifying Room Condition -- 3.3 Encoding Sequences -- 3.4 Conversion from Cell Cards to Encoding Sequences -- 3.5 Verifying Neighbor Condition -- 3.6 Verifying Arrow Condition -- 3.7 Complexity -- 4 Proof of Correctness and Security -- 5 Future Work -- References -- Characterization of the Imbalance Problem on Complete Bipartite Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Imbalance on Complete Bipartite Graphs -- 4 Imbalance on Chained Complete Bipartite Graphs -- 4.1 Proof of the Upper Bound -- 4.2 Proof of the Lower Bound -- References -- New Algorithms for a Simple Measure of Network Partitioning -- 1 Introduction -- 1.1 Related Work. ; 1.2 Our Results -- 2 The Greedy Cut Algorithm -- 2.1 The Algorithm -- 2.2 Analysis -- 3 Experiments -- 4 Conclusions -- References -- On Two Types of Concept Lattices in the Theory of Numberings -- 1 Introduction -- 2 Preliminaries -- 3 The First Approach: Capturing the Cardinality of a Family -- 3.1 Proof of Theorem 3.1 -- 3.2 Classification via Index Sets -- 4 The Second Approach: Realizing All Countable Complete Lattices -- 4.1 Uncountable Lattices -- 5 Further Discussion -- A Proof of Theorem 3.3 -- B Proof of Theorem4.1 -- References -- Computing Connected-k-Subgraph Cover with Connectivity Requirement -- 1 Introduction -- 1.1 Related Works -- 1.2 Contribution -- 2 Algorithm for MinCkSCcon in Terms of Treewidth -- 2.1 Basic Notations -- 2.2 MinCkSCcon on Bounded Treewidth Graphs -- 3 Sub-exponential FPT Algorithm for MinCkSCcon on H-minor-free Graphs -- 4 Conclusion -- References -- Analyzing the 3-path Vertex Cover Problem in Planar Bipartite Graphs -- 1 Introduction -- 2 Related Work -- 3 Computational Complexity -- 4 Approximation Algorithm -- 5 Approximation Complexity -- 6 Conclusion -- References -- Competition-Based Generalized Self-profit Maximization in Dual-Attribute Networks -- 1 Introduction -- 2 Problem Formulation -- 2.1 Dual-Attribute Compete Model and Diffusion Dynamics -- 2.2 Problem Statements -- 3 The Algorithm -- 3.1 Model Influence Probability -- 3.2 Find Candidate Solutions -- 3.3 Sandwich Approximation -- 4 Experiment -- 5 Conclusion -- References -- Largest Convex Hulls for Constant Size, Convex-Hull Disjoint Clusters -- 1 Introduction -- 1.1 Our Results -- 2 Algorithms for a Set of Disjoint Clusters of Size Two -- 2.1 An Overview -- 2.2 Optimum Solution of an Atomic Problem -- 2.3 Solving MPCH(U, s, t) for Point Clusters in Convex Position -- 2.4 Solving MPCH(U, s, t) for Arbitrarily Given Points -- 3 Extension. ; References -- Two-Stage Submodular Maximization Under Knapsack and Matroid Constraints -- 1 Introduction -- 2 Related Work -- 3 Preliminaries -- 4 Two-Stage Submodular Maximization Subject to Knapsack and K-Matroid Constraints -- 4.1 The Algorithm -- 4.2 The Analysis -- 5 Two-Stage Submodular Maximization Subject to Knapsack and k-exchange System Constraints -- 5.1 The Algorithm -- 5.2 The Analysis -- 6 Conclusion -- A Appendix -- References -- (Z,succ,U), (Z,E,U), and Their CSP's -- 1 Introduction -- 2 Preliminaries -- 3 A Sufficient Condition for Efficiency of CSP(Z,succ,U) -- 4 Bounds and Characterization of CSP(Z,succ,U) -- 4.1 ``Lower Bounding'' CSP(Z,succ,U) -- 4.2 Karp-Equivalent Characterizations of CSP(Z,succ,U) -- 5 From (Z,succ,U) to (Z,E,U) -- 6 Future Directions -- A Proof Details of Interesting Claims -- A.1 Details of Section3, Proposition 1 and Corollary 1 -- A.2 Details of Section3, Theorem 1 and Corollary 2 -- A.3 Details of Section4, Proposition 2 and Corollary 3 -- A.4 Details of Section4, Theorem 2 -- A.5 Details of Section5, Fact 3 and Proposition 4 -- B Diagrams Summarizing Main Results -- B.1 For Section4 -- B.2 For Section5 -- C Detailed Verification of Miscellaneous Claims -- C.1 Full Details of Section3, Observation 1 -- C.2 Section3 Equation1 Gives the L.U.B. in Karp-Order -- C.3 More Discussion on Diffd -- C.4 Figure4 Disproves Converse of Proposition3([struct1]1) -- C.5 Definition of Connectedness in General Case (Re. Comments at Beginning of Section5) -- C.6 Verification of Corollary 4 -- C.7 Remark on Further Generalizing Sect.5 -- C.8 More Discussion on Future Directions -- References -- Circle Graph Isomorphism in Almost Linear Time -- 1 Introduction -- 2 Minimal Split Decomposition and Split Trees -- 3 Canonization of Graph-Labeled Trees -- 4 Canonization of Prime and Degenerate Circle Graphs -- 5 Proof of Theorem 1. ; References -- The Exact Subset MultiCover Problem -- 1 Introduction -- 2 The Exact Subset MultiCover Problem -- 3 The Exclusive Exact Subset MultiCover Problem -- 4 The Max-EESM Problem -- 5 Conclusion -- References -- Hide a Liar: Card-Based ZKP Protocol for Usowan -- 1 Introduction -- 2 Preliminaries -- 2.1 Pile-shifting Shuffle ch17ShinagawaIEICE2017,ch17NishimuraIEICE18 -- 2.2 Mizuki-Sone Copy Protocol ch17MizukiFAW09 -- 2.3 Input-preserving Five-Card Trick ch17MiyaharaFUN2020 -- 2.4 How to Form a White Polyomino ch17RobertNGCO2022 -- 2.5 Sum in Zch17RuangwisesTCS2021 -- 3 ZKP Protocol for Usowan -- 3.1 Setup Phase -- 3.2 Connectivity Phase -- 3.3 Verification Phases -- 4 Conclusion -- A Mizuki-Sone Copy Protocol ch17MizukiFAW09 -- B Input-preserving Five-Card Trick ch17MiyaharaFUN2020 -- C How to Form a White Polyomino -- C.1 Chosen Pile Protocol ch17DumasCOCOON2019 -- C.2 Sub-protocol: 4-Neighbour Protocol ch17RobertNGCO2022 -- C.3 Full Protocol -- D Security Proofs -- References -- Complexity Analysis of a Stochastic Variant of Generalized Alternating Direction Method of Multipliers -- 1 Introduction -- 2 Stochastic Linearized Generalized ADMM -- 3 Complexity Analysis of SLG-ADMM -- 3.1 A Worst-Case O(1/k) Convergence Rate -- 3.2 A Worst-Case O(lnk/k) Convergence Rate Under Strong Convexity -- 4 Conclusion -- References -- A 3/4 Differential Approximation Algorithm for Traveling Salesman Problem -- 1 Introduction -- 2 Definitions and Basic Properties -- 3 Approximation for Even Instances -- 4 Approximation for Odd Instances -- References -- Exact and Parameterized Algorithms for Restricted Subset Feedback Vertex Set in Chordal Graphs -- 1 Introduction -- 2 Preliminaries -- 2.1 Graphs -- 2.2 Chordal Graphs and Split Graphs -- 2.3 Subset Feedback Vertex Set in Chordal Graphs -- 2.4 A Technique for Algorithm Design. ; 3 Reductions Between R-SFVS in Chordal Graphs and Vertex Cover -- 4 A Fast Exact Algorithm for R-SFVS in Chordal Graphs -- 4.1 Max Independent Set Based on Edge Clique Cover -- 4.2 Some Reduction Rules -- 4.3 A Special Case -- 4.4 Subset Feedback Vertex Set in Chordal Graphs -- 5 Conclusion -- References -- An Approximation Algorithm for the B-prize-collecting Multicut Problem in Trees -- 1 Introduction -- 2 Preliminaries -- 3 The Increasing Penalty Algorithm -- 4 Conclusions and Future Work -- References -- Two-Stage Non-submodular Maximization -- 1 Introduction -- 2 Preliminaries -- 3 Problem (2.1) Under a Matroid Constraint -- 3.1 Algorithm -- 3.2 Theoretical Analysis -- 4 Conclusion -- References -- Fault-Tolerant Total Domination via Submodular Function Approximation -- 1 Introduction -- 2 Preliminaries -- 3 General Greedy Submodular Approximation -- 4 Fault-Tolerant Total Domination -- 4.1 Total Domination -- 4.2 Fault-Tolerant Total Domination -- 5 Conclusions -- References -- On the Parallel Complexity of Constrained Read-Once Refutations in UTVPI Constraint Systems -- 1 Introduction -- 2 Statement of Problems -- 2.1 The Constraint-Required Read-Once Refutation (CROR) Problem -- 2.2 The Minimum Weight Perfect Matching (MWPM) Problem -- 2.3 Complexity Classes -- 3 Motivation and Related Work -- 4 The CROR Problem in UTVPI Constraints -- 5 Conclusion -- References -- Extracting Densest Sub-hypergraph with Convex Edge-Weight Functions -- 1 Introduction -- 2 Properties of Edge-Weight Functions -- 3 GDSH with Convex Edge-Weight Functions -- 3.1 A Linear Program Approach -- 3.2 A Network Flow Algorithm -- 3.3 A Fast 1r-approximation Algorithm -- 4 Non-convex Edge-Weight Functions -- 5 Conclusion -- A Missing Proof of Lemma 1 -- B Detailed Proof of Theorem 1 -- C Missing Proof of Lemma 3 -- D Missing Proof to Theorem 3. ; E Missing Proof of Theorem 5.
• Titolo autorizzato: Theory and Applications of Models of Computation
• ISBN: 3-031-20350-X
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910637713503321
• Lo trovi qui: Univ. Federico II
• Serie: Lecture notes in computer science ; ; Volume 13571.