检索结果-内蒙古大学图书馆

Min-CSPs on Complete Instances

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Anand, Aditya Lee, Euiwoong Sharma, Amatya University of Michigan Ann Arbor United States

Given a fixed arity k ≥ 2, Min-k-CSP on complete instances is the problem whose input consists of a set of n variables V and one (nontrivial) constraint for every k-subset of variables (so there are (nk) constraints), and the goal is to find an assignment that minimizes the number of unsatisfied constraints. Unlike Max-k-CSP that admits a PTAS on more general dense or expanding instances, the approximability of Min-k-CSP has not been well understood. Moreover, for some CSPs including Min-k-SAT, there is an approximation-preserving reduction from general instances to dense and expanding instances, leaving complete instances as a unique family that may admit new algorithmic techniques. In this paper, we initiate the systematic study of Min-CSPs on complete instances. First, we present an O(1)-approximation algorithm for Min-2-SAT on complete instances, the minimization version of Max-2-SAT. Since O(1)-approximation on dense or expanding instances refutes the Unique Games Conjecture, it shows a strict separation between complete and dense/expanding instances. Then we study the decision versions of CSPs, whose goal is to find an assignment that satisfies all constraints;an algorithm for the decision version is necessary for any nontrivial approximation for the minimization objective. Our second main result is a quasi-polynomial time algorithm for every Boolean k-CSP on complete instances, including k-SAT. We complement this result by giving additional algorithmic and hardness results for CSPs with a larger alphabet, yielding a characterization of (arity, alphabet size) pairs that admit a quasi-polynomial time algorithm on complete instances. © 2024, CC BY.

关键词： consensus algorithm

A Review on Integrating Cloud Blockchain Technology to Secure Electronic Health Records

学校读者我要写书评

暂无评论

A Review on Integrating Cloud Blockchain Technology to Secur...

Soft Computing for Security Applications (ICSCSA), International Conference on

作者： Savita Adhav Atharv Kalambkar Shubhada Kharwante Sanika Sutar Awej Shaikh Department of Information Technolog JSPM Rajarshi Shahu College Of Engineering Tathawade Department of Information Technology JSPM Rajarshi Shahu College of Engineering Tathawade

ISBN: (数字)9798331515720

ISBN: (纸本)9798331515737

The increasing adoption of electronic health records (EHRs) has necessitated secure and efficient sharing mechanisms among healthcare institutions. However, challenges related to data integrity and privacy persist. This review study explores the potential of blockchain technology to address these challenges and enhance EHR sharing security. Blockchain offers several advantages, including immutability, transparency, and decentralization, which can significantly improve data integrity and prevent unauthorized access. consensus algorithms like Proof-of-Work (PoW) or Proof-of-Stake (PoS) ensure data accuracy and reliability. Moreover, blockchain facilitates secure and efficient data sharing by eliminating intermediaries. Smart contracts automate processes, reducing human error and improving efficiency. Additionally, blockchain provides a transparent audit trail for tracking data access and usage. While implementing blockchain in EHR sharing systems presents challenges like scalability, performance, and regulatory compliance, careful consideration of consensus algorithms, data privacy measures, and integration with existing systems is crucial. Blockchain's potential to enhance EHR sharing security and contribute to a more efficient healthcare ecosystem makes it a promising solution.

关键词： Data privacy Electric potential Reviews Data integrity Scalability Ecosystems Medical services consensus algorithm Blockchains Electronic medical records

A New Crossover algorithm for LP Inspired by the Spiral Dynamic of PDHG

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Liu, Tianhao Lu, Haihao Shanghai Jiao Tong University Antai College of Economics and Management China MIT Sloan School of Management United States

Motivated by large-scale applications, there is a recent trend of research on using first-order methods for solving LP. Among them, PDLP, which is based on a primal-dual hybrid gradient (PDHG) algorithm, may be the most promising one. In this paper, we present a geometric viewpoint on the behavior of PDHG for LP. We demonstrate that PDHG iterates exhibit a spiral pattern with a closed-form solution when the variable basis remains unchanged. This spiral pattern consists of two orthogonal components: rotation and forward movement, where rotation improves primal and dual feasibility, while forward movement advances the duality gap. We also characterize the different situations in which basis change events occur. Inspired by the spiral behavior of PDHG, we design a new crossover algorithm to obtain a vertex solution from any optimal LP solution. This approach differs from traditional simplex-based crossover methods. Our numerical experiments demonstrate the effectiveness of the proposed algorithm, showcasing its potential as an alternative option for crossover. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Score-Based Metropolis-Hastings algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Aloui, Ahmed Hasan, Ali Dong, Juncheng Wu, Zihao Tarokh, Vahid Duke University United States Morgan Stanley United States

In this paper, we introduce a new approach for integrating score-based models with the Metropolis-Hastings algorithm. While traditional score-based diffusion models excel in accurately learning the score function from data points, they lack an energy function, making the Metropolis-Hastings adjustment step inaccessible. Consequently, the unadjusted Langevin algorithm is often used for sampling using estimated score functions. The lack of an energy function then prevents the application of the Metropolis-adjusted Langevin algorithm and other Metropolis-Hastings methods, limiting the wealth of other algorithms developed that use acceptance functions. We address this limitation by introducing a new loss function based on the detailed balance condition, allowing the estimation of the Metropolis-Hastings acceptance probabilities given a learned score function. We demonstrate the effectiveness of the proposed method for various scenarios, including sampling from heavy-tail distributions. © 2024, CC BY.

关键词： consensus algorithm

Decentralized Kernel Ridge Regression Based on Data-Dependent Random Feature

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Yang, Ruikai He, Fan He, Mingzhen Yang, Jie Huang, Xiaolin The Institute of Image Processing and Pattern Recognition The MOE Key Laboratory of System Control and Information Processing Shanghai Jiao Tong University Shanghai200240 China The STADIUS Center for Dynamical Systems Signal Processing and Data Analytics KU Leuven LeuvenB-3001 Belgium

Random feature (RF) has been widely used for node consistency in decentralized kernel ridge regression (KRR). Currently, the consistency is guaranteed by imposing constraints on coefficients of features, necessitating that the random features on different nodes are identical. However, in many applications, data on different nodes varies significantly on the number or distribution, which calls for adaptive and data-dependent methods that generate different RFs. To tackle the essential difficulty, we propose a new decentralized KRR algorithm that pursues consensus on decision functions, which allows great flexibility and well adapts data on nodes. The convergence is rigorously given and the effectiveness is numerically verified: by capturing the characteristics of the data on each node, while maintaining the same communication costs as other methods, we achieved an average regression accuracy improvement of 25.5% across six real-world data sets. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Further Improvements on Waring’s Problem

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, An-Ping Beijing 100085 China

关键词： consensus algorithm

Matching Design with algorithms and Applications to Foster Care

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Highsmith, Terence

We study the problem of an organization that matches agents to objects where agents have preference rankings over objects and the organization uses algorithms to construct a ranking over objects on behalf of each agent. Our new framework carries the interpretation that the organization and its agents may be misaligned in pursuing some underlying matching goal. We design matching mechanisms that integrate agent decision-making and the algorithm by avoiding matches that are unanimously disagreeable between the two parties. Our mechanisms also satisfy restricted efficiency properties. Subsequently, we prove that no unanimous mechanism is strategy-proof but that ours can be non-obviously manipulable. We generalize our framework to allow for any preference aggregation rules and extend the famed Gibbard-Satterthwaite Theorem to our setting. We apply our framework to place foster children in foster homes to maximize welfare. Using a machine learning model that predicts child welfare in placements and a (planned) novel lab-in-the-field eliciting real caseworkers’ preferences, we empirically demonstrate that there are important match-specific welfare gains that our mechanisms extract that are not realized under the status quo. Journal of Economic Literature Classification: D47 © 2024, CC BY.

关键词： consensus algorithm

Approximate Frank-Wolfe algorithms over Graph-structured Support Sets

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Pan, Yijian

In this project, we reviewed a paper that deals graph-structured convex optimization (GSCO) problem with the approximate Frank-Wolfe (FW) algorithm. We analyzed and re-implemented the original algorithm and introduced some extensions based on that. Then we conducted experiments to compare the results and concluded that our backtracking line-search method effectively reduced the number of iterations, while our new DMO method (Top-g+ optimal visiting) did not make satisfying enough improvements. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Corrigendum to"Balance of Communication and Convergence: Predefined-time Distributed Optimization Based on Zero-Gradient-Sum"

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zhang, Renyongkang Guo, Ge Zhou, Zeng-Di College of Information Science and Engineering Northeastern University Shenyang110819 China State Key Laboratory of Synthetical Automation for Process Industries Northeastern University Shenyang110819 China School of Control Engineering Northeastern University at Qinhuangdao Qinhuangdao066004 China

This paper proposes a distributed optimization algorithm with a convergence time that can be assigned in advance according to task requirements. To this end, a sliding manifold is introduced to achieve the sum of local gradients approaching zero, based on which a distributed protocol is derived to reach a consensus minimizing the global cost. A novel approach for convergence analysis is derived in a unified settling time framework, resulting in an algorithm that can precisely converge to the optimal solution at the prescribed time. The method is interesting as it simply requires the primal states to be shared over the network, which implies less communication requirements. The result is extended to scenarios with time-varying objective function, by introducing local gradients prediction and non-smooth consensus terms. Numerical simulations are provided to corroborate the effectiveness of the proposed algorithms. © 2024, CC BY.

关键词： consensus algorithm