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

21st annual acm/siam symposium on discrete algorithms

作者： Friggstad, Zachary Salavatipour, Mohammad R. Svitkina, Zoya Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

ISBN: (纸本)9780898717013

We study integrality gaps and approximability of two closely related problems on directed graphs. Given a set V of n nodes in an underlying asymmetric metric and two specified nodes s and t, both problems ask to find an s-t path visiting all other nodes In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total cost of this path. In the directed latency problem, the objective is to minimize the sum of distances on this path from s to each node. Both of these problems are NP-hard the best known approximation algorithms for ATSPP had ratio O(log n) [7,9] until the very recent result that improves it to O(log n/ log log n) [3,9]. However, only a bound of O(root n) for the integrality gap of its lineal programming relaxation has been known. For directed latency, the best previously known approximation algorithm has a guarantee of O(n(1/2+epsilon)), for any constant epsilon > 0 [23] We present a new algorithm for the ATSPP problem that has approximation ratio of O(log n), but whose analysis also bounds the integrality gap of the standard LP relaxation of ATSPP by the same factor. this solves an open problem posed in [7]. We then pursue a deeper study of this LP and its variations and their use in approximating directed latency. Our second major result is an O(log n)approximation to the directed latency problem this also places an O(log n) bound on the integrality gap of a new LP relaxation of the latency problem that we introduce

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Cake Cutting on Graphs: A discrete and Bounded Proportional Protocol 31

Cake Cutting on Graphs: A Discrete and Bounded Proportional ...

引用

31st annual acm-siam symposium on discrete algorithms (SODA)

作者： Bei, Xiaohui Sun, Xiaoming Wu, Hao Zhang, Jialin Zhang, Zhijie Zi, Wei Nanyang Technol Univ Sch Phys & Math Sci Singapore Singapore Chinese Acad Sci Univ Chinese Acad Sci Inst Comp Technol CAS Key Lab Network Data Sci & Technol Beijing Peoples R China Univ Chinese Acad Sci Beijing Peoples R China

ISBN: (纸本)9781611975994

the classical cake cutting problem studies how to find fair allocations of a heterogeneous and divisible resource among multiple agents. Two of the most commonly studied fairness concepts in cake cutting are proportionality and envy-freeness. It is well known that a proportional allocation among n agents can be found efficiently via simple protocols [16]. For envy-freeness, in a recent breakthrough, Aziz and Mackenzie [5] proposed a discrete and bounded envy-free protocol for any number of players. However, the protocol suffers from high multiple-exponential query complexity and it remains open to find simpler and more efficient envy-free protocols. In this paper we consider a variation of the cake cutting problem by assuming an underlying graph over the agents whose edges describe their acquaintance relationships, and agents evaluate their shares relatively to those of their neighbors. An allocation is called locally proportional if each agent thinks she receives at least the average value over her neighbors. Local proportionality generalizes proportionality and is in an interesting middle ground between proportionality and envy-freeness: its existence is guaranteed by that of an envy-free allocation, but no simple protocol is known to produce such a locally proportional allocation for general graphs. Previous works showed locally proportional protocols for special classes of graphs, and it is listed in both [1] and [8] as an open question to design simple locally proportional protocols for more general classes of graphs. In this paper we completely resolved this open question by presenting a discrete and bounded locally proportional protocol for any given graph. Our protocol has a query complexity of only single exponential, which is significantly smaller than the six towers of n query complexity of the envy-free protocol given in [5].

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Combination Can Be Hard: Approximability of the Unique Coverage Problem

Combination Can Be Hard: Approximability of the Unique Cover...

引用

17th acm-siam symposium on discrete algorithms

作者： Demaine, Erik D. Feige, Uriel Hajiaghayi, MohammadTaghi Salavatipour, Mohammad R. MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

ISBN: (纸本)9780898716054

We prove semi-logarithmic inapproximability for a maximization problem called unique coverage: given a collection of sets, find a subcollection that maximizes the number of elements covered exactly once. Specifically, we prove O(1/log(sigma/(epsilon)) n) inapproximability assuming that NP not subset of BPTIME(2(n epsilon)) for some epsilon > 0. We also prove O(1/log(1/3-epsilon) n) inapproximability, for any epsilon > 0, assuming that refuting random instances of 3SAT is hard on average;and prove 0(1/log n) inapproximability under a plausible hypothesis concerning the hardness of another problem, balanced bipartite independent set. We establish matching upper bounds up to exponents, even for a more general (budgeted) setting, giving an Omega(1/log n)-approximation algorithm as well as an Omega(1/log B)-approximation algorithm when every set has at most B elements. We also show that our inapproximability results extend to envy-free pricing, an important problem in computational economics. We describe how the (budgeted) unique coverage problem, motivated by real-world applications, has close connections to other theoretical problems including max cut, maximum coverage, and radio broadcasting.

关键词： Problem solving

来源：评论

学校读者我要写书评

暂无评论

discrete Choice, Permutations, and Reconstruction 29

Discrete Choice, Permutations, and Reconstruction

引用

29th annual acm-siam symposium on discrete algorithms (SODA)

作者： Chierichetti, Flavio Kumar, Ravi Tomkins, Andrew Sapienza Univ Rome Rome Italy Google Mountain View CA USA

ISBN: (纸本)9781611975031

In this paper we study the well-known family of Random Utility Models, developed over 50 years ago to codify rational user behavior in choosing one item from a finite set of options. In this setting each user draws i.i.d. from some distribution a utility function mapping each item in the universe to a real-valued utility. the user is then offered a subset of the items, and selects the one of maximum utility. A MAX-DIST oracle for this choice model takes any subset of items and returns the probability (over the distribution of utility functions) that each will be selected. A discrete choice algorithm, given access to a MAX-DIST oracle, must return a function that approximates the oracle. We show three primary results. First, we show that any algorithm exactly reproducing the oracle must make exponentially many queries. Second, we show an equivalent representation of the distribution over utility functions, based on permutations, and show that if this distribution has support size k, then it is possible to approximate the oracle using O(nk) queries. Finally, we consider settings in which the subset of items is always small. We give an algorithm that makes less than n((1 - epsilon/2)K) queries, each to sets of size at most (1 - epsilon/2) K, in order to approximate the MAX-DIST oracle on every set of size vertical bar T vertical bar <= K with statistical error at most epsilon. In contrast, we show that any algorithm that queries for subsets of size 2(O)(root log n) must make maximal statistical error on some large sets.

关键词： Set theory

来源：评论

学校读者我要写书评

暂无评论

On the diameter of the symmetric group: Polynomial bounds

On the diameter of the symmetric group: Polynomial bounds

引用

Proceedings of the Fifteenth annual acm-siam symposium on discrete algorithms

作者： Babai, László Beals, Robert Seress, Ákos Department of Computer Science University of Chicago 1100 East 58th Street Chicago IL 60637 Mathematical Institute Hungarian Academy of Science IDA Ctr. Commun. Res. - Princeton 805 Bunn Drive Princeton NJ 08540 Department of Mathematics Ohio State University 231 W. 18th Avenue Columbus OH 43210

We address the long-standing conjecture that all permutations have polynomially bounded word length in terms of any set of generators of the symmetric group. the best available bound on the maximum required word length is exponential in √n log n. Polynomial bounds on the word length have previously been established for very special classes of generating sets only. In this paper we give a polynomial bound on the word length under the sole condition that one of the generators fix at least 67% of the domain. Words of the length claimed can be found in Las Vegas polynomial time. the proof involves a Markov chain mixing estimate which permits us, apparently for the first time, to break the "element order bottleneck." As a corollary, we obtain the following average-case result: for a 1 - δ fraction of the pairs of generators for the symmetric group, the word length is polynomially bounded. It is known that for almost all pairs of generators, the word length is less than exp(√n ln n(1 + o(1))).

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Fast and Accurate Approximations of the Optimal Transport in Semi-discrete and discrete Settings 35

Fast and Accurate Approximations of the Optimal Transport in...

引用

35th annual acm-siam symposium on discrete algorithms (SODA)

作者： Agarwal, Pankaj K. Raghvendra, Sharath Shirzadian, Pouyan Yao, Keegan Duke Univ Dept Comp Sci Durham NC 27706 USA North Carolina State Univ Dept Comp Sci Raleigh NC 27695 USA Virginia Tech Dept Comp Sci Blacksburg VA USA

ISBN: (纸本)9781611977912

Given a d-dimensional continuous (resp. discrete) probability distribution mu and a discrete distribution nu, the semi-discrete (resp. discrete) optimal transport (OT) problem asks for computing a minimum-cost plan to transport mass from mu to nu;we assume n to be the number of points in the support of the discrete distributions. In this paper, we present three approximation algorithms for the OT problem with strong provable guarantees. (i) Additive approximation for semi-discrete OT: For any parameter epsilon > 0, we present an algorithm that computes a semi-discrete transport plan (tau) over tilde with cost cent((tau) over tilde) <= cent(tau*) + epsilon in n(O(d)) log D/epsilon time;here, tau* is the optimal transport plan, D is the diameter of the supports of mu and nu, and we assume we have access to an oracle that outputs the mass of mu inside a constant-complexity region in O(1) time. Our algorithm works for several ground distances including the L-p-norm and the squared-Euclidean distance. (ii) Relative approximation for semi-discrete OT: For any parameter epsilon > 0, we present an algorithm that computes a semi-discrete transport plan (tau) over tilde with cost cent((tau) over tilde) <= (1 + epsilon)cent(tau*) in n log(n) . (epsilon(-1) log log n)(O(d)) expected time;here, tau* is the optimal transport plan, and we assume we have access to an oracle that outputs the mass of mu inside an orthogonal box in O(1) time, and the ground distance is any L-p norm. (iii) Relative approximation for discrete OT: For any parameter epsilon > 0, we present a Monte-Carlo algorithm that computes a transport plan (tau) over tilde with an expected cost cent((tau) over tilde) <= (1 + epsilon)cent(tau*) under any L-p norm in n log(n) . (epsilon(-1) log log n)(O(d)) time;here, tau* is an optimal transport plan and we assume that the spread of the supports of mu and nu is polynomially bounded.

关键词：

来源：评论

学校读者我要写书评

暂无评论

(1+ε\)-Approximation for Facility Location in Data Streams

(1+ε\)-Approximation for Facility Location in Data Streams

引用

24th annual acm-siam symposium on discrete algorithms (SODA)

作者： Czumaj, Artur Lammersen, Christiane Monemizadeh, Morteza Sohler, Christian Univ Warwick Dept Comp Sci Coventry W Midlands England Univ Warwick Ctr Discrete Math & Its Applicat DIMAP Coventry W Midlands England Simon Fraser Univ Sch Comp Sci Burnaby BC Canada Goethe Univ Frankfurt Inst Comp Sci Frankfurt Germany Tech Univ Dortmund Dept Comp Sci Dortmund Germany

ISBN: (纸本)9781611973105;9781611972511

We consider the Euclidean facility location problem with uniform opening cost. In this problem, we are given a set of n points P subset of R-2 and an opening cost f is an element of R+, and we want to find a set of facilities F subset of R-2 that minimizes *** bar F vertical bar + Sigma(p is an element of P) (q is an element of F) min d(p,q), where d(p;q) is the Euclidean distance between p and q. We obtain two main results: A (1 + epsilon) -approximation algorithm with running time O(n log n(log n log log n + (log log n)(8) 2(O(log(1/epsilon)/epsilon)))), which is O(n log(2) n log log n) for any constant epsilon. the first (1 + epsilon)-approximation algorithm for the cost of the facility location problem for dynamic geometric data streams, i. e., when the stream consists of insert and delete operations of points from a discrete space (1, ..., Delta(2)}. the streaming algorithm uses (log Delta/epsilon)(O(1)) space. Our PTAS is significantly faster than any previously known (1 + epsilon)-approximation algorithm for the problem, and is also relatively simple. Our algorithm for dynamic geometric data streams is the first (1 + epsilon)-approximation algorithm for the cost of the facility location problem with polylogarithmic space, and it resolves an open problem in the streaming area. Both algorithms are based on a novel and simple decomposition of an input point set P into small subsets P-i, such that: the cost of solving the facility location problem for each P-i is small (which means that for each P-i one needs to open only a small, polylogarithmic number of facilities), Sigma(i) OPT (P-i) <= (1 + epsilon) . OPT (P), where for a point set P, OPT (P) denotes the cost of an optimal solution for P. the decomposition can be used directly to obtain the PTAS by splitting the point set in the subsets and efficiently solve the problem for each subset independently. By combining our partitioning with techniques to process dynamic data streams of sampling from the cel

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Asynchronous Byzantine Agreement and Leader Election with Full Information

Fast Asynchronous Byzantine Agreement and Leader Election wi...

引用

19th annual acm-siam symposium on discrete algorithms (SODA)

作者： Kapron, Bruce M. Kempe, David King, Valerie Saia, Jared Sanwalani, Vishal Univ Victoria Dept Comp Sci Victoria BC V8W 2Y2 Canada Univ So Calif Dept Comp Sci Los Angeles CA 90089 USA Univ Victoria Dept Comp Sci Victoria BC V8W 3P6 Canada Univ New Mexico Dept Comp Sci Albuquerque NM 87131 USA

We resolve two long-standing open problems in distributed computation by describing polylogarithmic protocols for Byzantine agreement and leader election in the asynchronous full information model with a nonadaptive malicious adversary. All past protocols for asynchronous Byzantine agreement had been exponential, and no protocol for asynchronous leader election had been known. Our protocols tolerate up to (1/3 - epsilon) . n faulty processors, for any positive constant E. they are Monte Carlo, succeeding with probability 1 - o(1) for Byzantine agreement, and constant probability for leader election. A key technical contribution of our article is a new approach for emulating Feige's lightest bin protocol, even with adversarial message scheduling.

关键词： Byzantine agreement distributed algorithms asynchronous communication probabilistic method Monte Carlo algorithms

来源：评论

学校读者我要写书评

暂无评论

Considering Suppressed Packets Improves Buffer Management in QoS Switches 18

Considering Suppressed Packets Improves Buffer Management in...

引用

18th acm-siam symposium on discrete algorithms

作者： Englert, Matthias Westermann, Matthias Rhein Westfal TH Aachen Dept Comp Sci Aachen Germany

ISBN: (纸本)9780898716245

the following buffer management problem arises in network switches providing differentiated services: At the beginning of each time step, one packet can be sent, and afterwards an arbitrary number of new packets arrive. Packets that are not sent can be stored in a buffer. Each packet is attributed by a deadline, and a packet is automatically deleted from the buffer if it is still stored in the buffer by the end of its deadline. the differentiated service model is abstracted by attributing each packet with a value according to its service level. A buffer management strategy determines the packet to be sent in each time step. the goal of a buffer management strategy is to maximize the sum of the values of sent packets. We introduce the concept of suppressed packets and present a deterministic strategy that is based on this concept. We show that this strategy achieves a competitive ratio of 2 root 2 - 1 approximate to 1.828, which is the best known competitive ratio in the deterministic case. Further, we present a memoryless version of this strategy that achieves a competitive ratio of approximate to 1.893. this is the first memoryless strategy that achieves a competitive ratio less than 2, and the competitive ratio of this strategy is even better than the ratios of all previously known deterministic strategies. this demonstrates the potential of the concept of suppressed packets. In addition, we present a simple strategy that achieves the optimal competitive ratio of min{(1 + alpha)/alpha, 2 alpha/(alpha +1)} <= root 2, if only two packet values 1 and alpha > 1 are possible.

关键词： Quality of service

来源：评论

学校读者我要写书评

暂无评论

Randomizing functions: Simulation of a discrete probability distribution using a source of unknown distribution

引用

IEEE TRANSACTIONS ON INFORMATION thEORY 2006年第11期52卷 4965-4976页

作者： Pae, Sung-il Loui, Michael C. Univ Illinois Dept Comp Sci Urbana IL 61801 USA Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA

In this paper, we characterize functions that simulate independent unbiased coin flips from independent coin flips of unknown bias. We call such functions randomizing. Our characterization of randomizing functions enables us to identify the functions that generate the largest average number of fair coin flips from a fixed number of biased coin flips. We show that these optimal functions are efficiently computable. then we generalize the characterization, and we present a method to simulate an arbitrary rational probability distribution optimally (in terms of the average number of output digits) and efficiently (in terms of computational complexity) from outputs of many-faced dice of unknown distribution. We also study randomizing functions on exhaustive prefix-free sets.

关键词： coin flipping random number generation randomizing function universal coding

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：