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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入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

分类表

所选分类

>> <<

限定检索结果

文献类型

73 篇 会议
11 篇 期刊文献
1 册 图书

馆藏范围

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

日期分布

学科分类号

57 篇 工学
- 53 篇 计算机科学与技术...
- 10 篇 软件工程
- 3 篇 信息与通信工程
- 1 篇 机械工程
- 1 篇 电气工程
- 1 篇 建筑学
- 1 篇 土木工程
- 1 篇 水利工程
41 篇 理学
- 41 篇 数学
- 4 篇 统计学（可授理学、...
2 篇 管理学
- 1 篇 管理科学与工程(可...
- 1 篇 工商管理
- 1 篇 图书情报与档案管...
1 篇 经济学
- 1 篇 应用经济学

主题

10 篇 algorithms
5 篇 discrete fourier...
3 篇 generating funct...
3 篇 logarithm (log)
3 篇 logs
3 篇 discrete mathema...
2 篇 computer science
2 篇 approximation al...
2 篇 average-case ana...
2 篇 mixtures
2 篇 analysis of algo...
2 篇 set theory
2 篇 optimization pro...
2 篇 discrete fourier...
2 篇 dependence
2 篇 smoothed analysi...
2 篇 mellin transform
2 篇 directed graphs
2 篇 analytic combina...
2 篇 dynamic programm...

机构

3 篇 univ bonn res in...
2 篇 rhein westfal th...
2 篇 university of ed...
2 篇 univ bonn hausdo...
2 篇 department of co...
2 篇 max planck inst ...
2 篇 inst for basic s...
2 篇 univ warwick ctr...
2 篇 univ montpellier...
2 篇 univ warwick dep...
2 篇 stanford univ st...
2 篇 natl & kapodistr...
1 篇 columbia univers...
1 篇 department of el...
1 篇 school of comput...
1 篇 univ southern ca...
1 篇 inst. discrete m...
1 篇 natl inst inform...
1 篇 technische unive...
1 篇 ctr wiskunde & i...

作者

3 篇 diakonikolas ili...
2 篇 chan siu-on
2 篇 stephens-davidow...
2 篇 kapralov michael
2 篇 wiederrecht seba...
2 篇 traub vera
2 篇 vöcking b
2 篇 czumaj artur
2 篇 thilikos dimitri...
2 篇 vygen jens
2 篇 giannopoulou arc...
2 篇 agarwal pankaj k...
2 篇 indyk piotr
2 篇 siu-on chan
2 篇 beier r
2 篇 servedio rocco a...
2 篇 piotr indyk
1 篇 racke harald
1 篇 huacheng yu
1 篇 halldorsson magn...

语言

83 篇 英文
1 篇 其他
1 篇 中文

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

共 85 条记录，以下是41-50 订阅

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

详细简洁

排序：

Finding orthogonal vectors in discrete structures 14

Finding orthogonal vectors in discrete structures

引用

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

作者： Ryan Williams Huacheng Yu Computer Science Department Stanford University

ISBN: (纸本)9781611973389

Hopcroft's problem in d dimensions asks: given n points and n hyperplanes in R~d, does any point lie on any hyperplane? Equivalently, if we are given two sets of n vectors each in R~(d+1), is there a pair of vectors (one from each set) that are orthogonal? this problem has a long history and a multitude of applications. It is widely believed that for large d, the problem is subject to the curse of dimensionality: all known algorithms need at least f(d) · n~(2-1/O(d)) time for fast-growing functions f, and at the present time there is little hope that a n-2ε, poly(d) time algorithm will be found. We consider Hopcroft's problem over finite fields and integers modulo composites, leading to both surprising algorithms and hardness reductions. the algorithms arise from studying the communication problem of determining whether two lists of vectors (one list held by Alice, one by Bob) contain an orthogonal pair of vectors over a discrete structure (one from each list). We show the randomized communication complexity of the problem is closely related to the sizes of matching vector families, which have been studied in the design of locally decodable codes. Letting HOPCROFT_R denote Hopcroft's problem over a ring R, we give randomized algorithms and almost matching lower bounds (modulo a breakthrough in SAT algorithms) for HOPCROFT_R, when R is the ring of integers modulo m or a finite field. Building on the ideas developed here, we give a very simple and efficient output-sensitive algorithm for matrix multiplication that works over any field.

关键词： orthogonal vector Matrix multiplication R-RING Galois fields algorithms Modulo able to communicate Integer PDE6B gene communication complexity randomized algorithms Curse of Dimensionality Hyperplane Cloning Vectors Pairing

来源：评论

学校读者我要写书评

暂无评论

discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems 13

Discrete Convexity and Polynomial Solvability in Minimum 0-E...

引用

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

作者： Hirai, Hiroshi Univ Tokyo Grad Sch Informat Sci & Technol Dept Math Informat Tokyo 1138656 Japan

ISBN: (纸本)9781611973105;9781611972511

the minimum 0-extension problem 0-Ext[Gamma] on a graph Gamma is: given a set V including the vertex set V-Gamma of Gamma and a nonnegative cost function c defined on the set of all pairs of V, find a 0-extension d of the path metric d of Gamma with Sigma(xy) c(xy)d(x;y) minimum, where a 0-extension is a metric d on V such that the restriction of d to V-Gamma coincides with d(Gamma) and for all x is an element of V there exists a vertex s in Gamma with d(x;s) = 0. 0-Ext[Gamma] includes a number of basic combinatorial optimization problems, such as minimum (s;t)-cut problem and multiway cut problem. Karzanov proved the polynomial solvability for a certain large class of modular graphs, and raised the question: What are the graphs Gamma for which 0-Ext[Gamma] can be solved in polynomial time? He also proved that 0-Ext[Gamma] is NP-hard if Gamma is not modular or not orientable (in a certain sense). In this paper, we prove the converse: if Gamma is orientable and modular, then 0-Ext[Gamma] can be solved in polynomial time. this completes the classification of the tractable graphs for the 0-extension problem. To prove our main result, we develop a theory of discrete convex functions on orientable modular graphs, analogous to discrete convex analysis by Murota, and utilize a recent result of thapper and Zivny on Valued-CSP.

关键词： Cost functions

来源：评论

学校读者我要写书评

暂无评论

Computing the discrete Frechet Distance in Subquadratic Time

Computing the Discrete Frechet Distance in Subquadratic Time

引用

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

作者： Agarwal, Pankaj K. Ben Avraham, Rinat Kaplan, Haim Sharir, Micha Duke Univ Dept Comp Sci Box 90129 Durham NC 27708 USA Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel NYU Courant Inst Math Sci New York NY 10012 USA

ISBN: (纸本)9781611973105;9781611972511

the Frechet 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 Frechet 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 Frechet 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 Frechet 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.

关键词： Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

(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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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.

关键词：

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共9页 << < 1 2 3 4 5 6 7 8 9 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：