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

Homogeneous algorithms Can Reduce Competition in Personalized Pricing

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Jo, Nathanael Creel, Kathleen Wilson, Ashia Raghavan, Manish Massachusetts Institute of Technology United States Northeastern University China

Firms’ algorithm development practices are often homogeneous. Whether firms train algorithms on similar data, aim at similar benchmarks, or rely on similar pre-trained models, the result is correlated predictions. We model the impact of correlated algorithms on competition in the context of personalized pricing. Our analysis reveals that (1) higher correlation diminishes consumer welfare and (2) as consumers become more price sensitive, firms are increasingly incentivized to compromise on the accuracy of their predictions in exchange for coordination. We demonstrate our theoretical results in a stylized empirical study where two firms compete using personalized pricing algorithms. Our results underscore the ease with which algorithms facilitate price correlation without overt communication, which raises concerns about a new frontier of anti-competitive behavior. We analyze the implications of our results on the application and interpretation of US antitrust law. © 2025, CC BY.

关键词： consensus algorithm

algorithm Engineering of SSSP With Negative Edge Weights

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Cassis, Alejandro Karrenbauer, Andreas Nusser, André Rinaldi, Paolo Luigi Saarland University Max Planck Institute for Informatics Saarland Informatics Campus Saarbrücken Germany Max Planck Institute for Informatics Saarland University Saarland Informatics Campus Saarbrücken Germany Université Côte d’Azur CNRS Inria France

Computing shortest paths is one of the most fundamental algorithmic graph problems. It is known since decades that this problem can be solved in near-linear time if all weights are nonnegative. A recent break-through by [5] presented a randomized near-linear time algorithm for this problem. A subsequent improvement in [6] significantly reduced the number of logarithmic factors and thereby also simplified the algorithm. It is surprising and exciting that both of these algorithms are combinatorial and do not contain any fundamental obstacles for being practical. We launch the, to the best of our knowledge, first extensive investigation towards a practical implementation of [6]. To this end, we give an accessible overview of the algorithm and discuss what adaptions are necessary to obtain a fast algorithm in practice. We manifest these adaptions in an efficient implementation. We test our implementation on a benchmark data set that is adapted to be more difficult for our implementation in order to allow for a fair comparison. As in [6] as well as in our implementation there are multiple parameters to tune, we empirically evaluate their effect and thereby determine the best choices. Our implementation is then extensively compared to one of the state-of-the-art algorithms for this problem [21]. On the hardest instance type, we are faster by up to almost two orders of magnitude. © 2025, CC BY.

关键词： consensus algorithm

An evaluation algorithm for q-Bézier triangular patches formed by convex combinations

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Delgado, J. Orera, H. Peña, J.M. Departamento de Matemática Aplicada IUMA Universidad de Zaragoza Spain

An extension to triangular domains of the univariate q-Bernstein basis functions is introduced and analyzed. Some recurrence relations and properties such as partition of unity and degree elevation are proved for them. It is also proved that they form a basis for the space of polynomials of total degree less than or equal to n on a triangle. In addition, it is presented a de Casteljau type evaluation algorithm whose steps are all linear convex combinations. © 2025, CC BY-NC-ND.

关键词： consensus algorithm

Faster Approximation algorithms for k-Center via Data Reduction

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Filtser, Arnold Jiang, Shaofeng H.-C. Li, Yi Naredla, Anurag Murty Psarros, Ioannis Yang, Qiaoyuan Zhang, Qin Bar-Ilan university Peking University China Nanyang Technological University Singapore University of Bonn Germany Archimedes Athena Research Center Greece Indiana University Bloomington United States

We study efficient algorithms for the Euclidean k-Center problem, focusing on the regime of large k. We take the approach of data reduction by considering α-coreset, which is a small subset S of the dataset P such that any β-approximation on S is an (α+β)-approximation on P. We give efficient algorithms to construct coresets whose size is k·o(n), which immediately speeds up existing approximation algorithms. Notably, we obtain a near-linear time O(1)approximation when k = nc for any 0 Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Energy Performance, Carbon Footprint and Hardware Efficiency of Blockchain Networks

学校读者我要写书评

暂无评论

Energy Performance, Carbon Footprint and Hardware Efficiency...

International Conference on Communication Systems and Network Technologies (CSNT)

作者： Madhav Ajwalia Parth Shah Zeel Vachhani Chandubhai S. Patel Institute of Technology (CSPIT) Faculty of Technology & Engineering (FTE) Charotar University of Science and Technology (CHARUSAT) Changa Gujarat India

ISBN: (数字)9798331531935

ISBN: (纸本)9798331531942

High Performance Computing (HPC) plays a critical role in supporting the computationally intensive tasks of blockchain technologies, such as consensus algorithms, data processing, and validation. However, the growing adoption of blockchain has raised concerns regarding the substantial energy consumption and carbon footprint associated with HPC systems. This paper investigates the energy efficiency and environmental impact of HPC in blockchain applications, with a focus on hardware and associated hashing algorithms for mining. We analyze power consumption and carbon emissions from computational devices such as Central Processing Units (CPUs), Graphics Processing Units (GPUs), Field-Programmable Gate Arrays (FPGAs), and Application-Specific Integrated Circuits (ASICs), particularly in cryptocurrency mining and decentralized applications. Additionally, we assess the environmental implications of different consensus algorithms, providing a comprehensive understanding of their energy demands and carbon emissions. Our findings offer valuable insights into blockchain sustainability, encouraging the adoption of more energy-efficient and environmentally conscious practices in the industry.

关键词： Industries Energy consumption Carbon dioxide consensus algorithm Hardware Energy efficiency Blockchains Cryptocurrency Sustainable development Field programmable gate arrays

Distributed Graph algorithms with Predictions

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Boyar, Joan Ellen, Faith Larsen, Kim S. University of Southern Denmark Denmark University of Toronto Canada

We initiate the study of deterministic distributed graph algorithms with predictions in synchronous message passing systems. The process at each node in the graph is given a prediction, which is some extra information about the problem instance that may be incorrect. The processes may use the predictions to help them solve the problem. The overall goal is to develop algorithms that both work faster when predictions are good and do not work much worse than algorithms without predictions when predictions are bad. Concepts from the more general area of algorithms with predictions, such as error measures, consistency, robustness, and smoothness, are adapted to distributed graph algorithms with predictions. We consider algorithms with predictions for four distributed graph problems, Maximal Independent Set, Maximal Matching, (∆+1)-Vertex Coloring, and (2∆−1)-Edge Coloring, where ∆ denotes the degree of the graph. For each, we define an appropriate error measure. We present generic templates that can be used to design deterministic distributed graph algorithms with predictions from existing algorithms without predictions. Using these templates, we develop algorithms with predictions for Maximal Independent Set. Alternative error measures for the Maximal Independent Set problem are also considered. We obtain algorithms with predictions for general graphs and for rooted trees and analyze them using two of these error measures. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

A (2+Ε)-Approximation algorithm for Metric k-Median

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Cohen-Addad, Vincent Grandoni, Fabrizio Lee, Euiwoong Schwiegelshohn, Chris Svensson, Ola Google Research France IDSIA USI-SUPSI Switzerland University of Michigan Ann ArborMI United States Aarhus University Denmark EPFL Switzerland

In the classical NP-hard (metric) k-median problem, we are given a set of n clients and centers with metric distances between them, along with an integer parameter k ≥ 1. The objective is to select a subset of k open centers that minimizes the total distance from each client to its closest open center. In their seminal work, Jain, Mahdian, Markakis, Saberi, and Vazirani presented the Greedy algorithm for facility location, which implies a 2-approximation algorithm for k-median that opens k centers in expectation. Since then, substantial research has aimed at narrowing the gap between their algorithm and the best achievable approximation by an algorithm guaranteed to open exactly k centers, as required in the k-median problem. During the last decade, all improvements have been achieved by leveraging their algorithm (or a small improvement thereof), followed by a second step called bi-point rounding, which inherently adds an additional factor to the approximation guarantee. Our main result closes this gap: for any Ε > 0, we present a (2 + Ε)-approximation algorithm for the k-median problem, improving the previous best-known approximation factor of 2.613. Our approach builds on a combination of two key algorithms. First, we present a non-trivial modification of the Greedy algorithm that operates with only O(log n/Ε2) adaptive phases. Through a novel walk-between-solutions approach, this enables us to construct a (2 + Ε)-approximation algorithm for k-median that consistently opens at most k + O(log n/Ε2) centers: via known results, this already implies a (2 + Ε)-approximation algorithm that runs in quasi-polynomial time. Second, we develop a novel (2 + Ε)-approximation algorithm tailored for stable instances, where removing any center from an optimal solution increases the cost by at least an Ω(Ε3/ log n) fraction. Achieving this involves several ideas, including a sampling approach inspired by the k-means++ algorithm and a reduction to submodular optimization subject t

关键词： consensus algorithm

A Quadratic Vertex Kernel and a Subexponential algorithm for Subset-FAST

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Jana, Satyabrata Kanesh, Lawqueen Kundu, Madhumita Lokshtanov, Daniel Saurabh, Saket University of Warwick Coventry United Kingdom Indian Institute of Technology Jodhpur India University of Bergen Norway University of California Santa BarbaraCA United States The Institute of Mathematical Sciences HBNI Chennai India

In the Subset Feedback Arc Set in Tournaments (Subset-FAST) problem we are given as input a tournament T with a vertex set V (T) and an arc set A(T), along with a terminal set S ⊆ V (T), and an integer k. The objective is to determine whether there exists a set F ⊆ A(T) with |F| ≤ k such that the resulting graph T − F contains no cycle that includes any vertex of S. When S = V (T) this is the classic Feedback Arc Set in Tournaments (FAST) problem. We obtain the first polynomial kernel for this problem parameterized by the solution size. More precisely, we obtain an algorithm that, given an input instance (T, S, k), produces an equivalent instance (T′, S′, k′) with k′ ≤ k and V (T′) = O(k2). It was known that FAST admits a simple quadratic vertex kernel and a non-trivial linear vertex kernel. However, no such kernel was previously known for Subset-FAST. Our kernel employs variants of the most well-known reduction rules for FAST and introduces two new reduction rules to identify irrelevant vertices. As a result of our kernelization, we also obtain the first sub-exponential time FPT algorithm for Subset-FAST. © 2025, CC BY.

关键词： consensus algorithm

Sampled-data self-triggered consensus-based economic dispatch problem under switching graph

学校读者我要写书评

暂无评论

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS 2020年第2期491卷 124371-124371页

作者： Jin, Kaiqi Yu, Mei Hou, Guolian North China Elect Power Univ Sch Control & Comp Engn Beijing 102206 Peoples R China China South Ind Grp Corp Beijing 100089 Peoples R China

To reduce the frequency of data exchange in power grid, a novel self-triggered consensus-based optimization algorithm for economic dispatch problem (EDP) is proposed for switching topologies, which guarantees that the increment cost converges to an optimal consensus value after iterations. In this brief, sampled-data framework is employed to complete the implementation of algorithm digitally. Based on that, self-triggered mechanism based approach can also avoid infinite number of communication in finite time, which can save communication cost between generators. Further, a time-varying gain function is designed to derive a tradeoff between convergence rate and triggering performance. Finally, some simulation examples are given to illustrate the effectiveness of the relevant theoretical results. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Sampled-data Self-triggered consensus algorithm Economic dispatch problem Power grid Switching graph