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

Best-of-Both-Worlds Fairness of the Envy-Cycle-Elimination algorithm

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Garg, Jugal Sharma, Eklavya Department of Industrial & Enterprise Engineering University of Illinois at Urbana-Champaign United States

We consider the problem of fairly dividing indivisible goods among agents with additive valuations. It is known that an Epistemic EFX and 2/3-MMS allocation can be obtained using the Envy-Cycle-Elimination (ECE) algorithm [16, 9]. In this work, we explore whether this algorithm can be randomized to also ensure ex-ante proportionality. For two agents, we show that a randomized variant of ECE can compute an ex-post EFX and ex-ante envy-free allocation in near-linear time. However, for three agents, we show that several natural randomization methods for ECE fail to achieve ex-ante proportionality. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

学校读者我要写书评

暂无评论

THE RQR algorithm

arXiv 2024年

作者： Camps, Daan Mach, Thomas Vandebril, Raf Watkins, David S. National Energy Research Scientific Computing Center Lawrence Berkeley National Laboratory United States University of Potsdam Institute of Mathematics Karl-Liebknecht-Str. 24–25 Potsdam14476 Germany Department of Computer Science KU Leuven Belgium Department of Mathematics Washington State University United States

Pole-swapping algorithms, generalizations of bulge-chasing algorithms, have been shown to be a viable alternative to the bulge-chasing QZ algorithm for solving the generalized eigenvalue problem for a matrix pencil A − λB. It is natural to try to devise a pole-swapping algorithm that solves the standard eigenvalue problem for a single matrix A. This paper introduces such an algorithm and shows that it is competitive with Francis’s bulge-chasing QR *** Codes 65F15, 15A18 © 2024, CC BY.

关键词： consensus algorithm

SPINEX_ Symbolic Regression: Similarity-based Symbolic Regression with Explainable Neighbors Exploration

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Naser, M.Z. Naser, Ahmed Z. Clemson University United States Clemson University United States Department of Mechanical Engineering University of Manitoba Canada

This article introduces a new symbolic regression algorithm based on the SPINEX (Similarity-based Predictions with Explainable Neighbors Exploration) family. This new algorithm (SPINEX_SymbolicRegression) adopts a similarity-based approach to identifying high-merit expressions that satisfy accuracy- and structural similarity metrics. We conducted extensive benchmarking tests comparing SPINEX_SymbolicRegression to over 180 mathematical benchmarking functions from international problem sets that span randomly generated expressions and those based on real physical phenomena. Then, we evaluated the performance of the proposed algorithm in terms of accuracy, expression similarity in terms of presence operators and variables (as compared to the actual expressions), population size, and number of generations at convergence. The results indicate that SPINEX_SymbolicRegression consistently performs well and can, in some instances, outperform leading algorithms. In addition, the algorithm's explainability capabilities are highlighted through in-depth experiments. © 2024, CC BY.

关键词： consensus algorithm

Computing largest minimum color-spanning intervals of imprecise points

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Acharyya, Ankush Keikha, Vahideh Saumell, Maria Silveira, Rodrigo I. Dept. of Computer Science and Engineering National Institute of Technology Durgapur India The Czech Academy of Sciences Institute of Computer Science Czech Republic Dept. of Theoretical Computer Science Faculty of Information Technology Czech Technical University Prague Czech Republic Dept. de Matemàtiques Universitat Politècnica de Catalunya Spain

We study a geometric facility location problem under imprecision. Given n unit intervals in the real line, each with one of k colors, the goal is to place one point in each interval such that the resulting minimum color-spanning interval is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given interval of each color. We prove that if the input intervals are pairwise disjoint, the problem can be solved in O(n) time, even for intervals of arbitrary length. For overlapping intervals, the problem becomes much more difficult. Nevertheless, we show that it can be solved in O(nlog2 n) time when k = 2, by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard. © 2024, CC BY.

关键词： consensus algorithm

Approximation and FPT algorithms for Finding DM-Irreducible Spanning Subgraphs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Norose, Ryoma Yamaguchi, Yutaro Osaka University Japan Osaka University Japan

Finding a minimum-weight strongly connected spanning subgraph of an edge-weighted directed graph is equivalent to the weighted version of the well-known strong connectivity augmentation problem. This problem is NP-hard, and a simple 2-approximation algorithm was proposed by Frederickson and Jájá (1981);surprisingly, it still achieves the best known approximation ratio in general. Also, Bang-Jensen and Yeo (2008) showed that the unweighted problem is FPT (fixed-parameter tractable) parameterized by the difference from a trivial upper bound of the optimal value. In this paper, we consider a generalization related to the Dulmage–Mendelsohn decompositions of bipartite graphs instead of the strong connectivity of directed graphs, and extend these approximation and FPT results to the generalized setting. © 2024, CC BY.

关键词： consensus algorithm

From Donkeys to Kings in Tournaments

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Abboud, Amir Grossman, Tomer Naor, Moni Solomon, Tomer Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot76100 Israel Tel Aviv University

A tournament is an orientation of a complete graph. A vertex that can reach every other vertex within two steps is called a king. We study the complexity of finding k kings in a tournament graph. We show that the randomized query complexity of finding k ≤ 3 kings is O(n), and for the deterministic case it takes the same amount of queries (up to a constant) as finding a single king (the best known deterministic algorithm makes O(n3/2) queries). On the other hand, we show that finding k ≥ 4 kings requires Ω(n2) queries, even in the randomized case. We consider the RAM model for k ≥ 4. We show an algorithm that finds k kings in time O(kn2), which is optimal for constant values of k. Alternatively, one can also find k ≥ 4 kings in time nω (the time for matrix multiplication). We provide evidence that this is optimal for large k by suggesting a fine-grained reduction from a variant of the triangle detection problem. © 2024, CC BY-NC-ND.

关键词： consensus algorithm

Stable Approximation algorithms for Dominating Set and Independent Set

学校读者我要写书评

暂无评论

arXiv 2024年

作者： de Berg, Mark Sadhukhan, Arpan Spieksma, Frits Department of Mathematics and Computer Science TU Eindhoven Netherlands

We study Dominating Set and Independent Set for dynamic graphs in the vertex-arrival model. We say that a dynamic algorithm for one of these problems is k-stable when it makes at most k changes to its output independent set or dominating set upon the arrival of each vertex. We study trade-offs between the stability parameter k of the algorithm and the approximation ratio it achieves. We obtain the following results. We show that there is a constant Ε∗ > 0 such that any dynamic (1+Ε∗)-approximation algorithm for Dominating Set has stability parameter Ω(n), even for bipartite graphs of maximum degree 4. We present algorithms with very small stability parameters for Dominating Set in the setting where the arrival degree of each vertex is upper bounded by d. In particular, we give a 1-stable (d+1)2-approximation algorithm, a 3-stable (9d/2)-approximation algorithm, and an O(d)-stable O(1)-approximation algorithm. We show that there is a constant Ε∗ > 0 such that any dynamic (1+Ε∗)-approximation algorithm for Independent Set has stability parameter Ω(n), even for bipartite graphs of maximum degree 3. Finally, we present a 2-stable O(d)-approximation algorithm for Independent Set, in the setting where the average degree of the graph is upper bounded by some constant d at all times. We extend this latter algorithm to the fully dynamic model where vertices can also be deleted, achieving a 6-stable O(d)-approximation algorithm. © 2024, CC BY.

关键词： consensus algorithm

PARALLEL GRAPH DRAWING algorithm FOR BIPARTITE PLANAR GRAPHS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Jain, Naman The International School Bangalore Bangalore India

We give a parallel O(log(n))-time algorithm on a CRCW PRAM to assign vertical and horizontal segments to the vertices of any planar bipartite graph G in the following manner: i) Two segments cannot share an interior point ii) Two segments intersect if and only if the corresponding vertices are adjacent, which uses a polynomial number of processors. In other words, represent vertices of a planar bipartite graph as parallel segments, and edges as intersection points between these segments. Note that two segments are not allowed to cross. Our method is based on a parallel algorithm for st-numbering which uses an ear decomposition search. © 2024, CC BY.

关键词： consensus algorithm

INFERENCE WITH THE UPPER CONFIDENCE BOUND algorithm

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Khamaru, Koulik Zhang, Cun-Hui Department of Statistics Rutgers University United States

In this paper, we discuss the asymptotic behavior of the Upper Confidence Bound (UCB) algorithm in the context of multiarmed bandit problems and discuss its implication in downstream inferential tasks. While inferential tasks become challenging when data is collected in a sequential manner, we argue that this problem can be alleviated when the sequential algorithm at hand satisfy certain stability properties. This notion of stability is motivated from the seminal work of Lai and Wei [19]. Our first main result shows that such a stability property is always satisfied for the UCB algorithm, and as a result the sample means for each arm are asymptotically normal. Next, we examine the stability properties of the UCB algorithm when the number of arms K is allowed to grow with the number of arm pulls T. We show that in such a case the arms are stable when loglogKT → 0, and the number of near-optimal arms are large. © 2024, CC BY.

关键词： consensus algorithm