| |
|
|
|
|
|
|
|
|
1. |
Record Nr. |
UNINA9910637718903321 |
|
|
Titolo |
Frontiers of Algorithmic Wisdom : International Joint Conference, IJTCS-FAW 2022, Hong Kong, China, August 15-19, 2022, Revised Selected Papers / / Minming Li and Xiaoming Sun, editors |
|
|
|
|
|
|
|
Pubbl/distr/stampa |
|
|
Cham, Switzerland : , : Springer, , [2022] |
|
©2022 |
|
|
|
|
|
|
|
|
|
ISBN |
|
|
|
|
|
|
Descrizione fisica |
|
1 online resource (304 pages) |
|
|
|
|
|
|
Collana |
|
Lecture Notes in Computer Science Series ; ; Volume 13461 |
|
|
|
|
|
|
Disciplina |
|
|
|
|
|
|
Soggetti |
|
Computer algorithms |
Mathematics |
|
|
|
|
|
|
|
|
Lingua di pubblicazione |
|
|
|
|
|
|
Formato |
Materiale a stampa |
|
|
|
|
|
Livello bibliografico |
Monografia |
|
|
|
|
|
Nota di bibliografia |
|
Includes bibliographical references and index. |
|
|
|
|
|
|
Nota di contenuto |
|
Intro -- Preface -- Organization -- Invited Talks -- Constrained Min-Max Optimization: Last-Iterate Convergence and Acceleration -- How Crypto, Stablecoins, CBDCs and Web3 Will Reshape Competition -- Voronoi Diagrams in the Presence of Obstacles -- Recent Progress in Online Matching -- Contents -- Papers and Talks Presented in IJTCS Tracks A-F and H-I, and the Forums -- Algorithmic Game Theory -- EFX Under Budget Constraint -- 1 Introduction -- 2 Preliminaries -- 3 Max-NSW Allocation and EFX Under Budget Constraint -- 4 Computing a BFEFX Allocation -- 5 Concluding Remarks -- References -- Two-Facility Location Games with Distance Requirement -- 1 Introduction -- 2 Preliminaries -- 3 Desirable Two-Facility Location Game with Maximum Distance Requirement -- 4 Obnoxious Two-Facility Location Game with Maximum Distance Requirement -- 5 Conclusions -- References -- Constrained Heterogeneous Two-Facility Location Games with Max-Variant Cost -- 1 Introduction -- 1.1 Our Contribution -- 1.2 Related Work -- 2 Model -- 3 Compulsory Setting -- 3.1 Sum Cost -- 3.2 Maximum Cost -- 4 Optional Setting -- 4.1 Sum Cost -- 4.2 Maximum Cost -- 5 Conclusion -- References -- Optimally Integrating Ad Auction into E-Commerce Platforms -- 1 Introduction -- 1.1 Our Contribution -- 1.2 Related Work -- 2 Notations and Preliminaries -- 2.1 Integrated Ad System -- 2.2 Mechanism Design -- 2.3 Core |
|
|
|
|
|
|
|
|
|
Problems -- 3 The Optimal Mechanisms for the IAS -- 3.1 The Unconstrained Problem -- 3.2 The Constrained Problem -- 4 Extensions -- 4.1 The Integrated Ad System with Number Budget on Ad Items -- 4.2 The Sparse Integrated Ad System -- 5 Conclusion -- References -- Verifiable Crowd Computing: Coping with Bounded Rationality -- 1 Introduction -- 1.1 Main Contributions -- 2 Additional Related Work -- 3 Preliminaries -- 4 Algorithmic Mechanism -- 5 Analysis. |
5.1 A Pareto-Efficient Repeated Game Equilibrium -- 5.2 Deviation-Detection Method -- 5.3 Deviation Punishment and Terminal Payoffs -- 5.4 Mechanism Properties -- 6 Simulations -- 7 Conclusion -- References -- Game Theory in Block Chain -- Equilibrium Analysis of Block Withholding Attack: An Evolutionary Game Perspective -- 1 Introduction -- 2 The Evolutionary Game Model for BWH Attack -- 2.1 Basic Evolutionary Game Model -- 2.2 The Stable Solutions of the Evolutionary Game -- 2.3 Evolutionary Equilibrium Analysis on the Decision of BWH Attack -- 3 Conclusions -- References -- Frontiers of Algorithmic Wisdom -- An Approximation Algorithm for the H-Prize-Collecting Power Cover Problem -- 1 Introduction -- 2 Preliminaries -- 3 The Prize-Collecting Power Cover Problem -- 4 The H-Prize-Collecting Power Cover Problem -- 5 Conclusion -- References -- Online Early Work Maximization on Three Hierarchical Machines with a Common Due Date -- 1 Introduction -- 2 Preliminaries -- 3 One Machine of Hierarchy 1 -- 4 Two Machines of Hierarchy 1 -- 5 Discussion -- References -- Secure Computations Through Checking Suits of Playing Cards -- 1 Introduction -- 1.1 The Five-Card Trick -- 1.2 Protocols with a Standard Deck of Cards -- 1.3 Contribution -- 2 The Existing Card-Minimal AND Protocol -- 3 New Action: Half-Open of Playing Cards -- 4 Our Simple AND Protocol Based on Half-Open Action -- 5 Formalizing Half-Open Action -- 5.1 Notations -- 5.2 Protocols -- 6 Formal Description of Our Protocol -- 6.1 Pseudocode -- 6.2 Correctness and Security -- 7 Discussion -- 7.1 Comparison -- 7.2 Theoretical Aspects -- 7.3 Millionaire Protocol Using Half-Open -- 8 Conclusion -- References -- Streaming Submodular Maximization with the Chance Constraint -- 1 Introduction -- 2 Related Work -- 3 Preliminaries. |
4 Streaming Algorithm: Uniform Independently Identically Distribution Weights (UIIDW) -- 5 Streaming Algorithm: Uniform Weights with the Same Dispersion -- 6 Conclusion -- References -- Colorful Graph Coloring -- 1 Introduction -- 2 Vertex-Coloring Vertex-Colorful -- 3 Edge-Coloring Vertex-Colorful -- 4 Edge-Coloring Edge-Colorful -- 5 Integer Linear Programming -- 6 Conclusion -- A Proof of Sect.2 -- B Proof of Sect.3 -- C Proof of Sect.4 -- References -- On the Transversal Number of Rank k Hypergraphs -- 1 Introduction -- 1.1 Known Results -- 1.2 Our Results -- 2 The Conjecture -- 3 The Rank 2 Hypergraphs -- 4 The Rank 3 Hypergraphs -- 5 The Hypergraphs with König Property -- 6 The Hypergraphs with Maximum Degree 2 -- 6.1 The Bound of Hypergraphs with Maximum Degree 2 -- 6.2 The Extremal Hypergraphs with Maximum Degree 2 -- References -- Exact Algorithms and Hardness Results for Geometric Red-Blue Hitting Set Problem -- 1 Introduction -- 1.1 Previous Work -- 1.2 Our Contributions -- 2 Preliminaries -- 3 The RBHS problem with lines and segments -- 3.1 Intervals on a Real Line IR -- 3.2 Axis-Parallel Line Segments -- 4 The RBHS Problem with Axis-Parallel Rectangles -- 4.1 Rectangles Anchored on a Horizontal Line -- 4.2 Rectangles Stabbing a Horizontal Line -- 5 APX-Hardness Results for the RBHS Problem -- References -- Bounds for the Oriented Diameter of Planar Triangulations -- 1 Introduction -- 2 Oriented Diameter of a Triangular |
|
|
|
|
|
|
|
|
Grid -- 3 Upper Bound on the Oriented Diameter of a Planar Triangulation -- 3.1 Planar Graphs and Schnyder Realizer -- 3.2 An Initial Upper Bound -- 3.3 An Improved Upper Bound -- 4 Lower Bound -- 5 Planar Weighted Oriented Diameter -- 5.1 Planar Weighted Oriented Diameter Is Weakly NP-complete -- 6 Conclusion -- References -- String Rearrangement Inequalities and a Total Order Between Primitive Words -- 1 Introduction. |
1.1 Related Work -- 2 Preliminaries -- 3 A Linear Time Algorithm for Sorting the Repeating Words -- 4 The String Rearrangement Inequalities -- 5 A Total Order on Words -- 6 Conclusions -- A An alternative proof of Lemma 3 -- References -- Approximation Algorithms for Prize-Collecting Capacitated Network Design Problems -- 1 Introduction -- 1.1 Related Works -- 1.2 Our Results -- 2 Preliminaries -- 2.1 Prize-Collecting Capacitated Network Design Problem -- 2.2 Prize-Collecting Facility Location Problem -- 2.3 Prize-Collecting Steiner Tree Problem -- 3 Algorithm and Analysis -- 3.1 Bound the Cost of Opening Sinks and Paying Prizes -- 3.2 Bound the Cost of Installing Cables -- 3.3 Case of Single Sink -- 4 Conclusion -- References -- Computational and Network Economics -- Possible and Necessary Winner Problems in Iterative Elections with Multiple Rules -- 1 Introduction -- 2 Preliminaries -- 2.1 Iterative Voting Rules -- 2.2 Possible and Necessary Winner Problems -- 3 Possible Winner -- 4 Necessary Winner -- 5 Conclusion -- References -- A Mechanism Design Approach for Multi-party Machine Learning -- 1 Introduction -- 1.1 Related Works -- 2 Preliminaries -- 2.1 Valid Data Size (Type) -- 2.2 Learning Protocol -- 2.3 Mechanism -- 2.4 Comparison with the Standard Interdependent Value Setting -- 3 Quasi-Monotone Externality Setting -- 4 General Externality Setting -- 5 Market Growth Rate -- 6 Finding a Desirable Mechanism -- 7 Conclusion -- A Proof of Theorem1 -- B Proof of Corollary1 -- C Proof of Theorem2 -- D Proof of Theorem3 -- E Proof of Theorem4 -- F Proof of Theorem5 -- G Experiments -- G.1 The MEP Mechanism -- G.2 Existence of Desirable Mechanisms -- References -- Budget-Feasible Sybil-Proof Mechanisms for Crowdsensing -- 1 Introduction -- 2 Related Work -- 3 Preliminaries -- 3.1 Reverse Auction Model -- 3.2 Sybil Attack -- 3.3 Properties. |
4 Sybil Attack on Budget-Feasible Mechanisms -- 5 Mechanism TBS -- 5.1 Theoretical Analysis on Desired Properties -- 6 Performance Evaluation -- 6.1 Evaluation of Desired Properties -- 6.2 Evaluation of Optimization Metrics -- 7 Conclusion -- References -- Author Index. |
|
|
|
|
|
| |