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

您好，读者！请登录

内蒙古大学图书馆

首页
概况
党建
资源
服务
科研支持
- 论文收录引用证明
- 科技查新
知识产权
档案馆
帮助

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入0个字，您还可以输入200个字

全部搜索
期刊论文
图书
学位论文
标准
纸本馆藏
外文资源发现
数据库导航
超星发现

高级检索

时间限定

出版年份：

文献类型

图书期刊文献学位论文多媒体

馆藏选择

电子馆藏纸本馆藏

核心期刊

全部期刊 SCI 收录期刊 SSCI 收录期刊 EI 收录期刊 CSCD 收录期刊 CSSCI 收录期刊

语言

中文英文

文献类型

期刊文献图书学位论文标准纸本馆藏

帮助

文字说明：

T=题名（书名、题名），A=作者（责任者），K=主题词，P=出版物名称，PU=出版社名称，O=机构（作者单位、学位授予单位、专利申请人），L=中图分类号，C=学科分类号，U=全部字段，Y=年（出版发行年、学位年度、标准发布年）

检索规则说明：

AND代表“并且”；OR代表“或者”；NOT代表“不包含”；(注意必须大写,运算符两边需空一格)

检索范例：

范例一：(K=图书馆学 OR K=情报学) AND A=范并思 AND Y=1982-2016
范例二：P=计算机应用与软件 AND (U=C++ OR U=Basic) NOT K=Visual AND Y=2011-2016

分类表

所选分类

>> <<

限定检索结果

文献类型

129 篇 会议
14 篇 期刊文献
3 册 图书

馆藏范围

146 篇 电子文献
0 种 纸本馆藏

日期分布

学科分类号

87 篇 工学
- 81 篇 计算机科学与技术...
- 20 篇 软件工程
- 5 篇 信息与通信工程
- 3 篇 控制科学与工程
- 1 篇 力学（可授工学、理...
- 1 篇 机械工程
- 1 篇 电气工程
- 1 篇 电子科学与技术（可...
- 1 篇 化学工程与技术
80 篇 理学
- 80 篇 数学
- 8 篇 统计学（可授理学、...
- 2 篇 物理学
- 1 篇 化学
- 1 篇 系统科学
5 篇 管理学
- 4 篇 管理科学与工程(可...
- 4 篇 工商管理
- 1 篇 图书情报与档案管...
3 篇 经济学
- 3 篇 应用经济学

主题

13 篇 algorithms
6 篇 approximation al...
6 篇 polynomial appro...
5 篇 discrete fourier...
4 篇 computational ge...
3 篇 set theory
3 篇 graphic methods
3 篇 logarithm (log)
3 篇 logs
2 篇 computer science
2 篇 generating funct...
2 篇 lattices
2 篇 computational co...
2 篇 shortest vector ...
2 篇 trees (mathemati...
2 篇 average-case ana...
2 篇 planted clique
2 篇 mixtures
2 篇 optimization pro...
2 篇 discrete fourier...

机构

6 篇 rhein westfal th...
3 篇 university of wi...
3 篇 univ bonn res in...
2 篇 university of ca...
2 篇 rhein westfal th...
2 篇 university of ed...
2 篇 department of ma...
2 篇 univ bonn hausdo...
2 篇 univ calif berke...
2 篇 rhein westfal th...
2 篇 department of co...
2 篇 labri université...
2 篇 max planck inst ...
2 篇 inst for basic s...
2 篇 univ warwick ctr...
2 篇 technion israel ...
2 篇 cornell univ 107...
2 篇 univ montpellier...
2 篇 harvard john a p...
2 篇 ut austin austin...

作者

9 篇 csaba d. tóth
5 篇 adrian dumitresc...
3 篇 englert matthias
3 篇 agarwal pankaj k...
3 篇 servedio rocco a...
3 篇 tóth csaba d.
3 篇 grohe martin
2 篇 chan siu-on
2 篇 de anindya
2 篇 stephens-davidow...
2 篇 kapralov michael
2 篇 roughgarden tim
2 篇 michael kaufmann
2 篇 raghavendra pras...
2 篇 sharir micha
2 篇 wiederrecht seba...
2 篇 traub vera
2 篇 vöcking b
2 篇 diakonikolas ili...
2 篇 koch laura varga...

语言

145 篇 英文
1 篇 其他

检索条件"任意字段=13th Annual ACM/SIAM Symposium on Discrete Algorithms"

共 146 条记录，以下是71-80 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

Succinct Sampling from discrete Distributions 13

Succinct Sampling from Discrete Distributions

引用

45th annual acm symposium on the theory of Computing (STOC)

作者： Bringmann, Karl Larsen, Kasper Green Max Planck Inst Informat Campus E1-4 D-66123 Saarbrucken Germany Aarhus Univ MADALGO Aarhus Denmark Aarhus Univ Dept Comp Sci Aarhus Denmark

ISBN: (纸本)9781450320290

We revisit the classic problem of sampling from a discrete distribution: Given n non-negative w -bit integers xi,, x, the task is to build a data structure that allows sampling i with probability proportional to x,. the classic solution is Walker's alias method that takes, when implemented on a Word RAM, 0(n) preprocessing time, 0(1) expected query time for one sample, and n(w+21g n+o(1)) bits of space. Using the terminology of succinct data structures, this solution has redundancy 2n lg n +o(n) bits, i.e., it uses 2n lg n +o(n) bits in addition to the information theoretic minimum required for storing the input. In this paper, we study whether this space usage can be improved. In the systematic case, in which the input is read-only, we present a novel data structure using r + 0(w) redundant bits, 0(n/r) expected query time and 0(n) preprocessing time for any r. this is an improvement in redundancy by a factor of S2(1g n) over the alias method for r = n, even though the alias method is not systematic. Moreover, we complement our data structure with a lower bound showing that this trade-off is tight for systematic data structures. In the non-systematic case, in which the input numbers may be represented in more clever ways than just storing them one-by-one, we demonstrate a very surprising separation from the systematic case: With only 1 redundant bit, it is possible to support optimal 0(1) expected query time and 0(n) preprocessing time! On the one hand, our results improve upon the space requirement of the classic solution for a fundamental sampling problem, on the other hand, they provide the strongest known separation between the systematic and non-systematic case for any data structure problem. Finally, we also believe our upper bounds are practically efficient and simpler than Walker's alias method.

关键词： Walker Alias Method

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

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

引用

symposium on discrete algorithms

作者： Artur Czumaj Christiane Lammersen Morteza Monemizadeh Christian Sohler Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP) University of Warwick School of Computing Science Simon Fraser University Institute for Computer Science University of Frankfurt Department of Computer Science Technische Universit?t Dortmund

ISBN: (纸本)9781627484855

We consider the Euclidean facility location problem with uniform opening cost. In this problem, we are given a set of n points P ? ?~2 and an opening cost f ∈ ?~+ and we want to find a set of facilities F ? ?~2 that minimizes where d(p, q) is the Euclidean distance between p and q. We obtain two main results: ? A (1 + ε)-approximation algorithm with running time 0(nlog n(log n log log n + (log log n)~8 2~(O(log (1/ε)/ε)))),which is O(n log~2 n log log n) for any constant ε. ? the first (1 + ε)-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,..., Δ}~2. the streaming algorithm uses (log △/?)~(o(1)) space. Our PTAS is significantly faster than any previously known (1 + ε)-approximation algorithm for the problem, and is also relatively simple. Our algorithm for dynamic geometric data streams is the first (1 + ε)-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 Ρ into small subsets Pi, such that: ? the cost of solving the facility location problem for each Pi is small (which means that for each Pi one needs to open only a small, polylogarithmic number of facilities), ? Σ_(i) OPT(P_(i)) ≤ (1+ε) ? 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 cells of the partition and estimating the cost from the sample, we obtain our data streaming algorithm.

关键词： (1 + ε)-Approximation Location in Data Streams process dynamic facility location data flow Approximation algorithms location problem streams logs logarithm (log) Set of points partitions rivers Euclidean distance algorithms

来源：评论

学校读者我要写书评

暂无评论

Packing anchored rectangles

Packing anchored rectangles

引用

23rd annual acm-siam symposium on discrete algorithms, SODA 2012

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

ISBN: (纸本)9781611972108

Let S be a set of n points in the unit square [0,1]2, one of which is the origin. We construct n pairwise interior-disjoint axis-aligned empty rectangles such that the lower left corner of each rectangle is a point in S, and the rectangles jointly cover at least a positive constant area (about 0.09). this is a first step towards the solution of a longstanding conjecture that the rectangles in such a packing can jointly cover an area of at least 1/2. Copyright © siam.

关键词：

来源：评论

学校读者我要写书评

暂无评论

the condensation transition in random hypergraph 2-coloring

The condensation transition in random hypergraph 2-coloring

引用

23rd annual acm-siam symposium on discrete algorithms, SODA 2012

作者： Coja-Oghlan, Amin Zdeborová, Lenka University of Warwick Mathematics and Computer Science Zeeman Building Coventry CV4 7AL United Kingdom Institut de Physique Théorique IPhT CNRS 91191 Gif-sur-Yvette France

ISBN: (纸本)9781611972108

For many random constraint satisfaction problems such as random satisfiability or random graph or hypergraph coloring, the best current estimates of the threshold for the existence of solutions are based on the first and the second moment method. However, in most cases these techniques do not yield matching upper and lower bounds. Sophisticated but non-rigorous arguments from statistical mechanics have ascribed this discrepancy to the existence of a phase transition called condensation that occurs shortly before the actual threshold for the existence of solutions and that affects the combinatorial nature of the problem (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborová: PNAS 2007). In this paper we prove for the first time that a condensation transition exists in a natural random CSP, namely in random hypergraph 2-coloring. Perhaps surprisingly, we find that the second moment method applied to the number of 2-colorings breaks down strictly before the condensation transition. Our proof also yields slightly improved bounds on the threshold for random hypergraph 2-colorability. Copyright © siam.

关键词： Statistical mechanics

来源：评论

学校读者我要写书评

暂无评论

the MAX-CUT of sparse random graphs

The MAX-CUT of sparse random graphs

引用

23rd annual acm-siam symposium on discrete algorithms, SODA 2012

作者： Daudé, Hervé Martínez, Conrado Rasendrahasina, Vonjy Ravelomanana, Vlady LATP - UMR CNRS 6622 Université de Provence 13453 Marseille Cedex 13 France Dept. Llenguatges I Sistemes Informàtics Universitat Politècnica de Catalunya E-08034 Barcelona Spain LIPN - UMR CNRS 7030 Université de Paris Nord 93430 Villetaneuse France LIAFA - UMR CNRS 7089 Université Denis Diderot 75205 Paris Cedex 13 France

ISBN: (纸本)9781611972108

A k-cut of a graph G = (V, E) is a partition of its vertex set into k parts;the size of the k-cut is the number of edges with endpoints in distinct parts. MAX-k-CUT is the optimization problem of finding a k-cut of maximal size and the case where k = 2 (often called MAX-CUT) has attracted a lot of attention from the research community. MAX-CUT - more generally, MAX-k-CUT - is NP-hard and it appears in many applications under various disguises. In this paper, we consider the MAX-CUT problem on random connected graphs script C(n, m) and on Erdocombining double acute accents-Rényi random graphs script G(n, m). More specifically, we consider the distance from bipartiteness of a graph G = (V, E), the minimum number of edge deletions needed to turn it into a bipartite graph. If we denote this distance DISTBIP (G), the size of the MAX-CUT of a graph G = (V, E) is clearly given by |E| - DISTBIP (G). Fix Ε > 0. For random connected graphs, we prove that asymptotically almost surely (a.a.s) DISTBIP (script C(n,m)) ∼ m-n/4 whenever m = n + O(n1-Ε). For sparse random graphs script G(n,m = n/2 + μn2/3/2) we show that DISTBIP (script G(n,m)) is a.a.s about (2m-n)3/6n2+ 1/12 log n-1/4 log μ for any 1 μ ≤ O(n1/3-Ε). Copyright © siam.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Simultaneous approximations for adversarial and stochastic online budgeted allocation

Simultaneous approximations for adversarial and stochastic o...

引用

23rd annual acm-siam symposium on discrete algorithms, SODA 2012

作者： Mirrokni, Vahab S. Gharan, Shayan Oveis Zadimoghaddam, Morteza Google Research 76 9th Ave. New York NY 10011 United States Department of Management Science and Engineering Stanford University United States MIT Computer Science and Artificial Intelligence Laboratory Cambridge MA 02139 United States

ISBN: (纸本)9781611972108

Motivated by online ad allocation, we study the problem of simultaneous approximations for the adversarial and stochastic online budgeted allocation problem. this problem consists of a bipartite graph G = (X, Y, E), where the nodes of Y along with their corresponding capacities are known beforehand to the algorithm, and the nodes of X arrive online. When a node of X arrives, its incident edges, and their respective weights are revealed, and the algorithm can match it to a neighbor in Y. the objective is to maximize the weight of the final matching, while respecting the capacities. When nodes arrive in an adversarial order, the best competitive ratio is known to be 1 - 1/e, and it can be achieved by the Ranking [18], and its generalizations (Balance [16, 21]). On the other hand, if the nodes arrive through a random permutation, it is possible to achieve a competitive ratio of 1 - Ε [9]. In this paper we design algorithms that achieve a competitive ratio better than 1 - 1/e on average, while preserving a nearly optimal worst case competitive ratio. Ideally, we want to achieve the best of both worlds, i.e, to design an algorithm with the optimal competitive ratio in both the adversarial and random arrival models. We achieve this for unweighted graphs, but show that it is not possible for weighted graphs. In particular, for unweighted graphs, under some mild assumptions, we show that Balance achieves a competitive ratio of 1 - Ε in a random permutation model. For weighted graphs, however, we prove this is not possible;we prove that no online algorithm that achieves an approximation factor of 1 - 1/e for the worst-case inputs may achieve an average approximation factor better than 97.6% for random inputs. In light of this hardness result, we aim to design algorithms with improved approximation ratios in the random arrival model while preserving the competitive ratio of 1 - 1/e in the worst case. To this end, we show the algorithm proposed by [21] achieves a competitive r

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Prize-collecting Steiner problems on planar graphs

Prize-collecting Steiner problems on planar graphs

引用

作者： Bateni, M. Chekuri, C. Ene, A. Hajiaghayi, M.T. Korula, N. Marx, D. Department of Computer Science Center for Computational Intractability Princeton University Princeton NJ 08540 United States Department of Computer Science University of Illinois Urbana IL 61801 United States Department of Computer Science University of Maryland 115 A.V. Williams Building College Park MD 20742 United States Google Research 76 9th Ave New York NY 10011 United States Humboldt-Universität zu Berlin Germany

ISBN: (纸本)9780898719932

In this paper, we reduce Prize-Collecting Steiner TSP (PCTSP), Prize-Collecting Stroll (PCS), Prize-Collecting Steiner Tree (PCST), Prize-Collecting Steiner Forest (PCSF), and more generally Submodular Prize-Collecting Steiner Forest (SPCSF), on planar graphs (and also on bounded-genus graphs) to the corresponding problem on graphs of bounded treewidth. More precisely, for each of the mentioned problems, an a-approximation algorithm for the problem on graphs of bounded treewidth implies an (α + Ε)- approximation algorithm for the problem on planar graphs (and also bounded-genus graphs), for any constant Ε > 0. PCS, PCTSP. and PCST can be solved exactly on graphs of bounded treewidth and hence we obtain a PTAS for these problems on planar graphs and bounded-genus graphs. In contrast, we show that PCSF is APX-hard to approximate on series-parallel graphs, which are planar graphs of treewidth at most 2. Apart from ruling out a PTAS for PCSF on planar graphs and bounded treewidth graphs, this result is also interesting since it gives the first provable hardness separation between the approxiinability of a problem and its prize-collecting version. We also show that PCSF is APX-hard on Euclidean instances.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

全选清除本页清除全部题录导出标记到“检索档案”

共15页 << < 4 5 6 7 8 9 10 11 12 13 > >>

检索报告对象比较合并检索0

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

电话和邮箱必须正确填写，我们会与您联系确认。

联系人：

所在院系：

联系邮箱：

联系电话：

内蒙古自治区呼和浩特市赛罕区大学西街235号邮编: 010021

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：