Alexandr Kuznetsov, Emanuele Frontoni, Alexandr Kuznetsov, Ruslan Shevchuk · 5 authors
In the rapidly evolving field of digital asset management, centralized and decentralized global registries have become essential tools for organizing, tracking, and distributing digital assets. However, existing systems often face challenges regarding security, censorship resistance, interoperability, customizability, and scalability. This research paper aims to address these gaps by proposing a novel decentralized global registry system based on blockchain technology and non-fungible tokens (NFTs). The research paper makes several key contributions to the field of digital asset management. First, it provides a detailed system design for the proposed decentralized global registry, outlining its architectural components, functional modules, and integration with blockchain and NFT technologies. Second, it offers a thorough comparative analysis of the advantages and limitations of the proposed system in relation to existing centralized and decentralized registries. Finally, the paper presents potential use cases and practical applications of the proposed system in various industries, demonstrating its versatility and adaptability to different contexts and requirements. In conclusion, this research paper contributes significantly to the ongoing efforts to improve digital asset management by presenting a novel, decentralized global registry system based on blockchain technology and NFTs. The proposed system addresses the key limitations of existing solutions and offers a promising direction for future research and development in this critical field.
A connected loopless graph is 2-edge-connected if it remains connected after the removal of at most one of its edges. Many combinatorial optimization problems seek, for a given graph with costs on its edges, a spanning subgraph satisfying certain connectivity constraints. The minimum 2-edge-connected spanning subgraph problem (2-ECSSP) is a problem of this type. It can be formulated as an integer linear program that selects edges of minimum total cost satisfying the restriction that every cut of the given graph is covered by at least two of the selected edges. This problem is known to be NP-hard. This thesis develops rounding algorithms for three variants of 2-ECSSP, focusing on rounding half-integral solutions of the corresponding linear relaxation. This family of solutions often yields the largest known integrality ratio for various subproblems of 2-ECSSP. The first problem we investigate is the half-integral 2-ECSSP with unrestricted costs. We develop a novel 5/3-rounding that, to the best of our knowledge, is the first one with a factor better than 2. Moreover, we design a reduction scheme, restricting the problem to 4-edge-connected graphs with maximum degree at most five. Then, we study the matching augmentation problem (MAP), a subproblem of 2-ECSSP in which the edge costs are either 0 or 1 and the zero cost edges define a matching. We survey a better-than-2-approximation, obtained in 2022 by Bamas, Drygala, and Svensson, presenting a comprehensive proof of their result and determining an improved factor. Additionally, we address conjectures posed in their work and present computational experiments to support our findings. Finally, we discuss the 2-edge-connected spanning multisubgraph problem (2-ECSMP), a variation of 2-ECSSP in which multiple copies of the same edge can be selected. We survey a recent work by Boyd et al. on a 4/3-rounding for the half-integral 2-ECSMP and leverage their techniques to prove novel decomposition theorems for 4-regular 4-edge-connected graphs. Finally, we pose two conjectures concerning extensions of the decomposition results, suggesting new research directions.