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

Proceedings of the 55th Annual ACM Symposium on Theory of Computing

作者： Sébastien Bubeck Christian Coester Yuval Rabani Microsoft Research USA University of Oxford UK Hebrew University of Jerusalem Israel

ISBN: (纸本)9781450399135

We prove a few new lower bounds on the randomized competitive ratio for the k-server problem and other related problems, resolving some long-standing conjectures. In particular, for metrical task systems (MTS) we asympotically settle the competitive ratio and obtain the first improvement to an existential lower bound since the introduction of the model 35 years ago (in 1987). More concretely, we show: (1) There exist (k+1)-point metric spaces in which the randomized competitive ratio for the k-server problem is Ω(log2 k). This refutes the folklore conjecture (which is known to hold in some families of metrics) that in all metric spaces with at least k+1 points, the competitive ratio is Θ(logk). (2) Consequently, there exist n-point metric spaces in which the randomized competitive ratio for MTS is Ω(log2 n). This matches the upper bound that holds for all metrics. The previously best existential lower bound was Ω(logn) (which was known to be tight for some families of metrics). (3) For all krandomized k-server competitive ratio is at least Ω(logk), and consequently the randomized MTS competitive ratio is at least Ω(logn). These universal lower bounds are asymptotically tight. The previous bounds were Ω(logk/loglogk) and Ω(logn/loglogn), respectively. (4) The randomized competitive ratio for the w-set metrical service systems problem, and its equivalent width-w layered graph traversal problem, is Ω(w2). This slightly improves the previous lower bound and matches the recently discovered upper bound. (5) Our results imply improved lower bounds for other problems like k-taxi, distributed paging, and metric allocation. These lower bounds share a common thread, and other than the third bound, also a common construction.

关键词： randomized algorithms metrical task systems online computing competitive analysis $k$-server lower bounds

来源：评论

学校读者我要写书评

暂无评论

A note on the k-restriction problem

引用

Information Processing Letters 2025年 187卷

作者： Lin, Jing-You Tsai, Shi-Chun Department of Computer Science National Yang Ming Chiao Tung University Hsinchu Taiwan

Consider a set of demands, each taking length-k strings as input. The k-restriction problem is to construct a small set of length-m strings, such that given any k positions and any demand, there exists a string in the set satisfying the demand at these positions. The k-restriction problem relates to many problems, such as k-independent sets, covering arrays, and many other combinatorial applications. By considering the VC-dimension of demands, we prove bounds independent of the number of demands with the Lovász Local Lemma. As a result, we can prove better bounds for demands with finite VC-dimension. © 2024 Elsevier B.V.

关键词： randomized algorithms Lovász Local Lemma VC-dimension ϵ-net Probabilistic methods

来源：评论

学校读者我要写书评

暂无评论

Layered List Labeling

引用

Proceedings of the ACM on Management of Data 2024年第2期2卷 1-19页

作者： Michael A. Bender Alex Conway Martin Farach-Colton Hanna Komlós William Kuszmaul Stony Brook University and RelationalAI Stony Brook NY USA Cornell Tech New York NY USA New York University New York NY USA Harvard University Cambridge MA USA

The list-labeling problem is one of the most basic and well-studied algorithmic primitives in data structures, with an extensive literature spanning upper bounds, lower bounds, and data management applications. The classical algorithm for this problem, dating back to 1981, has amortized cost O(log bn). Subsequent work has led to improvements in three directions: low-latency (worst-case) bounds; high-throughput (expected) bounds; and (adaptive) bounds for important *** surprisingly, these three directions of research have remained almost entirely disjoint---this is because, so far, the techniques that allow for progress in one direction have forced worsening bounds in the others. Thus there would appear to be a tension between worst-case, adaptive, and expected bounds. List labeling has been proposed for use in databases at least as early as PODS'99, but a database needs good throughput, response time, and needs to adapt to common workloads (e.g., bulk loads), and no current list-labeling algorithm achieve good bounds for all *** show that this tension is not fundamental. In fact, with the help of new data-structural techniques, one can actually combine any three list-labeling solutions in order to cherry-pick the best worst-case, adaptive, and expected bounds from each of them.

关键词： algorithms data structures history independence online algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel Load Balancing on constrained client-server topologies

引用

THEORETICAL COMPUTER SCIENCE 2021年 895卷 16-33页

作者： Clementi, Andrea Natale, Emanuele Ziccardi, Isabella Univ Roma Tor Vergata Rome Italy Univ Cote Azur INRIA CNRS Sophia Antipolis France Univ Aquila Laquila Italy

We study parallel Load Balancing protocols for the client-server distributed model defined as follows. There is a set C of n clients and a set S of n servers where each client has (at most) a constant number d >= 1 of requests that must be assigned to some server. The client set and the server one are connected to each other via a fixed bipartite graph: the requests of client v can only be sent to the servers in its neighborhood N (v). The goal is to assign every client request so as to minimize the maximum load of the servers. In this setting, efficient parallel protocols are available only for dense topologies. In particular, a simple protocol, named RAES, has been recently introduced by Becchetti et al. [1] for regular dense bipartite graphs. They show that this symmetric, non-adaptive protocol achieves constant maximum load with parallel completion time O(logn) and overall work O(n), w.h.p. Motivated by proximity constraints arising in some client-server systems, we analyze RAES over almost-regular bipartite graphs where nodes may have neighborhoods of small size. In detail, we prove that, w.h.p., the RAES protocol keeps the same performances as above (in terms of maximum load, completion time, and work complexity, respectively) on any almost-regular bipartite graph with degree Omega(log(2) n). Our analysis significantly departs from that in [1] since it requires to cope with non-trivial stochastic-dependence issues on the random choices of the algorithmic process which are due to the worst-case, sparse topology of the underlying graph. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Parallel balanced allocations Balls-into-bins processes randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Query-competitive sorting with uncertainty

引用

THEORETICAL COMPUTER SCIENCE 2021年 867卷 50-67页

作者： Halldorsson, Magnus M. de Lima, Murilo Santos Reykjavik Univ Dept Comp Sci Menntavegi 1 IS-102 Reykjavik Iceland Univ Leicester Sch Informat Univ Rd Leicester LE1 7RH Leics England

We study the problem of sorting under incomplete information, when queries are used to resolve uncertainties. Each of n data items has an unknown value, which is known to lie in a given interval. We can pay a query cost to learn the actual value, and we may allow an error threshold in the sorting. The goal is to find a nearly-sorted permutation by performing a minimum-cost set of queries. We show that an offline optimum query set can be found in polynomial time, and that both oblivious and adaptive problems have simple query-competitive algorithms. The query competitiveness for the oblivious problem is n for uniform query costs, and unbounded for arbitrary costs;for the adaptive problem, the ratio is 2. We then present a unified adaptive strategy for uniform query costs that yields the following improved results: (i) a 3/2-query-competitive randomized algorithm;(ii) a 5/3-query competitive deterministic algorithm if the dependency graph has no 2-components after some preprocessing, which has query-competitive ratio 3/2 + O(1/k) if the components obtained have size at least k;and (iii) an exact algorithm if the intervals constitute a laminar family. The first two results have matching lower bounds, and we have a lower bound of 7/5 for large components. We also give a randomized adaptive algorithm with query-competitive factor 1 + 4/3 root 3 approximate to 1.7698 for arbitrary query costs, and we show that the 2-query competitive deterministic adaptive algorithm can be generalized for queries returning intervals and for a more general graph problem (which is also a generalization of the vertex cover problem), by using the local ratio technique. Furthermore, we prove that the advice complexity of the adaptive problem is left perpendicularn/2right perpendicular if no error threshold is allowed, and inverted left perpendicularn/3 lg 3inverted right perpendicular for the general case. Finally, we present some graph-theoretical results regarding co-threshold tolerance grap

关键词： Online algorithms Sorting randomized algorithms Advice complexity Threshold tolerance graphs

来源：评论

学校读者我要写书评

暂无评论

Estimating the Longest Increasing Subsequence in Nearly Optimal Time 63

Estimating the Longest Increasing Subsequence in Nearly Opti...

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Andoni, Alexandr Nosatzki, Negev Shekel Sinha, Sandip Stein, Clifford Columbia Univ New York NY 10027 USA

ISBN: (纸本)9781665455190

Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence, and has been studied for decades. While the LIS of a sequence of length n can be computed exactly in time O(n log n), the complexity of estimating the (length of the) LIS in sublinear time, especially when LIS << n, is still open. We show that for any n is an element of N and lambda = o(1), there exists a (randomized) non-adaptive algorithm that, given a sequence of length n with LIS >= lambda n, approximates the LIS up to a factor of 1/lambda(o(1)) in n(o(1))/lambda time. Our algorithm improves upon prior work substantially in terms of both approximation and run-time: (i) we provide the first sub-polynomial approximation for LIS in sub-linear time;and (ii) our run-time complexity essentially matches the trivial sample complexity lower bound of Omega(1/lambda), which is required to obtain any non-trivial approximation of the LIS. As part of our solution, we develop two novel ideas which may be of independent interest. First, we define a new Genuine-LIS problem, in which each sequence element may be either genuine or corrupted. In this model, the user receives unrestricted access to the actual sequence, but does not know a priori which elements are genuine. The goal is to estimate the LIS using genuine elements only, with the minimal number of tests for genuineness. The second idea, Precision Tree, enables accurate estimations for composition of general functions from "coarse" (sub-)estimates. Precision Tree essentially generalizes classical precision sampling, which works only for summations. As a central tool, the Precision Tree is pre-processed on a set of samples, which thereafter is repeatedly used by multiple components of the algorithm, improving their amortized complexity.

关键词： sublinear algorithms approximation algorithms randomized algorithms longest increasing subsequence string algorithms

来源：评论

学校读者我要写书评

暂无评论

Phase Transition of the 3-Majority Dynamics with Uniform Communication Noise 1

引用

29th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： d'Amore, Francesco Ziccardi, Isabella Univ Cote Azur INRIA CNRS I3S Sophia Antipolis France Univ Aquila Laquila Italy

ISBN: (数字)9783031099939

ISBN: (纸本)9783031099939;9783031099922

Communication noise is a common feature in several real-world scenarios where systems of agents need to communicate in order to pursue some collective task. In particular, many biologically inspired systems that try to achieve agreements on some opinion must implement resilient dynamics that are not strongly affected by noisy communications. In this work, we study the popular 3-Majority dynamics, an opinion dynamics which has been proved to be an efficient protocol for the majority consensus problem, in which we introduce a simple feature of uniform communication noise, following (d'Amore et al. 2020). We prove that in the fully connected communication network of n agents and in the binary opinion case, the process induced by the 3-Majority dynamics exhibits a phase transition. For a noise probability p < 1/3, the dynamics reaches in logarithmic time an almost-consensus metastable phase which lasts for a polynomial number of rounds with high probability. Furthermore, departing from previous analyses, we further characterize this phase by showing that there exists an attractive equilibrium value s(eq) is an element of [n] for the bias of the system, i.e. the difference between the majority community size and the minority one. Moreover, the agreement opinion turns out to be the initial majority one if the bias towards it is of magnitude Omega(root n log n) in the initial configuration. If, instead, p > 1/3, no form of consensus is possible, and any information regarding the initial majority opinion is lost in logarithmic time with high probability. Despite more communications per-round are allowed, the 3-Majority dynamics surprisingly turns out to be less resilient to noise than the Undecided-State dynamics (d'Amore et al. 2020), whose noise threshold value is p = 1/2.

关键词： Opinion dynamics Consensus Problem Communication Noise randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function

引用

algorithms 2025年第3期18卷 140-140页

作者： Schulhof, Noah Sukprasert, Pattara Ruppin, Eytan Khuller, Samir Schaffer, Alejandro A. NCI NIH Canc Data Sci Lab Bethesda MD 20892 USA Northwestern Univ Dept Comp Sci Evanston IL 60201 USA Databricks Inc San Francisco CA 94105 USA

Integer linear programs (ILPs) and mixed integer programs (MIPs) often have multiple distinct optimal solutions, yet the widely used Gurobi optimization solver returns certain solutions at disproportionately high frequencies. This behavior is disadvantageous, as, in fields such as biomedicine, the identification and analysis of distinct optima yields valuable domain-specific insights that inform future research directions. In the present work, we introduce MORSE (Multiple Optima via Random Sampling and careful choice of the parameter Epsilon), a randomized, parallelizable algorithm to efficiently generate multiple optima for ILPs. MORSE maps multiplicative perturbations to the coefficients in an instance's objective function, generating a modified instance that retains an optimum of the original problem. We formalize and prove the above claim in some practical conditions. Furthermore, we prove that for 0/1 selection problems, MORSE finds each distinct optimum with equal probability. We evaluate MORSE using two measures;the number of distinct optima found in r independent runs, and the diversity of the list (with repetitions) of solutions by average pairwise Hamming distance and Shannon entropy. Using these metrics, we provide empirical results demonstrating that MORSE outperforms the Gurobi method and unweighted variations of the MORSE method on a set of 20 Mixed Integer Programming Library (MIPLIB) instances and on a combinatorial optimization problem in cancer genomics.

关键词： integer linear program selection problems multiple optima randomized algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Bidirectional stochastic configuration network for regression problems

引用

NEURAL NETWORKS 2021年 140卷 237-246页

作者： Cao, Weipeng Xie, Zhongwu Li, Jianqiang Xu, Zhiwu Ming, Zhong Wang, Xizhao Shenzhen Univ Coll Comp Sci & Software Engn Shenzhen 518060 Peoples R China

To adapt to the reality of limited computing resources of various terminal devices in industrial applications, a randomized neural network called stochastic configuration network (SCN), which can conduct effective training without GPU, was proposed. SCN uses a supervisory random mechanism to assign its input weights and hidden biases, which makes it more stable than other randomized algorithms but also leads to time-consuming model training. To alleviate this problem, we propose a novel bidirectional SCN algorithm (BSCN) in this paper, which divides the way of adding hidden nodes into two modes: forward learning and backward learning. In the forward learning mode, BSCN still uses the supervisory mechanism to configure the parameters of the newly added nodes, which is the same as SCN. In the backward learning mode, BSCN calculates the parameters at one time based on the residual error feedback of the current model. The two learning modes are performed iteratively until the prediction error of the model reaches an acceptable level or the number of hidden nodes reaches its maximum value. This semi-random learning mechanism greatly speeds up the training efficiency of the BSCN model and significantly improves the quality of the hidden nodes. Extensive experiments on ten benchmark regression problems, two real-life air pollution prediction problems, and a classical image processing problem show that BSCN can achieve faster training speed, higher stability, and better generalization ability than SCN. (C) 2021 Elsevier Ltd. All rights reserved.

关键词： Stochastic configuration network Random vector functional link network randomized algorithms Neural networks with random weights Constructive neural networks

来源：评论

学校读者我要写书评

暂无评论

Derandomization for Sliding Window algorithms with Strict Correctness*

引用

THEORY OF COMPUTING SYSTEMS 2021年第3期65卷 444-461页

作者： Ganardi, Moses Hucke, Danny Lohrey, Markus Univ Siegen Holderlinstr 3 D-57076 Siegen Germany

In the sliding window streaming model the goal is to compute an output value that only depends on the lastnsymbols from the data stream. Thereby, only space sublinear in the window sizenshould be used. Quite often randomization is used in order to achieve this goal. In the literature, one finds two different correctness criteria for randomized sliding window algorithms: (i) one can require that for every data stream and every time instantt, the algorithm computes a correct output value with high probability, or (ii) one can require that for every data stream the probability that the algorithm computes at every time instant a correct output value is high. Condition (ii) is stronger than (i) and is called "strict correctness" in this paper. The main result of this paper states that every strictly correct randomized sliding window algorithm can be derandomized without increasing the worst-case space consumption.

关键词： Streaming algorithms Sliding window algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：