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

Tight Bounds for Online Weighted Tree Augmentation

algorithmICA 2022年第2期84卷 304-324页

作者： Naor, Joseph (Seffi) Umboh, Seeun William Williamson, David P. Technion Haifa Israel Univ Sydney Sydney NSW Australia Cornell Univ Ithaca NY USA

The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this paper, we consider this problem in the online setting. We are given an n-vertex tree T = (V, E) and an additional set L subset of ((V)(2)) of edges (called links) with costs. Then, terminal pairs arrive one-by-one and our task is to maintain a low-cost subset of links F such that every terminal pair that has arrived so far is 2-edge-connected in T boolean OR F. This online problem was first studied by Gupta, Krishnaswamy and Ravi (SICOMP 2012) who used it as a subroutine for the online survivable network design problem. They gave a deterministic O(log 2 n)-competitive algorithm and showed an Omega (log n) lower bound on the competitive ratio of randomized algorithms. The case when T is a path is also interesting: it is exactly the online interval set cover problem, which also captures as a special case the parking permit problem studied by Meyerson (FOCS 2005). The contribution of this paper is to give tight results for online weighted tree and path augmentation problems. The main result of this work is a deterministic O (log n)-competitive algorithm for online WTAP, which is tight up to constant factors.

关键词： randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

The complexity of leader election in diameter-two networks

引用

DISTRIBUTED COMPUTING 2020年第2期33卷 189-205页

作者： Chatterjee, Soumyottam Pandurangan, Gopal Robinson, Peter Univ Houston Houston TX 77204 USA McMaster Univ Hamilton ON Canada

This paper focuses on studying the message complexity of implicit leader election in synchronous distributed networks of diameter two. Kutten et al. (J ACM 62(1):7:1-7:27, 2015) showed a fundamental lower bound of Omega(m) (m is the number of edges in the network) on the message complexity of (implicit) leader election that applied also to Monte Carlo randomized algorithms with constant success probability;this lower bound applies for graphs that have diameter at least three. On the other hand, for complete graphs (i.e., graphs with diameter one), Kutten et al. (Theor Comput Sci 561(Part B):134-143, 2015) established a tight bound of (Theta) over tilde(root n) on the message complexity of randomized leader election (n is the number of nodes in the network). For graphs of diameter two, the complexity was not known. In this paper, we settle this complexity by showing a tight bound of (Theta) over tilde (n) on the message complexity of leader election in diameter-two networks. We first give a simple randomized Monte-Carlo leader election algorithm that with high probability (i.e., probability at least 1 - n(-c), for some fixed positive constant c) succeeds and uses O(n log(3) n) messages and runs in O(1) rounds;this algorithm works without knowledge of n (and hence needs no global knowledge). We then show that any algorithm (even Monte Carlo randomized algorithms with large enough constant success probability) needs O(n) messages (even when n is known), regardless of the number of rounds. We also present an O(n log n) message deterministic algorithm that takes O(log n) rounds (but needs knowledge of n);we show that this message complexity is tight for deterministic algorithms. Together with the two previous results of Kutten et al., our results fully characterize the message complexity of leader election vis-a-vis the graph diameter.

关键词： Distributed algorithm Leader election randomized algorithm Message complexity Time complexity Lower bound

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT algorithmS FOR THE HITCHCOCK TRANSPORTATION PROBLEM

引用

SIAM JOURNAL ON COMPUTING 1995年第3期24卷 563-578页

作者： TOKUYAMA, T NAKANO, J IBM Research Kanagawa Japan

We consider the Hitchcock transportation problem on n supply points and k demand points when n is much greater than k. The problem can be solved in O(kn(2) log n + n(2) log(2) n) time if an efficient minimum-cost flow algorithm is directly applied. Applying a geometric method named splitter finding and a randomization technique. we can improve the time complexity when the ratio c of the maximum supply to the minimum supply is sufficiently small. The expected running time of our randomized algorithm is O(kn log cn/log(n/k(4) log(2) k)) if n > k(4) log(2) k, and O(k(5) log(2) n log cn) if n less than or equal to k(4) log(2) k. If n = Omega(k(4+epsilon) (epsilon > 0) and c = poly(n), the problem is solved in O(kn) time, which is optimal.

关键词： TRANSPORTATION PROBLEM COMPUTATIONAL GEOMETRY randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

High-performance sorting algorithms for the CRAY T3D parallel computer

引用

JOURNAL OF SUPERCOMPUTING 1997年第4期10卷 371-395页

作者： Dixon, B Swallow, J DAVIDSON COLL DEPT MATHDAVIDSONNC 28036 CTR COMMUN RES PRINCETONNJ

In this paper we study the sorting performance of a 128-processor CRAY T3D and discuss the efficient use of the toroidal network connecting the processors. The problems we consider range from that of sorting one word per processor to sorting the entire memory of the machine, and we give efficient algorithms for each case. In addition, we give both algorithms that make assumptions about the distribution of the data and those that make no assumptions. The clear winner, if data can be assumed to be uniformly distributed, is a method that we call a hash-and-chain sort. The time for this algorithm to sort one million words per processor over 64 processors is less than two seconds, which compares favorably to about four seconds using a 4-processor CRAY C90 and about 17 seconds using a 64-processor Thinking Machines CM-5.

关键词： parallel algorithm quicksort radix sort randomized algorithm distributed-memory multiprocessing

来源：评论

学校读者我要写书评

暂无评论

Distributed (Δ+1)-coloring in the physical model

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期553卷 37-56页

作者： Yu, Dongxiao Wang, Yuexuan Hua, Qiang-Sheng Lau, Francis C. M. Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China

In multi-hop radio networks, such as wireless ad-hoc networks and wireless sensor networks, nodes employ a MAC (Medium Access Control) protocol such as TDMA to coordinate accesses to the shared medium and to avoid interference of close-by transmissions. These protocols can be implemented using standard node coloring. The (Delta + 1)-coloring problem is to color all nodes in as few timeslots as possible using at most Delta + 1 colors such that any two nodes within distance R are assigned different colors, where R is a given parameter and Delta is the maximum degree of the modeled unit disk graph using R as a scaling factor. Being one of the most fundamental problems in distributed computing, this problem is well studied and there is a long chain of algorithms prescribed for it. However, all previous works are based on abstract models, such as message passing models and graph based interference models, which limit the utility of these algorithms in practice. In this paper, for the first time, we consider the distributed (Delta + 1)-coloring problem under the more practical SINR interference model. In particular, without requiring any knowledge about the neighborhood, we propose a novel randomized (Delta + 1)-coloring algorithm with time complexity O (Delta log n + log(2) n). For the case where nodes cannot adjust their transmission power, we give an O (Delta log(2) n) randomized algorithm, which only incurs a logarithmic multiplicative factor overhead. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Distributed algorithm randomized algorithm Wireless ad-hoc and sensor networks Coloring Physical interference model

来源：评论

学校读者我要写书评

暂无评论

An Improved Approximation algorithm for Knapsack Median Using Sparsification

引用

algorithmICA 2018年第4期80卷 1093-1114页

作者： Byrka, Jaroslaw Pensyl, Thomas Rybicki, Bartosz Spoerhase, Joachim Srinivasan, Aravind Khoa Trinh Univ Wroclaw Inst Comp Sci Wroclaw Poland Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA

Knapsack median is a generalization of the classic k-median problem in which we replace the cardinality constraint with a knapsack constraint. It is currently known to be 32-approximable. We improve on the best known algorithms in several ways, including adding randomization and applying sparsification as a preprocessing step. The latter improvement produces the first LP for this problem with bounded integrality gap. The new algorithm obtains an approximation factor of 17.46. We also give a 3.05 approximation with small budget violation.

关键词： Approximation algorithm Combinatorial optimization randomized algorithm Facility-location problems

来源：评论

学校读者我要写书评

暂无评论

Simultaneous Perturbation Stochastic Approximation-Based Consensus for Tracking Under Unknown-But-Bounded Disturbances

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2021年第8期66卷 3710-3717页

作者： Granichin, Oleg Erofeeva, Victoria Ivanskiy, Yury Jiang, Yuming St Petersburg State Univ Sci & Educ Ctr Math Robot & Artificial Intelligen St Petersburg 198504 Russia Norwegian Univ Sci & Technol NTNU Dept Informat Secur & Commun Technol NO-7491 Trondheim Norway

We consider a setup where a distributed set of sensors working cooperatively can estimate an unknown signal of interest, whereas any individual sensor cannot fulfill the task due to lack of necessary information diversity. This article deals with these kinds of estimation and tracking problems and focuses on a class of simultaneous perturbation stochastic approximation (SPSA)-based consensus algorithms for the cases when the corrupted observations of sensors are transmitted between sensors with communication noise and the communication protocol has to satisfy a prespecified cost constraints on the network topology. Sufficient conditions are introduced to guarantee the stability of estimates obtained in this way, without resorting to commonly used but stringent conventional statistical assumptions about the observation noise, such as randomness, independence, and zero mean. We derive an upper bound of the mean square error of the estimates in the problem of unknown time-varying parameters tracking under unknown-but-bounded observation errors and noisy communication channels. The result is illustrated by a practical application to the multisensor multitarget tracking problem.

关键词： Sensors Approximation algorithms Optimization Noise measurement Perturbation methods Network topology Upper bound Arbitrary noise consensus algorithm distributed tracking multiagent networks randomized algorithm simultaneous perturbation stochastic approximation (SPSA) stochastic stability tracking performance unknown-but-bounded disturbances

来源：评论

学校读者我要写书评

暂无评论

Large independent sets in general random intersection graphs

引用

THEORETICAL COMPUTER SCIENCE 2008年第3期406卷 215-224页

作者： Nikoletseas, S. Raptopoulos, C. Spirakis, P. Comp Technol Inst GR-26110 Patras Greece Univ Patras Patras 26500 Greece

We investigate the existence and efficient algorithmic construction of close to optimal independent sets in random models of intersection graphs. In particular, (a) we propose a new model for random intersection graphs (G(n),(m),((p) over right arrow)) which includes the model of [M. Karonski, E.R. Scheinerman, K.B. Singer-Cohen, On random intersection graphs: The subgraph problem, Combinatorics, Probability and Computing journal 8 (1999), 131-159] (the "uniform" random intersection graph models) as an important special case. We also define an interesting variation of the model of random intersection graphs, similar in spirit to random regular graphs. (b) For this model we derive exact formulae for the mean and variance of the number of independent sets of size k (for any k) in the graph. (c) We then propose and analyse three algorithms for the efficient construction of large independent sets in this model. The first two are variations of the greedy technique while the third is a totally new algorithm. Our algorithms are analysed for the special case of uniform random intersection graphs. Our analyses show that these algorithms succeed in finding close to optimal independent sets for an interesting range of graph parameters. (c) 2008 Elsevier B.V. All rights reserved.

关键词： Random intersection graph randomized algorithm Independent set Wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

Nonlinear Monotonically Convergent Iterative Learning Control for Batch Processes

引用

IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS 2018年第7期65卷 5826-5836页

作者： Lu, Jingyi Cao, Zhixing Zhang, Ridong Gao, Furong Hong Kong Univ Sci & Technol Fok Ying Tung Grad Sch Kowloon Hong Kong Peoples R China Univ Edinburgh Sch Biol Sci Edinburgh EH9 3JH Midlothian Scotland Hong Kong Univ Sci & Technol Dept Chem & Biol Engn Kowloon Hong Kong Peoples R China

Iterative learning control (ILC) has been successfully applied to numerous batch processes over the past decades. Monotonic convergence of tracking error is a desired characteristic that attracts much attention in academia. Many factors arising in industrial practice, such as strong nonlinearity and parameter uncertainty, have challenged the most existing monotonically convergent ILC approaches. This motivates the development of the nonlinear monotonically convergent ILC (NMC-ILC) in this paper. The proposed NMC-ILC is an optimization-based control strategy, in which the original nonlinear process is linearly approximated to reduce the complexity of the optimization problem accompanied. An upper bound of the tracking error is derived by considering the effects of model mismatches that consist of two components: structural mismatch induced by the linearization and parametric mismatch arising from the indetermination of process parameters. The NMC-ILC is then devised by minimizing this upper bound. Numerical experiments are conducted on an ILC-testing benchmark and the velocity control in an injection molding process.

关键词： Batch processes iterative learning control (ILC) monotonic convergence (MC) nonlinear system randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

On fractional cut covers

引用

DISCRETE APPLIED MATHEMATICS 2019年 265卷 168-181页

作者： Neto, Jose Ben-Ameur, Walid Telecom SudParis CNRS Samovar 9 Rue Charles Fourier F-91011 Evry France

Given an undirected graph, a minimum cut cover is a collection of cuts covering the whole set of edges and having minimum cardinality. This paper is dedicated to the fractional version of this problem where a fractional weight is computed for each cut such that, for each edge, the sum of the weights of all cuts containing it is no less than 1, while the sum of all weights is minimized. The fractional cover is computed for different graph classes among which are the weakly bipartite graphs. Efficient algorithms are described to compute lower and upper bounds with worst-case performance guarantees. A general randomized approach is also presented giving new insights into Goemans and Williamson's algorithm for the maximum cut problem. Some numerical experiments are included to assess the quality of bounds. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Graph cuts Covering Approximation randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：