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

Near Optimal Online algorithms and Fast approximation algorithms for Resource Allocation Problems

JOURNAL OF THE ACM 2019年第1期66卷 1-41页

作者： Devanur, Nikhil R. Jain, Kamal Sivan, Balasubramanian Wilkens, Christopher A. Microsoft Res 1 Microsoft Way Redmond WA 98052 USA Faira 608 State St S Kirkland WA 98033 USA Google Res 111 8th Ave New York NY 10011 USA Facebook Res 1 Hacker Way Menlo Pk CA 94025 USA

We present prior robust algorithms for a large class of resource allocation problems where requests arrive one-by-one (online), drawn independently from an unknown distribution at every step. We design a single algorithm that, for every possible underlying distribution, obtains a 1 - epsilon fraction of the profit obtained by an algorithm that knows the entire request sequence ahead of time. The factor epsilon approaches 0 when no single request consumes/contributes a significant fraction of the global consumption/contribution by all requests together. We show that the tradeoff we obtain here that determines how fast epsilon approaches 0, is near optimal: We give a nearly matching lower bound showing that the tradeoff cannot be improved much beyond what we obtain. Going beyond the model of a static underlying distribution, we introduce the adversarial stochastic input model, where an adversary, possibly in an adaptive manner, controls the distributions from which the requests are drawn at each step. Placing no restriction on the adversary, we design an algorithm that obtains a 1 - epsilon fraction of the optimal profit obtainable w.r.t. the worst distribution in the adversarial sequence. Further, if the algorithm is given one number per distribution, namely the optimal profit possible for each of the adversary's distribution, then we design an algorithm that achieves a 1 - epsilon fraction of the weighted average of the optimal profit of each distribution the adversary picks. In the offline setting we give a fast algorithm to solve very large linear programs (LPs) with both packing and covering constraints. We give algorithms to approximately solve (within a factor of 1 + epsilon) the mixed packing-covering problem with O(gamma m log(n/delta)/epsilon(2)) oracle calls where the constraint matrix of this LP has dimen- sion n x m, the success probability of the algorithm is 1 - delta, and gamma quantifies how significant a single request is when compared to the sum tot

关键词： Online algorithms unknown distribution approximation algorithms greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Scalability of Betweenness approximation algorithms: An Experimental Review

引用

IEEE ACCESS 2019年 7卷 104057-104071页

作者： Wandelt, Sebastian Shi, Xing Sun, Xiaoqian Beihang Univ Sch Elect & Informat Engn Beijing 100191 Peoples R China

Betweenness centrality, which measures the contribution of an individual node to the network's connectivity by counting the number of shortest paths a node appears in, is widely used for the analysis of the complex networks. The computation of exact betweenness centrality is prohibitively expensive for large networks, given a worst-case complexity of O(N * E), where N is the number of nodes and E is the number of edges in the network. Accordingly, a multitude of approximation algorithms has been proposed in the literature. Obtaining an overview of the state of the art is difficult, given a combination of numerous algorithms, parameters, and network topologies. In this paper, we report on the results of the probably largest benchmark performed in this field. Specifically, we select 100 networks with distinct topologies and scales, covering various domains. We devise and compare eight selected measures to evaluate the accuracy of the approximation, compared with the exact betweenness computation. All experiments, including those to obtain the exact betweenness values, have been performed on one computer using a single thread, in order to provide a fair comparison. We implemented typical approximation methods and report sensitivity analysis results with a variety of parameters. We find that a uniformly random sampling method, one of the earliest proposed methods in this field, still delivers the best performance, nicely addressing a sweet spot between quality and runtime complexity. In addition, we carried out robustness experiments based on the ranking order of approximated betweenness, in order to show the effect of different approximations on a real-world task. Our study aims at being a reference for choosing a betweenness approximation method, with consideration of network type, the required level of accuracy, and available computational resources.

关键词： Complex networks network topology approximation algorithms experimental review betweenness centrality

来源：评论

学校读者我要写书评

暂无评论

The ordered k-median problem: surrogate models and approximation algorithms

引用

MATHEMATICAL PROGRAMMING 2019年第1-2期177卷 55-83页

作者： Aouad, Ali Segev, Danny London Business Sch London NW1 4SA England Univ Haifa Dept Stat IL-31905 Haifa Israel

In the last two decades, a steady stream of research has been devoted to studying various computational aspects of the ordered k-median problem, which subsumes traditional facility location problems (such as median, center, p-centrum, etc.) through a unified modeling approach. Given a finite metric space, the objective is to locate k facilities in order to minimize the ordered median cost function. In its general form, this function penalizes the coverage distance of each vertex by a multiplicative weight, depending on its ranking (or percentile) in the ordered list of all coverage distances. While antecedent literature has focused on mathematical properties of ordered median functions, integer programming methods, various heuristics, and special cases, this problem was not studied thus far through the lens of approximation algorithms. In particular, even on simple network topologies, such as trees or line graphs, obtaining non-trivial approximation guarantees is an open question. The main contribution of this paper is to devise the first provably-good approximation algorithms for the ordered k-median problem. We develop a novel approach that relies primarily on a surrogate model, where the ordered median function is replaced by a simplified ranking-invariant functional form, via efficient enumeration. Surprisingly, while this surrogate model is Omega(n Omega(1))-hard to approximate on general metrics, we obtain an O(logn)-approximation for our original problem by employing local search methods on a smooth variant of the surrogate function. In addition, an improved guarantee of 2+E is obtained on tree metrics by optimally solving the surrogate model through dynamic programming. Finally, we show that the latter optimality gap is tight up to an O(E) term.

关键词： Location theory approximation algorithms Surrogate model Local search

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for minimum power covering problems

引用

THEORETICAL COMPUTER SCIENCE 2019年 795卷 285-300页

作者： Calinescu, Gruia Kortsarz, Guy Nutov, Zeev IIT Chicago IL 60616 USA Rutgers State Univ Camden NJ USA Open Univ Israel Raanana Israel

Given an undirected graph with edge costs, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider two network design problems under the power minimization criteria. In both problems we are given a graph G = (V, E) with edge costs and a set T subset of V of terminals. The goal is to find a minimum power edge subset F subset of E such that the graph H = (V, F) satisfies some prescribed requirements. In the MIN-POWER EDGE-COVER problem, H should contain an edge incident to every terminal. Using the Iterative Randomized Rounding (IRR) method, we give an algorithm with expected approximation ratio 1.41;the ratio is reduced to 73/60 < 1.217 when T is an independent set in G. In the case of unit costs we also achieve ratio 73/60, and in addition give a simple efficient combinatorial algorithm with ratio 5/4. For all these NP-hard problems the previous best known ratio was 3/2. In the related MIN-POWER TERMINAL BACKUP problem, H should contain a path from every t is an element of T to some node in T \ {t}. We obtain ratio 3/2 for this NP-hard problem, improving the trivial ratio of 2. (C) 2019 Elsevier B.V. All rights reserved.

关键词： approximation algorithms Iterative randomized rounding Minimum power Edge-cover Terminal backup

来源：评论

学校读者我要写书评

暂无评论

General multilevel adaptations for stochastic approximation algorithms of Robbins-Monro and Polyak-Ruppert type

引用

NUMERISCHE MATHEMATIK 2019年第2期142卷 279-328页

作者： Dereich, Steffen Mueller-Gronbach, Thomas Westfalische Wilhelms Univ Munster Inst Math Stat Fachbereich Math & Informat 10 Orleans Ring 10 D-48149 Munster Germany Univ Passau Fak Informat & Math Innstr 33 D-94032 Passau Germany

In this article we present and analyse new multilevel adaptations of classical stochastic approximation algorithms for the computation of a zero of a function f:DRd defined on a convex domain D< subset of>Rd, which is given as a parameterised family of expectations. The analysis of the error and the computational cost of our method is based on similar assumptions as used in Giles (Oper Res 56(3):607-617, 2008) for the computation of a single expectation. Additionally, we essentially only require that f satisfies a classical contraction property from stochastic approximation theory. Under these assumptions we establish error bounds in pth mean for our multilevel Robbins-Monro and Polyak-Ruppert schemes that decay in the computational time as fast as the classical error bounds for multilevel Monte Carlo approximations of single expectations known from Giles (Oper Res 56(3):607-617, 2008). Our approach is universal in the sense that having multilevel implementations for a particular application at hand it is straightforward to implement the corresponding stochastic approximation algorithm.

关键词： computational time approximation Theory approximation algorithms stochastic approximation multilayers

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Connected Graph Factors of Minimum Weight

引用

THEORY OF COMPUTING SYSTEMS 2018年第2期62卷 441-464页

作者： Cornelissen, Kamiel Hoeksma, Ruben Manthey, Bodo Narayanaswamy, N. S. Rahul, C. S. Waanders, Marten Univ Twente Enschede Netherlands Univ Chile Santiago Chile Indian Inst Technol Madras Chennai Tamil Nadu India

Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning subgraphs (or d-factors) of minimum weight with connectivity requirements. For the case of k-edge-connectedness, we present approximation algorithms that achieve constant approximation ratios for all . For the case of k-vertex-connectedness, we achieve constant approximation ratios for dae -1. Our algorithms also work for arbitrary degree sequences if the minimum degree is at least (for k-edge-connectivity) or 2k-1 (for k-vertex-connectivity). To complement our approximation algorithms, we prove that the problem with simple connectivity cannot be approximated better than the traveling salesman problem. In particular, the problem is APX-hard.

关键词： Graph factors Edge-connectivity Vertex-connectivity approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for a Class of Stochastic Selection Problems with Reward and Cost Considerations

引用

OPERATIONS RESEARCH 2018年第3期66卷 834-848页

作者： Strinka, Zohar M. A. Romeijn, H. Edwin Mashey Denver CO 80202 USA Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA

We study a class of problems with both binary selection decisions and associated continuous choices that result in stochastic rewards and costs. The rewards are received based on the decision maker's selection, and the costs depend both on the decisions and realizations of the stochastic variables. We consider a family of risk-based objective functions that contains the traditional risk-neutral expected-value objective as a special case. A combination of rounding and sample average approximation is used to produce solutions that are guaranteed to be close to the optimal solution with high probability. We also provide an empirical comparison of the performance of the algorithms on a set of randomly generated instances of a supply cham example problem. The computational results illustrate the theoretical claims in the paper that, for this problem, high-quality solutions can be found with small computational effort.

关键词： two-stage stochastic optimization selection resource allocation approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Three Dimensional Protein Folding

引用

FUNDAMENTA INFORMATICAE 2018年第4期163卷 375-393页

作者： Shaw, Dipan Lal Islam, A. S. M. Shohidull Karmaker, Shuvasish Rahman, M. Sohel Univ Calif Riverside Dept CSE Riverside CA 92521 USA McMaster Univ Dept Computat Engn & Sci Hamilton ON Canada BUET Dept CSE Dhaka 1205 Bangladesh BUET Dept CSE AlEDA Grp ECE Bldg Dhaka 1205 Bangladesh

Predicting the secondary structure of a protein using a lattice model is one of the most studied computational problems in bioinformatics. Here the secondary structure or three dimensional structure of a protein is predicted from its amino acid sequence. The secondary structure refers to the local sub-structures of a protein. Simplified energy models have been proposed in the literature on the basis of interaction of amino acid residues in proteins. We focus on a well researched model known as the Hydrophobic-Polar (HP) energy model. In this paper, we propose the hexagonal prism lattice with diagonals that can overcome the problems of other lattice structures, e.g., parity problem. We give two approximation algorithms for protein folding on this lattice using HP model. Our first algorithm leads us to a similar structure of helix structure that is commonly found in a protein structure. This motivates us to propose the next algorithm with a better approximation ratio. Finally, we analyze the algorithms on the basis of intensity of the chemical forces along the different types of edges of hexagonal prism lattice with diagonals.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Minimum-Load k-Facility Location

引用

ACM TRANSACTIONS ON algorithms 2018年第2期14卷 1–29页

作者： Ahmadian, Sara Behsaz, Babak Friggstad, Zachary Jorati, Amin Salavatipour, Mohammad R. Swamy, Chaitanya Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimnm-load klacility location (MLkFL) problem, Which is defined as follows. We have a set F of facilities, a set C of clients, and an integer k >= 0. Assigning client j to a facility f incurs a connection cost d(f, j). The goal is to open a set F subset of F of k facilities and assign each client j to a-facility f (j) is an element of F so as to minimize max(f is an element of F) Sigma(j is an element of C:f(j)=f) d(f, j);we call Sigma(j is an element of C:f(j)=f) d(f, j) the load of facility f. This problem was studied under the name of min-max star cover in References [3, 7], who (among other results) gave bicriteria approximation algorithms for MLkFL for when F = C. MLkFL is rather poorly understood, a rid only an O(k)-approximation is currently known for MLkFL, even for line metrics. Our main result is the first polytime approximation scheme (PTAS) for MLkFL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that MLkFL is strongly NP-hard on line metrics. We also devise a quasi-PTAS for MLkFL on tree metrics. MLkFL turns out to be surprisingly challenging even on line metrics and resilient to attack by a variety of techniques that have been successfully applied to facility-location problems. For instance, we show that (a) even a configuration-style LP-relaxation has a bad integrality gap and (b) a multi-swap k-median style local search heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack MLkFL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near optimal solution possessing sonic nice structural properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP) encoding of the problem and

关键词： approximation algorithms min-max star cover polynomial time approximation scheme minimum load k-facility location lower bound

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the Max-Buying Problem with Limited Supply

引用

ALGORITHMICA 2018年第11期80卷 2973-2992页

作者： Fernandes, Cristina G. Schouery, Rafael C. S. Univ Sao Paulo Inst Matemat & Estat Rua Matao1010Cidade Univ BR-05508090 Sao Paulo SP Brazil Univ Estadual Campinas Inst Comp Av Albert Einstein1251Cidade Univ BR-13083852 Campinas SP Brazil

We consider the Max-Buying Problem with Limited Supply, in which there are n items, with copies of each item i, and m consumers such that each consumer b has a valuation for item i. The goal is to find a pricing p and an allocation of items to consumers that maximize the revenue, with every item allocated to at most consumers, every consumer receives at most one item, and if a consumer b receives item i, then . We present a randomized -approximation for the Max-Buying Problem with Limited Supply and show how to derandomize it, improving the previously known upper bound of 2. The algorithm uses an integer programming formulation with an exponential number of variables to do a probabilistic rounding and it explores some structure of the problem that might be useful when developing approximations for other pricing problems. We also present a PTAS for the price ladder variant, in which the pricing must be non-increasing (that is, ), improving the previously known upper bound of 4.

关键词： Pricing Economics approximation algorithms Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：