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

Online Stochastic Matching: New algorithms and Bounds

ALGORITHMICA 2020年第10期82卷 2737-2783页

作者： Brubach, Brian Sankararaman, Karthik Abinav Srinivasan, Aravind Xu, Pan Univ Maryland College Pk MD 20742 USA New Jersey Inst Technol Newark NJ 07102 USA

Online matching has received significant attention in recent years due to its close connection to Internet advertising. As the seminal work of Karp, Vazirani, and Vazirani has an optimal (1 - 1/ ) competitive ratio in the standard adversarial online model, much effort has gone into developing useful online models that incorporate some stochasticity in the arrival process. One such popular model is the "known I.I.D. model" where different customer-types arrive online from a known distribution. We develop algorithms with improved competitive ratios for some basic variants of this model with integral arrival rates, including: (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to Haeupler, Mirrokni and Zadimoghaddam (WINE, 2011) to 0.705;and (b) the vertexweighted case, where we improve the 0.7250 ratio of Jaillet and Lu (Math Oper Res 39(3):624-646, 2013) to 0.7299. We also consider an extension of stochastic rewards, a variant where each edge has an independent probability of being present. For the setting of stochastic rewards with non-integral arrival rates, we present a simple optimal non-adaptive algorithm with a ratio of 1 - 1/ . For the special case where each edge is unweighted and has a uniform constant probability of being present, we improve upon 1 - 1/ by proposing a strengthened LP benchmark. One of the key ingredients of our improvement is the following (offline) approach to bipartite-matching polytopes with additional constraints. We first add several valid constraints in order to get a good fractional solution;however, these give us less control over the structure of . We next remove all these additional constraints and randomly move from to a feasible point on the matching polytope with all coordinates being from the set {0, 1/k, 2/k,., 1} for a chosen integer k. The structure of this solution is inspired by Jaillet and Lu (2013) and is a tractable structure for algorithm design and analysis. The appropriate rand

关键词： Online algorithms randomized algorithms Bipartite matching Internet advertising

来源：评论

学校读者我要写书评

暂无评论

NEARLY WORK-EFFICIENT PARALLEL ALGORITHM FOR DIGRAPH REACHABILITY

引用

SIAM JOURNAL ON COMPUTING 2020年第5期49卷 STOC18-500-STOC18-539页

作者： Fineman, Jeremy T. Georgetown Univ Dept Comp Sci Washington DC 20057 USA

One of the simplest problems on directed graphs is that of identifying the set of vertices reachable from a designated source vertex. This problem can be solved easily sequentially by performing a graph search, but efficient parallel algorithms have eluded researchers for decades. For sparse high-diameter graphs in particular, there is no known work-efficient parallel algorithm with nontrivial parallelism. This amounts to one of the most fundamental open questions in parallel graph algorithms: Is there a parallel algorithm for digraph reachability with nearly linear work? This article shows that the answer is yes, presenting a randomized parallel algorithm for digraph reachability and related problems with expected work o(m) and span (O) over tilde (n(2/3)), and hence parallelism (O) over tilde (m/n(2/3)) = (Omega) over tilde (n(1/3)), on any graph with n vertices and m arcs. This is the first parallel algorithm having both nearly linear work and strongly sublinear span, i.e., span (O) over tilde (n(1-is an element of)) for any constant is an element of > 0. The algorithm can be extended to produce a directed spanning tree, determine whether the graph is acyclic, topologically sort the strongly connected components of the graph, or produce a directed ear decomposition, all with work (O) over tilde (m) and span (O) over tilde (n(2/3)). The main technical contribution is an efficient Monte Carlo algorithm that, through the addition of a(n) shortcuts, reduces the diameter of the graph to (O) over tilde (n(2/3)) with high probability. While both sequential and parallel algorithms are known with those combinatorial properties, even the sequential algorithms are not efficient, having sequential runtime Omega(mn(Omega(1))). This article presents a surprisingly simple sequential algorithm that achieves the stated diameter reduction and runs in (O) over tilde (m) time. Parallelizing that algorithm yields the main result, but doing so involves overcoming several other challen

关键词： parallel algorithms randomized algorithms graph search reachability shortcuts

来源：评论

学校读者我要写书评

暂无评论

Randomness as source for inspiring solution search methods: Music based approaches

引用

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2020年 537卷 122650-000页

作者： Altay, Elif Varol Alatas, Bilal Firat Univ Dept Software Engn Elazig Turkey

As the world progresses towards industrialization, engineering problems become increasingly complex and it becomes even more difficult to optimize these problems. The reason for this is the increasing complexity of variables, dimensions, space complexity, and time complexity. In order to be able to cope with such a situation, randomized intelligent optimization and search algorithms are proposed to optimize numerical benchmarking problems, multi-objective problems, and solve difficult problems including a large number of variables, dimensions, constraints, and objectives. Metaheuristic random search and optimization methods are widely used to search and find the most appropriate solutions for large-scale optimization problems in an acceptable time. They are general-purposed methods that can be efficiently applied to optimization and search problems without too much modification to accommodate a specific probing. Metaheuristic optimization algorithms are generally categorized as physics, music, sociology, biology, swarm, mathematics, plant, chemistry, sports, water, and hybrid based. Although most of the intelligent metaheuristic methods are inspired by physics and biology: concepts, activities, rules, and processes in music can be an inspiration source of new intelligent optimization and search techniques. That is why;novel and efficient music inspired intelligent optimization and search methods having effective exploitation and exploration capabilities have been proposed. In this paper, music based metaheuristic optimization algorithms were gathered and analyzed for the first time. Harmony search and its versions, melody search algorithm, and method of musical composition have been examined in detail. Furthermore, their performances have been compared within both unconstrained numerical benchmark functions and constrained problems and the obtained results from music based algorithms have been comparatively studied. (C) 2019 Elsevier B.V. All rights reserved.

关键词： randomized algorithms Global optimization Music based optimization algorithms Constrained G-suite functions Benchmark functions

来源：评论

学校读者我要写书评

暂无评论

The Online Reservation Problem

引用

algorithms 2020年第10期13卷 241页

作者： Goyal, Shashank Gupta, Diwakar Univ Minnesota Twin Cities Dept Ind & Syst Engn Minneapolis MN 55455 USA Univ Texas Austin McCombs Sch Business Austin TX 78705 USA

Many sharing-economy platforms operate as follows. Owners list the availability of resources, prices, and contract-length limits. Customers propose contract start times and lengths. The owners decide immediately whether to accept or decline each proposal, even if the contract is for a future date. Accepted proposals generate revenue. Declined proposals are lost. At any decision epoch, the owner has no information regarding future proposals. The owner seeks easy-to-implement algorithms that achieve the best competitive ratio (CR). We first derive a lower bound on the CR of any algorithm. We then analyze CRs of all intuitive "greedy" algorithms. We propose two new algorithms that have significantly better CRs than that of any greedy algorithm for certain parameter-value ranges. The key idea behind these algorithms is that owners may reserve some amount of capacity for late-arriving higher-value proposals in an attempt to improve revenue. Our contribution lies in operationalizing this idea with the help of algorithms that utilize thresholds. Moreover, we show that if non-optimal thresholds are chosen, then those may lead to poor CRs. We provide a rigorous method by which an owner can decide the best approach in their context by analyzing the CRs of greedy algorithms and those proposed by us.

关键词： online algorithms randomized algorithms competitive ratio interval scheduling online optimization

来源：评论

学校读者我要写书评

暂无评论

Periodicity in Data Streams with Wildcards

引用

THEORY OF COMPUTING SYSTEMS 2020年第1期64卷 177-197页

作者： Ergun, Funda Grigorescu, Elena Azer, Erfan Sadeqi Zhou, Samson Indiana Univ Sch Informat & Comp Bloomington IN 47405 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

We investigate the problem of detecting periodic trends within a string S of length n, arriving in the streaming model, containing at most k wildcard characters, where k = o(n). A wildcard character is a special character that can be assigned any other character. We say that S has wildcard-period p if there exists an assignment to each of the wildcard characters so that in the resulting stream the prefix of length n - p equals the suffix of length n - p. We present a two-pass streaming algorithm that computes wildcard-periods of S using O(k3 polylog n) bits of space, while we also show that this problem cannot be solved in sublinear space in one pass. We also give a one-pass randomized streaming algorithm that computes all wildcard-periods p of S withp < n2 and no wildcard characters appearing in the last p symbols of S, using O(k3 log9 n) space.

关键词： Streaming algorithms Periodicity Wildcards randomized algorithms String algorithms

来源：评论

学校读者我要写书评

暂无评论

Effective Data-Aware Covariance Estimator From Compressed Data

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2020年第7期31卷 2441-2454页

作者： Chen, Xixian Yang, Haiqin Zhao, Shenglin Lyu, Michael R. King, Irwin Tencent Youtu Lab Shenzhen 518057 Peoples R China Meitu Hong Kong Peoples R China Hang Seng Univ Hong Kong Dept Comp Hong Kong Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Peoples R China Chinese Univ Hong Kong Shenzhen Res Inst Shenzhen 518057 Peoples R China

Estimating covariance matrix from massive high-dimensional and distributed data is significant for various real-world applications. In this paper, we propose a data-aware weighted sampling-based covariance matrix estimator, namely DACE, which can provide an unbiased covariance matrix estimation and attain more accurate estimation under the same compression ratio. Moreover, we extend our proposed DACE to tackle multiclass classification problems with theoretical justification and conduct extensive experiments on both synthetic and real-world data sets to demonstrate the superior performance of our DACE.

关键词： Covariance matrices Sparse matrices Silicon Estimation Distributed databases Learning systems Dimensionality reduction Covariance estimation dimension reduction randomized algorithms unsupervised learning

来源：评论

学校读者我要写书评

暂无评论

A Power-of-Two Choices Based Algorithm for Fog Computing

引用

IEEE TRANSACTIONS ON CLOUD COMPUTING 2020年第3期8卷 698-709页

作者： Beraldi, Roberto Alnuweiri, Hussein Mtibaa, Abderrahmen Univ Roma La Sapienza DIAG I-00185 Rome Italy Texas A&M Univ Qatar Dept Elect & Comp Engn Doha 1111 Qatar New Mexico State Univ USA Dept Comp Sci College Stn TX 77843 USA

The fog computing paradigm brings together storage, communication, and computation resources closer to users' end-devices. Therefore, fog servers are deployed at the edge of the network, offering low latency access to users. With the expansion of such fog computing services, different providers will be able to deploy multiple resources within a restricted geographical proximity. In this paper, we investigate an incentive-based cooperation scheme across fog providers. We propose a distributed cooperative algorithm amongst fog computing providers where fully collaborative fog nodes are subject to different loads. The proposed algorithm leverages the power-of-two result and exploits a cooperation probability, namely the probability that a given provider collaborates by accepting a computation request from another provider, as a mean to achieve a fair cooperation. We adopt an analytical approach based on exploiting a simplified performance model to demonstrate numerically that a set of optimal accepting probabilities exits when the number of server nodes goes to infinity. This result then drives the design of our distributed algorithm. Second, in our experimental approach, we perform a set of simulation analysis to verify the validity of the proposed solution when the number of servers is limited.

关键词： randomized algorithms cooperation Markov chains

来源：评论

学校读者我要写书评

暂无评论

Detecting possibly frequent change-points: Wild Binary Segmentation 2 and steepest-drop model selection

引用

JOURNAL OF THE KOREAN STATISTICAL SOCIETY 2020年第4期49卷 1027-1070页

作者： Fryzlewicz, Piotr London Sch Econ Dept Stat Houghton St London WC2A 2AE England

Many existing procedures for detecting multiple change-points in data sequences fail in frequent-change-point scenarios. This article proposes a new change-point detection methodology designed to work well in both infrequent and frequent change-point settings. It is made up of two ingredients: one is "Wild Binary Segmentation 2" (WBS2), a recursive algorithm for producing what we call a 'complete' solution path to the change-point detection problem, i.e. a sequence of estimated nested models containing 0, horizontal ellipsis ,T-1 change-points, where T is the data length. The other ingredient is a new model selection procedure, referred to as "Steepest Drop to Low Levels" (SDLL). The SDLL criterion acts on the WBS2 solution path, and, unlike many existing model selection procedures for change-point problems, it is not penalty-based, and only uses thresholding as a certain discrete secondary check. The resulting *** procedure, combining both ingredients, is shown to be consistent, and to significantly outperform the competition in the frequent change-point scenarios tested. *** is fast, easy to code and does not require the choice of a window or span parameter.

关键词： Segmentation Break detection Jump detection randomized algorithms Adaptive algorithms Multiscale methods

来源：评论

学校读者我要写书评

暂无评论

A Lower Bound on Cycle-Finding in Sparse Digraphs

引用

ACM TRANSACTIONS ON algorithms 2022年第4期18卷 31-31页

作者： Chen, Xi Randolph, Tim Servedio, Rocco A. Sun, Timothy Columbia Univ Comp Sci Dept 500 W 120th StRoom 450MC 0401 New York NY 10027 USA

We consider the problem of finding a cycle in a sparse directed graphG that is promised to be far from acyclic, meaning that the smallest feedback arc set, i.e., a subset of edges whose deletion results in an acyclic graph, in G is large. We prove an information-theoretic lower bound, showing that for N-vertex graphs with constant outdegree, any algorithm for this problem must make (Omega) over tilde (N-5/9) queries to an adjacency list representation of G. In the language of property testing, our result is an (Omega) over tilde (N-5/9) lower bound on the query complexity of one-sided algorithms for testing whether sparse digraphs with constant outdegree are far from acyclic. This is the first improvement on the O(v N) lower bound, implicit in the work of Bender and Ron, which follows from a simple birthday paradox argument.

关键词： Property testing directed acyclic graphs randomized algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal Matchings with One-Sided Preferences: Fixed and Cost-Based Quotas 22

Optimal Matchings with One-Sided Preferences: Fixed and Cost...

引用

Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems

作者： Santhini K. A. Govind S. Sankar Meghana Nasre Indian Institute of Technology Madras Madras India Duke University Durham NC USA

ISBN: (纸本)9781450392136

We consider the well-studied many-to-one bipartite matching problem of assigning applicants A to posts P where applicants rank posts in the order of preference. This setting models many important real-world allocation problems like assigning students to courses, applicants to jobs, amongst many others. In such scenarios, it is natural to ask for an allocation that satisfies guarantees of the form "match at least 80% of applicants to one of their top three choices" or "it is unacceptable to leave more than 10% of applicants unassigned". The well-studied notions of rank-maximality and fairness fail to capture such requirements due to their property of optimizing extreme ends of the signature of a matching. We, therefore, propose a novel optimality criterion, which we call as the "cumulative better signature".We investigate the computational complexity of the new notion of optimality in the setting where posts have associated fixed quotas. We prove that under the fixed quota setting, the problem turns out to be NP-hard under natural restrictions. We provide randomized algorithms in the fixed quota setting when the number of ranks is constant. We also study the problem under a cost-based quota setting and show that min-cost cumulative better matching can be computed efficiently. Apart from circumventing the hardness, the cost-based quota setting is motivated by real-world applications like course allocation or school choice where the capacities or quotas need not be rigid.

关键词： NP-hardness matchings with preferences network flows randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：