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

21st annual acm/siam symposium on discrete algorithms

作者： Bernath, Attila Grappe, Roland Szigeti, Zoltan Eotvos Lorand Univ Dept Operat Res Egervary Res Grp MTA ELTE Pazmeny Peter Setany 1-C H-1117 Budapest Hungary Univ Paris 13 Sorbonne Paris Cite LIPN CNRS UMR 7030 F-93430 Villetaneuse France UJF Grenoble INP CNRS Lab G SCOP F-38000 Grenoble France

ISBN: (纸本)9780898717013

Given a symmetric crossing super modular set function p on V and a partition P of V, we solve the problem of finding a graph with ground set V having edges only between the classes of P such that for every subset X of V the cut of the graph defined by X contains at least p(X) edges. the objective is to minimize the number of edges of the graph this problem is a common generalization of the global edge-connectivity augmentation of a graph with partition constraints, which was solved by Bang-Jensen, Gabow, Jordan and Szigeti [1] and the problem of covering a. symmetric crossing supermodular set function solved by Benezur and Frank [3] Our problem can be considered as an abstract form of the problem of global edge-connectivity augmentation of a hypergraph by a multipartite graph;which was earlier solved by the authors [5]

关键词： Set theory

来源：评论

学校读者我要写书评

暂无评论

Distributed SINR based Scheduling Algorithm for Multi-hop Wireless Networks

Distributed SINR based Scheduling Algorithm for Multi-hop Wi...

引用

13th acm International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems

作者： Ryu, Jiho Joo, Changhee Kwon, Ted 'Taekyoung' Shroff, Ness B. Choi, Yanghee Seoul Natl Univ Sch Comp Sci & Engn Seoul 151 South Korea

ISBN: (纸本)9781450302746

the problem of developing high-performance distributed scheduling algorithms for multi-hop wireless networks has seen enormous interest in recent years. the problem is especially challenging when studied under a physical interference model, which requires the SINR at the receiver to be above a certain threshold for decoding success. Under such an SINR model, transmission failure may be caused by interference due to simultaneous transmissions from far away nodes, which exacerbates the difficulty in developing a distributed algorithm. In this paper, we propose a scheduling algorithm that exploits carrier sensing and show that the algorithm is not only amenable to distributed implementation, but also results in throughput optimality. Our algorithm has a feature called the "dual-state" approach, which separates the transmission schedules from the system state and can be shown to improve delay performance.

关键词： Wireless scheduling SINR CSMA/CA discrete Time Markov Chain

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the 20th annual acm-siam symposium on discrete algorithms

Proceedings of the 20th Annual ACM-SIAM Symposium on Discret...

引用

20th annual acm-siam symposium on discrete algorithms

ISBN: (纸本)9780898716801

the proceedings contain 135 papers. the topics discussed include: improved bounds and new techniques for Daveport-Schinzel sequences and their generalizations;perfect matchings via uniform sampling in regular bipartite graphs;the ratio index for budgeted learning, with applications;approximation algorithms for restless bandit problems;better algorithms for benign bandits;comparison-based time-space lower bounds for selection;linear-time algorithms for geometric graphs with sublinearly many crossings;self-overlapping curves revisited;line transversals of convex polyhedra in R3;optimal halfspace range reporting in three dimensions;decomposition of multiple coverings into more parts;on stars and steiner stars. II;and combinatorial algorithms for nearest neighbors, near-duplicates and small-world design.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Appointment Scheduling with discrete Random Durations

Appointment Scheduling with Discrete Random Durations

引用

20th annual acm-siam symposium on discrete algorithms

作者： Begen, Mehmet A. Queyranne, Maurice Univ British Columbia Sander Sch Business Vancouver BC V6T 1Z2 Canada

ISBN: (纸本)9780898716801

We consider the problem of determining optimal appointment schedule for a given sequence of jobs (e.g., medical procedures) on a single processor (e.g., operating room, examination facility), to minimize the expected total underage and overage costs when each job has a random processing duration given by a joint discrete probability distribution. Simple conditions on the cost rates imply that the objective function is submodular and L-convex. then there exists an optimal appointment schedule which is integer and can be found in polynomial time. Our model can handle a given due date for the total processing (e.g., end of day for an operating room) after which overtime is incurred and, no-shows and emergencies.

关键词： Operating rooms

来源：评论

学校读者我要写书评

暂无评论

(Un)Expected Behavior of Digital Search Tree Profile

(Un)Expected Behavior of Digital Search Tree Profile

引用

20th annual acm-siam symposium on discrete algorithms

作者： Drmota, Michael Szpankowski, Wojciech TU Wien Inst Discrete Math & Geometry A-1040 Vienna Austria Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

ISBN: (纸本)9780898716801

A digital search tree (DST) - one of the most fundamental data structures on words is a digital tree in which keys (strings, words) are stored directly in (internal) nodes. Such trees find myriad of applications from the popular Lempel-Ziv'78 data compression scheme to distributed hash tables. the profile of a DST measures the number of nodes at the same distance from the root;it is a function of the number of stored strings and the distance from the root. Most parameters of DST (e.g., height, fill-up) can be expressed in terms of the profile. However, from the inception of DST, the analysis of the profile has been elusive and it has become a prominent open problem in the area of analysis of algorithms. We make here the first, but decisive, step towards solving this problem. We present a precise analysis of the average profile when stored strings are generated by a biased memoryless source. the main technical difficulty of analyzing the profile lies in solving a sophisticated recurrence equation. We present such a solution for the Poissonized version of the problem (i.e., when the number of stored strings is generated by a Poisson distribution) in the Mellin transform domain. To accomplish it, we introduce a novel functional operator that allows us to express the solution in an explicit form, and then using analytic algorithmics tools to extract the asymptotic behavior of the profile. this analysis is surprisingly demanding but once it is carried out it reveals unusually intriguing and interesting behavior. the average profile undergoes several phase transitions when moving from the root to the longest path. At first, it resembles a full tree until it abruptly starts growing polynomially and it oscillates in this range. Our results are derived by methods of analytic algorithmics such as generating functions, Mellin transform, Poissonization and de-Poissonization, the saddle-point method, singularity analysis and uniform asymptotic analysis.

关键词： Digital search trees trees profile analytic combinatorics analysis of algorithms generating functions Mellin transform

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the Twentieth 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 2009年 xiii-xiv页

作者： Mathieu, Claire

来源：评论

学校读者我要写书评

暂无评论

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

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on D...

引用

19th annual acm-siam symposium on discrete algorithms

ISBN: (纸本)9780898716474

the proceedings contain 134 papers. the topics discussed include: delaunay graphs of point sets in the plane with respect to axis-parallel rectangles;maintaining deforming surface meshes;two-phase greedy algorithms for some classes of combinatorial linear programs;yet another algorithm for dense max cut: go greedy;computing large matchings fast;distributed broadcast in unknown radio networks;the power of memory in randomized broadcasting;competitive queue management for latency sensitive packets;a nearly linear time algorithm for the half integral disjoint paths packing;nondecreasing paths in a weighted graph or: how to optimally read a train schedule;graph balancing: a special case of scheduling unrelated parallel machines;on the connectivity of dynamic random geometric graphs;balls and bins with structure: balanced allocations on hypergraphs;improved algorithms for orienteering and related problems;and deterministic random walks on regular trees.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Learning mixtures of product distributions over discrete domains

引用

siam JOURNAL ON COMPUTING 2008年第5期37卷 1536-1564页

作者： Feldman, Jon O'Donnell, Ryan Servedio, Rocco A. Google New York Off New York NY 10011 USA Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA Carnegie Mellon Univ Sch Comp Sci Pittsburgh PA 15213 USA Columbia Univ Dept Comp Sci New York NY 10027 USA

We consider the problem of learning mixtures of product distributions over discrete domains in the distribution learning framework introduced by Kearns et al. [Proceedings of the 26th annual symposium on theory of Computing (STOC), Montreal, QC, 1994, acm, New York, pp. 273-282]. We give a poly(n/epsilon)-time algorithm for learning a mixture of k arbitrary product distributions over the n-dimensional Boolean cube {0, 1}(n) to accuracy epsilon, for any constant k. Previous polynomial-time algorithms could achieve this only for k = 2 product distributions;our result answers an open question stated independently in [M. Cryan, Learning and Approximation algorithms for Problems Motivated by Evolutionary Trees, Ph. D. thesis, University of Warwick, Warwick, UK, 1999] and [Y. Freund and Y. Mansour, Proceedings of the 12th annual Conference on Computational Learning theory, 1999, pp. 183-192]. We further give evidence that no polynomial-time algorithm can succeed when k is superconstant, by reduction from a difficult open problem in PAC (probably approximately correct) learning finally, we generalize our poly(n/epsilon)-time algorithm to learn any mixture of k = O(1) product distributions over {0, 1,..., b - 1}(n), for any b = O(1).

关键词： computational learning theory PAC learning mixture distributions product distributions

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the Nineteenth 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 2008年 xiii页

作者： Mestre, Julián

来源：评论

学校读者我要写书评

暂无评论

Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles

Delaunay graphs of point sets in the plane with respect to a...

引用

19th annual acm-siam symposium on discrete algorithms

作者： Chen, Xiaomin Pach, János Szegedy, Mario Tardos, Gábor Google 76 Ninth Avenue New York NY 10011 United States City College CUNY and Courant Institute NYU 251 Mercer Street New York NY 10012 United States Rutgers University 110 Frelinghuysen Road Piscataway NJ 08854-8019 United States Simon Fraser University 8888 University Drive Burnaby BC V5A 1S6 Canada Rényi Institute Reáltanoda utca 13-15 H-1055 Budapest Hungary

ISBN: (纸本)9780898716474

Given a point set P in the plane, the Delaunay graph with respect to axis-parallel rectangles is a graph defined on the vertex set P, whose two points p,q ∈ P are connected by an edge if and only if there is a rectangle parallel to the coordinate axes that contains p and q, but no other elements of P. the following question of Even et al. [ELRS03] was motivated by a frequency assignment problem in cellular telephone networks. Does there exist a constant c > 0 such that the Delaunay graph of any set of n points in general position in the plane contains an independent set of size at least cn? We answer this question in the negative, by proving that the largest independent set in a randomly and uniformly selected point set in the unit square is O(n log 2 log n/log n), with probability tending to 1. We also show that our bound is not far from optimal, as the Delaunay graph of a uniform random set of n points almost surely has an independent set of size at least cn/log n. We give two further applications of our methods. 1. We construct 2-dimensional n-element partially ordered sets such that the size of the largest independent sets of vertices in their Hasse diagrams is o(n). this answers a question of Matoušek and Prívetivý [MaP06] and improves a result of Kríz and Nešetril [KrN91]. 2. For any positive integers c and d, we prove the existence of a planar point set with the property that no matter how we color its elements by c colors, we find an axis-parallel rectangle containing at least d points, all of which have the same color. this solves an old problem from [BrMP05].

关键词： Color

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：