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

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

来源：评论

学校读者我要写书评

暂无评论

Learning mixtures of structured distributions over discrete domains

Learning mixtures of structured distributions over discrete ...

引用

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

作者： Chan, Siu-On Diakonikolas, Ilias Servedio, Rocco A. Sun, Xiaorui Univ Calif Berkeley Berkeley CA 94720 USA Univ Edinburgh Edinburgh Midlothian Scotland Columbia Univ New York NY 10027 USA

ISBN: (纸本)9781611973105;9781611972511

Let C be a class of probability distributions over the discrete domain [n] = {1, ..., n}: We show that if C satisfies a rather general condition - essentially, that each distribution in C can be well-approximated by a variable-width histogram with few bins - then there is a highly efficient (both in terms of running time and sample complexity) algorithm that can learn any mixture of k unknown distributions from C. We analyze several natural types of distributions over [n], including log-concave, monotone hazard rate and unimodal distributions, and show that they have the required structural property of being well-approximated by a histogram with few bins. Applying our general algorithm, we obtain near-optimally efficient algorithms for all these mixture learning problems as described below. More precisely, Log-concave distributions: We learn any mixture of k log-concave distributions over [n] using k.(O) over tilde (1/epsilon(4)) samples (independent of n) and running in time (O) over tilde (k log(n)/epsilon(4)) bit-operations (note that reading a single sample from [n] takes theta (log n) bit operations). For the special case k = 1 we give an efficient algorithm using (O) over tilde (1/epsilon(3)) samples;this generalizes the main result of [DDS12b] from the class of Poisson Binomial distributions to the much broader class of all log-concave distributions. Our upper bounds are not far from optimal since any algorithm for this learning problem requires Omega (k/epsilon(5/2)) samples. Monotone hazard rate (MHR) distributions: We learn any mixture of k MHR distributions over [n] using O (k log(n/epsilon)/epsilon(4)) samples and running in time (O) over tilde (k log(2) (n)/epsilon(4)) bit-operations. Any algorithm for this learning problem must use Omega (k log(n)/epsilon(3)) samples. Unimodal distributions: We give an algorithm that learns any mixture of k unimodal distributions over [n] using O (k log(n)/epsilon(4)) samples and running in time (O) over tilde (k log(2

关键词： Mixtures

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the annual acm-siam symposium on discrete algorithms: Preface

Proceedings of the Annual ACM-SIAM Symposium on Discrete Alg...

引用

Proceedings of the annual acm-siam symposium on discrete algorithms 2013年 xiii-xiv页

作者： Khanna, Sanjeev University of Pennsylvania United States

来源：评论

学校读者我要写书评

暂无评论

ASYMMETRIC TRAVELING SALESMAN PAth AND DIRECTED LATENCY PROBLEMS

引用

siam JOURNAL ON COMPUTING 2013年第4期42卷 1596-1619页

作者： Friggstad, Zachary Salavatipour, Mohammad R. Svitkina, Zoya Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Google Inc Mountain View CA USA

We study integrality gaps and approximability of three closely related problems on directed graphs with edge lengths that satisfy the triangle inequality. Given two specified vertices s and t, two of these problems ask to find an s-t path in the graph visiting all other vertices. In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total length of this path. In the directed latency problem, the objective is to minimize the sum of the latencies of the vertices, where the latency of a vertex v is the distance from s to v along the path. the third problem that we study is the k-person ATSPP, in which the goal is to find k paths from s to t, of minimum total length, such that every vertex is on at least one of these paths. All of these problems are NP-hard. the best known approximation algorithms for ATSPP had ratio O(log n) [C. Chekuri and M. Pal, theory Comput., 3 (2007), pp. 197-209], [U. Feige and M. Singh, "Improved approximation ratios for traveling salesperson tours and paths in directed graphs," in Proceedings of the 10th APPROX, 2007, pp. 107-118] until the recent result that improves it to O(log n/log log n) [A. Asadpour et al., "An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem," in Proceedings of the 21st annual acm-siam symposium on discrete algorithms, 2010, pp. 379-389], [U. Feige and M. Singh, "Improved approximation ratios for traveling salesperson tours and paths in directed graphs," in Proceedings of the 10th APPROX, 2007, pp. 107-118]. However, the best known bound on the integrality gap of any linear programming relaxation for ATSPP is only O(root n). For directed latency, the best previously known approximation algorithm has a guarantee of O(n(1/2+epsilon)) for any constant epsilon > 0 [V. Nagarajan and R. Ravi, "the directed minimum latency problem," in Proceedings of the 11th APPROX, 2008, pp. 193-206]. We present a new algorithm for the ATSPP problem that has an app

关键词： approximation algorithms asymmetric traveling salesman path directed latency integrality gap k-person traveling salesmen problem

来源：评论

学校读者我要写书评

暂无评论

Asymmetric traveling salesman path and directed latency problems

Asymmetric traveling salesman path and directed latency prob...

引用

作者： Friggstad, Zachary Salavatipour, Mohammad R. Svitkina, Zoya Department of Combinatorics and Optimization University of Waterloo Waterloo ON N2L 3G1 Canada Department of Computing Science University of Alberta Edmonton AB T6G 2E8 Canada Google Inc. Mountain View CA United States

We study integrality gaps and approximability of three closely related problems on directed graphs with edge lengths that satisfy the triangle inequality. Given two specified vertices s and t, two of these problems ask to find an s-t path in the graph visiting all other vertices. In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total length of this path. In the directed latency problem, the objective is to minimize the sum of the latencies of the vertices, where the latency of a vertex v is the distance from s to v along the path. the third problem that we study is the k-person ATSPP, in which the goal is to find k paths from s to t, of minimum total length, such that every vertex is on at least one of these paths. All of these problems are NP-hard. the best known approximation algorithms for ATSPP had ratio O(logn) [C. Chekuri and M. Pal, theory Comput., 3 (2007), pp. 197-209], [U. Feige and M. Singh, "Improved approximation ratios for traveling salesperson tours and paths in directed graphs," in Proceedings of the 10th APPROX, 2007, pp. 107-118] until the recent result that improves it to O(logn/loglogn) [A. Asadpour et al., "An O(logn/log log n)-approximation algorithm for the asymmetric traveling salesman problem," in Proceedings of the 21st annual acm-siam symposium on discrete algorithms, 2010, pp. 379-389], [U. Feige and M. Singh, "Improved approximation ratios for traveling salesperson tours and paths in directed graphs," in Proceedings of the 10th APPROX, 2007, pp. 107-118]. However, the best known bound on the integrality gap of any linear programming relaxation for ATSPP is only O(√n). For directed latency, the best previously known approximation algorithm has a guarantee of O(n1/2+Ε) for any constant Ε > 0 [V. Nagarajan and R. Ravi, "the directed minimum latency problem," in Proceedings of the 11th APPROX, 2008, pp. 193-206]. We present a new algorithm for the ATSPP problem that has an approximation ratio of O(l

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Analysis of the "hiring above the median" selection strategy for the hiring problem

Analysis of the "hiring above the median" selection strategy...

引用

作者： Helmi, Ahmed Panholzer, Alois Departament de Llenguatges i Sistemes Informàtics Universitat Politècnica de Catalunya Jordi Girona 1-3 08034 Barcelona Spain Institut für Diskrete Mathematik und Geometrie Technische Universität Wien Wiedner Hauptstr. 8-10/104 1040 Wien Austria

this paper gives a precise mathematical analysis of the behaviour of "hiring above the median" strategies for a problem in the context of "on-line selection under uncertainty" that is known (at least in computer science related literature) as the "hiring problem". Here a sequence of candidates is interviewed sequentially and based on the "score" of the current candidate an immediate decision whether to hire him or not has to be made. For "hiring above the median" selection rules, a new candidate will be hired if he has a score better than the median score of the already recruited candidates. Under the natural probabilistic model assuming that the ranks of the first n candidates are forming a random permutation, we show exact and asymptotic results for various quantities of interest to describe the dynamics of the hiring process and the quality of the hired staff. In particular we can characterize the limiting distribution of the number of hired candidates of a sequence of n candidates, which reveals the somewhat surprising effect, that slight changes in the selection rule, i.e., assuming the "lower" or the "upper" median as the threshold, have a strong influence on the asymptotic behaviour. thus we could extend considerably previous analyses (Krieger et al., Ann. Appl. Probab., 17:360-385, 2007;Broder et al., Proceedings of the 19th annual acm-siam symposium on discrete algorithms (SODA), pp. 1184-1193, acm/siam, New York/Philadelphia, 2008 and Archibald and Martinez, Proceedings of the 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), discrete Mathematics and theoretical Computer Science, pp. 63-76, 2009) of such selection rules. Furthermore, we discuss connections between the hiring process and the Chinese restaurant process introduced by Pitman (Combinatorial Stochastic Processes, Springer, Berlin, 2006). © 2012 Springer Science+Business Media New York.

关键词： Random processes

来源：评论

学校读者我要写书评

暂无评论

Learning mixtures of structured distributions over discrete domains 13

Learning mixtures of structured distributions over discrete ...

引用

annual Association for Computing Machinery-Society for Industrial and Applied Mathmatics symposium on discrete algorithms

作者： Siu-On Chan Ilias Diakonikolasy Rocco A. Servedioz Xiaorui Sunx UC Berkeley University of Edinburgh Columbia University

ISBN: (纸本)9781611972511

Let C be a class of probability distributions over the discrete domain [n] = {1,..., n}. We show that if e satisfies a rather general condition essentially, that each distribution in e can be well-approximated by a variable-width histogram with few bins then there is a highly efficient (both in terms of running time and sample complexity) algorithm that can learn any mixture of k unknown distributions from e. We analyze several natural types of distributions over [n], including log-concave, monotone hazard rate and unimodal distributions, and show that they have the required structural property of being well-approximated by a histogram with few bins. Applying our general algorithm, we obtain near-optimally efficient algorithms for all these mixture learning problems as described below.

关键词： Learning mixtures structured distributions discrete domains Probability distribution Learning Problems Running in mixtures Unimodal histograms algorithms Running

来源：评论

学校读者我要写书评

暂无评论

Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More 13

Graph Products Revisited: Tight Approximation Hardness of In...

引用

annual acm-Society for Industrial and Applied Mathmatics symposium on discrete algorithms

作者： Parinya Chalermsook Bundit Laekhanukit Danupon Nanongkai IDSIA School of Computer Science McGill University Theory and Applications of Algorithms Research Group University of Vienna

ISBN: (纸本)9781611972511

Graph product is a fundamental tool with rich applications in both graph theory and theoretical computer science. It is usually studied in the form f(G * H) where G and H are graphs, * is a graph product and f is a graph property. For example, if f is the independence number and * is the disjunctive product, then the product is known to be multiplicative: f(G * H) = f(G)f(H). In this paper, we study graph products in the following non-standard form: f((G{direct +} H)*J) where G, H and J are graphs, and * are two different graph products and f is a graph property. We show that if f is the induced and semi-induced matching number, then for some products {direct +} and *, it is subadditive in the sense that f((G{direct +} H) * J) ≤ f(G* J)+f(H * J). Moreover, when f is the poset dimension number, it is almost subadditive.

关键词： Graph Products Approximation Hardness Poset Dimension subadditive Line graph Poset Fluorine (F) iodine dimensions theoretical computer science discrete mathematics approximation

来源：评论

学校读者我要写书评

暂无评论

the Traveling Salesman Problem for Lines, Balls and Planes 13

The Traveling Salesman Problem for Lines, Balls and Planes

引用

symposium on discrete algorithms

作者： Adrian Dumitrescu Csaba D. Tóth Department of Computer Science University of Wisconsin-Milwaukee USA. Department of Mathematics and Statistics University of Calgary Canada

ISBN: (纸本)9781627484855

We revisit the traveling salesman problem with neighborhoods (TSPN) and obtain several approximation algorithms. these constitute either improvements over previously best approximations achievable in comparable times (for unit disks in the plane), or first approximations ever (for planes, lines and unit balls in 3-space). (I) Given a set of n planes in 3-space, a TSP tour that is at most 2.31times longer than the optimal can be computed in O(n) time. (II) Given a set of n lines in 3-space, a TSP tour that is at most O(log~3 n) times longer than the optimal can be computed in polynomial time. (III) Given a set of n unit disks in the plane (resp., unit balls in 3-space), we improve the approximation ratio using a black box that computes an approximate tour for a set of points (the centers of a subset of the disks or the balls).

关键词： Traveling Salesman Balls and Planes disks or the balls plane travelling salesman problems Ball Device Component Travelling salesman disks cultivators Approximation algorithms lines lines Platanus hybrida

来源：评论

学校读者我要写书评

暂无评论

Computing the discrete Fréchet Distance in Subquadratic Time 13

Computing the Discrete Fréchet Distance in Subquadratic Tim...

引用

symposium on discrete algorithms

作者： Pankaj K. Agarwal Rinat Ben Avraham Haim Kaplan Micha Sharir Department of Computer Science Box 90129 Duke University Durham NC 27708-0129 USA School of Computer Science Tel Aviv University Tel Aviv 69978 Israel

ISBN: (纸本)9781627484855

the Fréchet distance is a similarity measure between two curves A and B that takes into account the location and ordering of the points along the two curves: Informally, it is the minimum length of a leash required to connect a dog, walking along A, and its owner, walking along B, as they walk without backtracking along their respective curves from one endpoint to the other. the discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on n and m specific stones on the curves A and B, respectively. these frogs hop from one stone to the next without backtracking, and the discrete Fréchet distance is the minimum length of a "leash" that connects the frogs and allows them to execute such a sequence of hops. It can be computed in quadratic time by a straightforward dynamic programming algorithm. We present the first subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane. Assuming m ≤ n, the algorithm runs in O (mn log log n/log n) time, in the standard RAM model, using O(n) storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automaton.

关键词： discrete Fréchet Subquadratic Time algorithm runs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：