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

Approximation algorithms for Maximization of k-Submodular Function Under a Matroid Constraint

Tsinghua Science and Technology 2024年第6期29卷 1633-1641页

作者： Yuezhu Liu Yunjing Sun Min Li School of Mathematics and Statistics Shandong Normal UniversityJinan 250014China

In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid *** order to reduce the complexity of this algorithm,we also present a randomized 1/3-approximation algorithm with the probability of 1−ε,whereεis the probability of algorithm ***,we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.

关键词： k-submodular matroid constraint deterministic algorithm randomized algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

DASL: An Index for Enhancing Tail Latency, Microarchitecture Friendliness, and Restructuring Overhead

引用

IEEE ACCESS 2025年 13卷 78303-78319页

作者： Shin, Hojin Choi, Gunhee Kim, Bryan S. Yoo, Seehwan Choi, Jongmoo Dankook Univ Dept Software Yongin 16890 Gyeonggi Do South Korea Syracuse Univ Dept Elect Engn & Comp Sci Syracuse NY 13244 USA Dankook Univ Dept Mobile Syst Engn Yongin 16890 Gyeonggi Do South Korea

The skip list is a popular in-memory index in modern database systems. It maintains multiple levels of lists, which makes it efficient in traversing sorted data. In addition, it is flexible in inserting and deleting data, while avoiding the restructuring overhead of tree-based structures. However, there are considerable challenges in the conventional skip list design. First, the linked list structure has a drawback in utilizing microarchitecture features such as cache, pipeline, and SIMD (Single Instruction Multiple Data) capability. Second, the skip list randomly selects the level of a new node. That is, the skip list runs based on probability rather than data distribution, which can lead to suboptimal lookup performance. Unlike balanced tree structures, the worst-case lookup performance of a skip list remains O(n). This paper proposes a new data structure called DASL (deterministic Arrayed Skip List). It follows the algorithm of the skip list, but seamlessly integrates the array and devises a new deterministic raise operation in order to obtain flexibility, microarchitecture-friendliness, and reduced tail latency. In specific, a node in DASL consists of an array structure with multiple elements instead of a single element, taking advantage of the array within a list structure. Additionally, the raise operation is conducted deterministically instead of probabilistically, allowing data to be more balanced in multiple lists. Furthermore, we devise two optimization techniques, utilization-based adaptive intra-node search and uneven split operation. Experimental results with various synthetic and real-world workloads demonstrate that DASL outperforms other state-of-the-art in-memory indexes, including skip list, B+tree, and ART.

关键词： Indexes Arrays Microarchitecture Tail Subspace constraints Optimization Single instruction multiple data Probabilistic logic Periodic structures Throughput Array-based indexing database index deterministic algorithm in-memory indexes skip list performance optimizations

来源：评论

学校读者我要写书评

暂无评论

SVD-based algorithms for tensor wheel decomposition

引用

ADVANCES IN COMPUTATIONAL MATHEMATICS 2024年第5期50卷 1-23页

作者： Wang, Mengyu Cui, Honghua Li, Hanyu Chongqing Univ Coll Math & Stat Chongqing Peoples R China Xiamen Univ Wang Yanan Inst Studies Econ Fujian Peoples R China Chongqing Univ Key Lab Nonlinear Anal & its Applicat Minist Educ Chongqing Peoples R China

Tensor wheel (TW) decomposition combines the popular tensor ring and fully connected tensor network decompositions and has achieved excellent performance in tensor completion problem. A standard method to compute this decomposition is the alternating least squares (ALS). However, it usually suffers from slow convergence and numerical instability. In this work, the fast and robust SVD-based algorithms are investigated. Based on a result on TW-ranks, we first propose a deterministic algorithm that can estimate the TW decomposition of the target tensor under a controllable accuracy. Then, the randomized versions of this algorithm are presented, which can be divided into two categories and allow various types of sketching. Numerical results on synthetic and real data show that our algorithms have much better performance than the ALS-based method and are also quite robust. In addition, with one SVD-based algorithm, we also numerically explore the variability of TW decomposition with respect to TW-ranks and the comparisons between TW decomposition and other famous formats in terms of the performance on approximation and compression.

关键词： Tensor wheel decomposition SVD Alternating least squares deterministic algorithm Randomized algorithm Sketching

来源：评论

学校读者我要写书评

暂无评论

Memory optimal distance-2-dispersion with termination

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2025年

作者： Kaur, Tanvir Mondal, Kaushik Indian Inst Technol Ropar Dept Math Rupnagar 140001 Punjab India

The aim of the dispersion problem is to place a set of k(= n, it is guaranteed that the nodes with robots form a maximal independent set of the underlying network. The graph G=(V,E) is a port-labeled graph with n node... 详细信息

The aim of the dispersion problem is to place a set of k(<= n) mobile robots in the nodes of an unknown graph consisting of n nodes such that in the final configuration each node contains at most one robot, starting from any arbitrary initial configuration of the robots on the graph. In this work, we propose a variant of the dispersion problem, namely Distance-2-Dispersion, in short, D-2-D, where we start with any number of robots, and put an additional constraint that no two adjacent nodes contain robots in the final configuration. That is, the distance between any two nodes with robots must be at least 2. However, even if the number of robots k is less than n, it might be the case that it is not possible for each robot to find a distinct node to reside, maintaining our added constraint. More specifically, if a maximal independent set is already formed by the nodes containing a robot each, then any other unsettled robot will not find a node to settle. Hence we allow multiple robots to sit on some nodes only if there is no place to sit. If k >= n, it is guaranteed that the nodes with robots form a maximal independent set of the underlying network. The graph G=(V,E) is a port-labeled graph with n nodes and m edges, where nodes are anonymous. The robots have unique IDs in the range [1,L], where L >= k. Co-located robots can communicate among themselves. We provide an algorithm that solves D-2-D starting from a rooted configuration (i.e. initially all the robots are co-located) and terminates after 2 Delta(8m-3n+3) synchronous rounds using O(log n) memory per robot, without using any global knowledge of the graph parameters m, n and Delta, the maximum degree of the graph. We provide Omega(log n) lower bound on the memory requirement by the robots to solve the D-2-D problem. Thus our algorithm is memory-optimal. We conjecture that the time required by the robots to solve the D-2-D problem, provided each of them have O(log n) memory, is Omega(m Delta) rounds. We further

关键词： Mobile robots dispersion distance-2-dispersion deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithmic research on surface roughness in laser-melted claddings: A review

引用

SURFACE ENGINEERING 2024年第9-10期40卷 933-944页

作者： Zhao, Changlong Zhang, Zihao Yu, Zice Du, Weilong Changchun Univ Coll Mech & Vehicle Engn Changchun 130022 Jilin Peoples R China

As a breakthrough of the additive manufacturing technology being achieved, many fields have broadly applied laser cladding due to its unique advantages. But the surface characteristics of the cladding layer are not frequently aligned with the standards necessary for industrial use. Consequently, with a particular focus on refining its surface roughness, it has emerged as a significant area of interest among numerous investigators. This paper reviews a variety of methods for optimizing the surface roughness of laser cladding, covering from deterministic algorithms such as Taguchi's method, orthogonal experimental method, gradient descent method, to stochastic algorithms including neural network, genetic algorithm, Gray Wolf algorithm, and even hybrid algorithms combining multiple algorithms like neural network genetic algorithm, adaptive neural fuzzy reasoning algorithm, and improved genetic algorithms for response surface analysis, and so on. Through comparative analysis, it is found that the hybrid algorithms can quickly generate the optimal optimization parameters for the sake of achieving the optimal surface quality since they may combine the accuracy of deterministic algorithms and the robustness of stochastic algorithms. In addition, this paper also looks forward to the future development direction of surface quality optimization methods for laser cladding, aiming at laying a foundation for the research work of high-quality coating preparation.

关键词： laser cladding technology surface roughness deterministic algorithm stochastic algorithm hybrid algorithm

来源：评论

学校读者我要写书评

暂无评论

Distance-2-Dispersion with Termination by a Strong Team 10th

Distance-2-Dispersion with Termination by a Strong Team

引用

10th International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Gorain, Barun Kaur, Tanvir Mondal, Kaushik Indian Inst Technol Bhilai Bhilai India Indian Inst Technol Ropar Rupnagar India

ISBN: (纸本)9783031522123;9783031522130

Distance-2-Dispersion (D-2-D) problem aims to disperse k mobile robots starting from an arbitrary initial configuration on an anonymous port-labeled graph G with n nodes such that no two robots occupy adjacent nodes in the final configuration, though multiple robots may occupy a single node if there is no other empty node whose all adjacent nodes are also empty. In the existing literature, this problem is solved starting from a rooted configuration for k(>= 1) robots using O(m Delta) synchronous rounds with a total of O(log n) memory per robot, where m is the number of edges and Delta is the maximum degree of the graph. In this work, we start with k > n mobile robots and improve the run time to O(m) starting from a rooted configuration using the same amount of memory per robot. Further, we achieve D-2-D for an arbitrary initial configuration in O(pm) rounds using O(log n) memory per robot, where p is the number of nodes containing robots in the initial configuration. Both the algorithms terminate without any global knowledge of m, n, Delta, k, p. As we start with k > n robots, the nodes occupied by robots in the final configuration form a maximal independent set of the graph.

关键词： Mobile robots Dispersion Distance-2-Dispersion deterministic algorithm Distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: deterministic Massively Parallel algorithms for Ruling Sets 22

Brief Announcement: Deterministic Massively Parallel Algorit...

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Pai, Shreyas Pemmaraju, Sriram V. Aalto Univ Espoo Finland Univ Iowa Iowa City IA USA

ISBN: (纸本)9781450392624

In this paper we present a deterministic O( log logn)-round algorithm for the 2-ruling set problem in the Massively Parallel Computation (MPC) model with O-similar to (n) memory;this algorithm also runs in O( log logn) rounds in the Congested Clique model. This is exponentially faster than the fastest known deterministic 2-ruling set algorithm for these models, which is simply the Omicron(log Delta)-round deterministic Maximal Independent Set (MIS) algorithm due to Czumaj, Davies, and Parter (SPAA 2020). Our result is obtained by derandomizing the 2-ruling set algorithm of Kothapalli and Pemmaraju (FSTTCS 2012).

关键词： Ruling Sets Massively Parallel Computing Congested Clique deterministic algorithm Derandomization

来源：评论

学校读者我要写书评

暂无评论

deterministic Approximate Methods for Maximum Consensus Robust Fitting

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2021年第3期43卷 842-857页

作者： Le, Huu Chin, Tat-Jun Eriksson, Anders Do, Thanh-Toan Suter, David Chalmers Univ Technol S-41296 Gothenburg Sweden Univ Adelaide Sch Comp Sci Adelaide SA 5005 Australia Univ Queensland Sch Informat Technol & Elect Engn Brisbane Qld 4072 Australia Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Edith Cowan Univ Sch Sci Joondalup WA 6027 Australia

Maximum consensus estimation plays a critically important role in several robust fitting problems in computer vision. Currently, the most prevalent algorithms for consensus maximization draw from the class of randomized hypothesize-and-verify algorithms, which are cheap but can usually deliver only rough approximate solutions. On the other extreme, there are exact algorithms which are exhaustive search in nature and can be costly for practical-sized inputs. This paper fills the gap between the two extremes by proposing deterministic algorithms to approximately optimize the maximum consensus criterion. Our work begins by reformulating consensus maximization with linear complementarity constraints. Then, we develop two novel algorithms: one based on non-smooth penalty method with a Frank-Wolfe style optimization scheme, the other based on the Alternating Direction Method of Multipliers (ADMM). Both algorithms solve convex subproblems to efficiently perform the optimization. We demonstrate the capability of our algorithms to greatly improve a rough initial estimate, such as those obtained using least squares or a randomized algorithm. Compared to the exact algorithms, our approach is much more practical on realistic input sizes. Further, our approach is naturally applicable to estimation problems with geometric residuals. Matlab code and demo program for our methods can be downloaded from https://***/FQcxpi.

关键词： Approximation algorithms Optimization Computer vision Mathematical model Estimation Computational modeling Data models Maximum consensus robust fitting deterministic algorithm approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Local Deal-Agreement algorithms for Load Balancing in Dynamic General Graphs

引用

THEORY OF COMPUTING SYSTEMS 2022年第2期67卷 348-382页

作者： Dinitz, Yefim Dolev, Shlomi Kumar, Manish Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

We study the classic load balancing problem on dynamic general graphs, where the graph changes arbitrarily between the computational rounds, remaining connected with no permanent cut. A lower bound of Omega (n(2)) for the running time bound in the dynamic setting, where n is the number of nodes in the graph, is known even for randomized algorithms. We solve the problem by deterministic distributed algorithms, based on a short local deal-agreement communication of proposal/deal in the neighborhood of each node. Our synchronous load balancing algorithms achieve a discrepancy of is an element of within the time of O(nDlog(nK/is an element of)) for the continuous setting and the discrepancy of at most 2D within the time of O(nDlog(nK/D)) and a 1-balanced state within the additional time of O(nD(2)) for the discrete setting, where K is the initial discrepancy, and D is a bound for the graph diameter. Also, the stability of the achieved 1-balanced state is studied. The above results are extended to the case of unbounded diameter, essentially keeping the time bounds, via special averaging of the graph diameter over time. Our algorithms can be considered anytime ones, in the sense that they can be stopped at any time during the execution, since they never make loads negative and never worsen the state as the execution progresses. In addition, we describe a version of our algorithms, where each node may transfer load to and from several neighbors at each round, as a heuristic for better performance. The algorithms are generalized to the asynchronous distributed model. We also introduce a self-stabilizing version of our asynchronous algorithms.

关键词： Load balancing Dynamic graph General graph deterministic algorithm Distributed algorithm Asynchronous system Self-stabilization

来源：评论

学校读者我要写书评

暂无评论

Byzantine gathering in polynomial time

引用

DISTRIBUTED COMPUTING 2022年第3期35卷 235-263页

作者： Bouchard, Sebastien Dieudonne, Yoann Lamani, Anissa Sorbonne Univ LIP6 CNRS F-75005 Paris France Univ Picardie Jules Verne Lab MIS Amiens France Ecole Int Sci Traitement Informat EISTI Cergy France

Gathering is a key task in distributed and mobile systems, which becomes significantly harder if some agents are subject to Byzantine faults, known as being the worst ones. We propose here to study the task of Byzantine gathering in an arbitrary graph: despite the presence of Byzantine agents, the goal is to ensure that all the other (good) agents, executing the same algorithm, eventually meet at the same node and stop. Initially, each agent gets as input a different label and some global knowledge that is common to all agents. The agents move in synchronous rounds and communicate with each other only when located at the same node. There are integral Byzantine agents. These agents act in an unpredictable way, e.g., they may convey arbitrary informations or forge any label. In the literature, the gathering algorithms working in such a context all have an exponential time complexity in the number n of nodes and the labels of the good agents. In this paper, we design a deterministic algorithm to solve Byzantine gathering in time polynomial in n and the logarithm integral of the smallest label of a good agent, provided the agents are a strong team i.e., a team where the number of good agents is at least some quadratic polynomial in f. Our algorithm requires global knowledge that can be coded in O(log log log n) bits: we prove this size is of optimal order of magnitude to obtain a polynomial time complexity in n and l with strong teams.

关键词： Gathering deterministic algorithm Mobile agent Byzantine fault Polynomial time

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：