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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

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

分类表

所选分类

>> <<

限定检索结果

文献类型

137 篇 会议
60 册 图书

馆藏范围

188 篇 电子文献
16 种 纸本馆藏

日期分布

学科分类号

167 篇 理学
- 166 篇 数学
- 8 篇 生物学
- 6 篇 统计学（可授理学、...
- 2 篇 生态学
- 1 篇 物理学
- 1 篇 系统科学
150 篇 工学
- 142 篇 计算机科学与技术...
- 3 篇 软件工程
- 2 篇 机械工程
- 2 篇 仪器科学与技术
- 2 篇 动力工程及工程热...
- 2 篇 信息与通信工程
- 2 篇 控制科学与工程
- 1 篇 力学（可授工学、理...
- 1 篇 兵器科学与技术
- 1 篇 环境科学与工程（可...
9 篇 农学
- 1 篇 农业资源与环境
7 篇 管理学
- 7 篇 管理科学与工程(可...
6 篇 经济学
- 6 篇 应用经济学
1 篇 哲学
- 1 篇 哲学
1 篇 法学
- 1 篇 社会学

主题

15 篇 approximation al...
6 篇 data structures
6 篇 congresses.
5 篇 polynomial appro...
5 篇 graph theory
3 篇 computational co...
3 篇 probability dist...
3 篇 vector spaces
3 篇 computational ge...
3 篇 graphic methods
3 篇 linear programmi...
3 篇 costs
3 篇 game theory
3 篇 cryptography
3 篇 geometry
2 篇 数学
2 篇 literary collect...
2 篇 sorting
2 篇 proceedings
2 篇 landforms

机构

4 篇 max planck inst ...
3 篇 georgia inst tec...
3 篇 res org informat...
3 篇 ibm corp almaden...
3 篇 mit comp sci & a...
3 篇 university of wa...
3 篇 carnegie mellon ...
2 篇 cnrs inria lab i...
2 篇 mit ctr operat r...
2 篇 univ wisconsin d...
2 篇 univ michigan an...
2 篇 univ calif irvin...
2 篇 princeton univ d...
2 篇 princeton univer...
2 篇 york univ n york...
2 篇 cornell univ dep...
2 篇 max planck inst ...
2 篇 mcgill univ dept...
2 篇 harvard univ dep...
2 篇 univ toronto dep...

作者

4 篇 kawarabayashi ke...
4 篇 patrascu mihai
3 篇 sauerwald thomas
3 篇 woodruff david p...
3 篇 american mathema...
3 篇 kleinberg robert
3 篇 demaine erik d.
3 篇 symposium in app...
3 篇 gupta anupam
2 篇 mathieu claire
2 篇 rabani yuval
2 篇 talwar kunal
2 篇 chandrasekaran k...
2 篇 gamarnik david
2 篇 andoni alexandr
2 篇 saberi amin
2 篇 friedrich tobias
2 篇 bansal nikhil
2 篇 reed bruce
2 篇 robert sedgewick

语言

147 篇 英文
50 篇 中文

检索条件"丛书名=Proceedings in Applied Mathematics"

共 197 条记录，以下是51-60 订阅

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

详细简洁

排序：

Inapproximability for VCG-Based Combinatorial Auctions

Inapproximability for VCG-Based Combinatorial Auctions

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Buchfuhrer, Dave Dughmi, Shaddin Fu, Hu Kleinberg, Robert Mossel, Elchanan Papadimitriou, Christos Schapira, Michael Singer, Yaron Umans, Chris CALTECH Dept Comp Sci Pasadena CA 91125 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA Cornell Univ Dept Comp Sci Ithaca NY 14850 USA Univ Calif Berkeley Math & Comp Sci Weizrnann Inst Statist & Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA Yale Univ Dept Comp Sci New Haven CT 06520 USA CALTECH Dept Comp Sci Pasadena CA 91125 USA

ISBN: (纸本)9780898717013

The existence of incentive-compatible, computationally-efficient mechanisms flu combinatorial auctions with good approximation ratios is the paradigmatic problem in algorithmic mechanism design It is believed that, in many cases, good approximations for combinatorial auctions may be unattainable due to an inherent clash between truthfulness and computational efficiency. In tins paper, we prove the first computational-complexity in-approximability results for incentive-compatible mechanisms for combinatorial auctions. Our results are tight, hold for the important, class of VCG-based mechanisms, and are based on the complexity assumption that NP has no polynomial-size circuits We show two different, techniques to obtain such lower bounds one for deterministic mechanisms that attains optimal dependence on the number of players and number of items, and one that also applies to a class of randomized mechanisms and attains optimal dependence on the number of players Both techniques ale based on novel VC dimension machinery.

关键词： Computational efficiency

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds for Testing Triangle-freeness in Boolean Functions

Lower Bounds for Testing Triangle-freeness in Boolean Functi...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Bhattacharyya, Arnab Xie, Ning MIT CSAIL Cambridge MA 02139 USA

ISBN: (纸本)9780898717013

Let f(1), f(2), f(3) : F-2(n) --> {0, 1} be three Boolean functions We say a triple (x, y, x + y) is a triangle in the function-triple (f(1),f(2),f(3)) if f(1)(x) = f(2)(y) = f(3)(x + y) = 1 (f(1),f(2),f(3)) is said to be triangle-free if there is no triangle in the triple The distance between a function-triple and triangle-freeness is the minimum fraction of function values one needs to modify in order to make the function-triple triangle-free. A canonical tester for triangle-freeness repeatedly picks x and y uniformly and independently at random and checks if f(1)(x) = f(2)(y) = f(3)(x y) = 1 Based on an algebraic regularity lemma, Green showed that the number of queries for the canonical testing algorithm is upper-bounded by a tower of 2's whose height is polynomial in 1/epsilon. A trivial query complexity lower bound of Omega(1/epsilon) is straightforward to show. In this paper, we give the first non-trivial query complexity lower bound for testing triangle-freeness in Boolean functions. We show that, for every small enough c there exists an integer n(0)(epsilon) such that for all n >= n(0) there exists a function-triple f(1), f(2), f(3) F-2(n) --> {0,1} depending on all the n variables which is E-far from being triangle-free and requires (1/epsilon)(4 847) queries for the canonical tester. For the single function case that f(1) = f(2) = f(3), we obtain a weaker lower bound of (1/epsilon)(3 409) We also show that the query complexity of any general (possibly adaptive) one-sided tester for triangle-freeness is at least square-root of the query complexity of the corresponding canonical tester. Consequently, this yields (1/epsilon)(2 423) and (1/epsilon)(1 704) query complexity lower bounds for multi-function and single-function triangle-freeness respectively, with respect to general one-sided testers.

关键词： Boolean functions

来源：评论

学校读者我要写书评

暂无评论

Towards the Randomized k-Server Conjecture: A Primal-Dual Approach

Towards the Randomized <i>k</i>-Server Conjecture: A Primal-...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Bansal, Nikhil Buchbinder, Niv Naor, Joseph (Seffi) IBM Corp Thomas J Watson Res Ctr Box 218 Yorktown Hts NY 10598 USA

ISBN: (纸本)9780898717013

Recently, Cote et al. [10] proposed an approach for solving the k-server problem on Hierchically Separated Trees (HSTs) In particular, they define a problem on a uniform metric, and show that if an algorithm with a certain refined guarantee exists for it, then one can obtain polylogarithmic (in diameter) competitive factors for the k-server problem on HSTs by solving this problem recursively. By designing such an algorithm for a two point metric, they obtained a logarithmic competitive algorithm for well-seperated binary HSTs Extending their result. to uniform metrics on arbitrarily many points would imply a poly-logarithmic competitive algorithm for k-server on general HSTs (and hence general metrics) and is thus of major interest Here, we design such an algorithm for any uniform metric, provided the instance satisfies a certain "convexity" property Even though this does not. give a result fin k-server, convexity seems to be a very natural property, and we give evidence that instances arising in the Cote et al [10] reduction from k-server essentially possess this property, suggesting that this might, be a promising approach Already, our setting is general enough to model the finely competitive paging problem proposed by Blum et al [4], who motivated it as a first. step towards achieving a polylog(k) competitive algorithm for k-server Our result implies an r + O(log k)-competitive algorithm for finely competitive paging, resolving the main open problem of [4] Our results are based on an extension of the primal-dual framework for online algorithms developed by Buchbinder and Naoi [7] The original approach works for problems whose offline version can be expressed as a packing of a covering linear program, possibly with box constraints The online nature of the problem is modeled by revealing the constraints one by one and the requirement that variables can only be increased over time. Here, we consider more general types of constraints, where terms can be both positive

关键词： Linear programming

来源：评论

学校读者我要写书评

暂无评论

Testing Monotone Continuous Distributions on High-dimensional Real Cubes

Testing Monotone Continuous Distributions on High-dimensiona...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Adamaszek, Michal Czumaj, Artur Sohler, Christian Univ Warwick Ctr Discrete Math & Applicat DIMAP Coventry CV4 7AL W Midlands England

ISBN: (纸本)9780898717013

We study the task of testing properties of probability distributions. We consider a scenario in which we have access to independent samples of an unknown distribution D with infinite (perhaps even uncountable) support Our goal is to test whether D has a given property of it is e-far nom it (in the statistical distance, with the L-1-distance measure) It is not difficult to see that for many natural distributions on infinite of uncountable domains, no testing algorithm can exist and the central objective of our study is to understand if there ale any nontrivial distributions that can be efficiently tested. For example, it is easy to see that there is no testing algorithm that tests if a given probability distribution on [0,1] is uniform We show however, that if some additional information about the input distribution is known, testing uniform distribution is possible. We extend the recent result about testing uniformity for monotone distributions on Boolean n-dimensional cubes by Rubinfeld and Servedio (STOC'2005) to the case of continuous [0, 1](n) cubes. We show that if a distribution D on [0,1](n) is monotone, then one can test if D is uniform with the sample complexity O(n/epsilon(2)) This result is optimal up to a polylogarithmic factor

关键词： Probability distributions

来源：评论

学校读者我要写书评

暂无评论

The Rank of Diluted Random Graphs

The Rank of Diluted Random Graphs

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Bordenave, Charles Lelarge, Marc Univ Toulouse Inst Math Toulouse France Univ Toulouse Dept Informat Toulouse France

ISBN: (纸本)9780898717013

We investigate the lank of the adjacency matrix of large diluted random graphs for a sequence of graphs converging locally to a tree, we give new formulas for the asymptotic of the multiplicity of the eigenvalue 0. In particular, the result depends only on the limiting tree structure, showing that the normalized rank is 'continuous at infinity'. Our work also gives a new formula for the mass at zero of the spectral measure of a Galton-Watson tree Our techniques of proofs borrow ideas from analysis of algorithms, random matrix theory, statistical physics and analysis of Schrodinger operators on trees

关键词： Statistical Physics

来源：评论

学校读者我要写书评

暂无评论

Monotonicity in Bargaining Networks

Monotonicity in Bargaining Networks

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Azar, Yossi Devanur, Nikhil R. Jain, Kamal Rabani, Yuval Microsoft Res 1 Microsoft Way Redmond WA 98052 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)9780898717013

We study bargaining networks, discussed in a recent impel of Kleinberg and Tardos [KT08], nom the perspective of cooperative game theory. In particular we examine three solution concepts, the nucleolus, the core center and the core median. All solution concepts define unique solutions, so they provide testable predictions. We define a new monotonicity property that is a natural axiom of any bargaining game solution, and we prove that all three of them satisfy this monotonicity property. This is actually in contrast to the conventional wisdom for general cooperative games that monotonicity and the core condition (which is a basic property that all three of them satisfy) ale incompatible with each other. Our proofs are based on a primal-dual arugument (for the nucleolus) and on the PKG inequality (for the core center and the core median). We further observe sonic qualitative differences between the solution concepts. In particular, there are cases where a strict version of our monotonicity property is a natural axiom, but only the core center and the core median satisfy it On the other hand, the nucleolus is easy to compute, whereas computing the core center or the core median is #P-hard (yet it can be approximated in polynomial time)

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

The focus of attention problem

The focus of attention problem

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Goossens, Dries Polyakovskiy, Sergey Spieksma, Frits C. R. Woeginger, Gerhard J. Katholieke Univ Leuven Operat Res Grp Louvain Belgium Eindhoven Univ Technol Dept Math Eindhoven Netherlands

ISBN: (纸本)9780898717013

We consider the problem of assigning sensors to track targets so as to minimize the expected error in the resulting estimation for target locations The so-called Focus of Attention problem deals with the special case where every target is tracked by one pair of range sensors We provide a complete complexity and approximability analysis of the Focus Of Attention problem. We establish its strong NP-hardness, and we construct a polynomial time approximation scheme for it

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs

Cache-Oblivious Dynamic Dictionaries with Update/Query Trade...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Brodal, Gerth Stolting Demaine, Erik D. Fineman, Jeremy T. Iacono, John Langerman, Stefan Munro, J. Ian Aarhus Univ Dept Comp Sci IT Parken Abogade 34 DK-8200 Aarhus Denmark MADALGO Ctr Massive Data Algorithm Ctr Danish Natl Res Fdn Aarhus Denmark MIT Artificial Intelligence Lab Dept Comp Sci Cambridge MA 02139 USA Polytech Inst New York Univ Dept Comp Sci & Engn Brooklyn NY 11201 USA Univ Libre Bruxelles Dept Comp Sci Maitre Rech FRS FNRS B-1050 Brussels Belgium Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

ISBN: (纸本)9780898717013

Several existing cache-oblivious dynamic dictionaries achieve O(log(B) N) (or slightly better O(log(B) N/M)) memory transfers per operation, where N is the number of items stored, M is the memory size, and B is the block size, which matches the classic B-tree data structure. One recent structure achieves the same query bound and a sometimes-better amortized update bound of O (1/B circle minus(1/(log log B)2) log(B) N + 1/B log(2) N) memory transfers. This paper presents a new data structure, the xDict, implementing predecessor queries in O(1/epsilon log(B) N/M) worst-case memory transfers and insertions and deletions in O (1/epsilon B1-c log(B) N/M) amortized memory transfers, for any constant epsilon with 0 < epsilon < 1. For example, the xDict achieves subconstant amortized update cost when N = M B-o(B1-e), whereas the B-tree's circle minus(log(B) N/M)) is subconstant only when N = o(MB), and the previously obtained circle minus (1/B-circle minus(1/(log log B)(2)) log(B) N + 1/B log(2) N) is subconstant only when N = o(2(root B)). The xDict attains the optimal tradeoff between insertions and queries, even in the broader external-memory model, for the range where inserts cost between Omega(1/B lg(1+epsilon) N) and O(1/lg(3) N) memory transfers.

关键词： Data structures

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Analysis of the Semidefinite Relaxation Detector in Digital Communications

Probabilistic Analysis of the Semidefinite Relaxation Detect...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： So, Anthony Man-Cho Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China

ISBN: (纸本)9780898717013

We consider the problem of detecting a vector of symbols that, is being transmitted over a lading multiple-input multiple-output (MIMO) channel, where each symbol is an M-th loot of unity for some fixed M >= 2 Although the symbol vector that minimizes the Enrol probability can be found by the so-called maximum-likelihood (ML) detector, its computation is intractable in general In this paper we analyze a popular polynomial time heuristic, called the semidefinite relaxation (SDI?) detector, for the problem mid establish its first non asymptotic performance guarantee Specifically, in the low signal-to-noise ratio (SNR) region, we show that, for any M >= 2, the SDR detector will yield a constant. factor approximation to the optimal log-likelihood value with a probability that increases exponentially fast to as the channel size increases In the high SNR, legion, it. is known that for M = 2. the SDR. detector will yield an exact solution to the ML detection problem with a. probability that converges to I We lane this result by establishing the rate of convergence. Our work can be viewed as an average-case analysis of a certain SDP relaxation, and the input distribution we use is motivated by physical considerations Our results also refine and extend those in previous work, which are all asymptotic in nature and apply only to the problem of detecting binary (i e, when M = 2) vectors. In particular, our results can give better insight into the performance of the SDR. detector in practical settings

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Terrain Guarding is NP-Hard

Terrain Guarding is NP-Hard

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： King, James Krohn, Erik Univ Iowa Dept Comp Sci Iowa City IA 52242 USA McGill Univ Sch Comp Sci Montreal PQ H3A 2T5 Canada

ISBN: (纸本)9780898717013

A set G of points on a 1.5-dimensional terrain, also known as an x-monotone polygonal chain, is said to guard the terrain if every point on the terrain is seen by a point in G Two points on the terrain see each other if and only if the line segment between them is never strictly below the terrain The minimum terrain guarding problem asks for a minimum guarding set for the given input terrain Using a reduction from PLANAR. 3-SAT we prove that, the decision version of this problem is NP-hard This solves a significant open problem and complements recent positive approximability results for the optimization problem.

关键词： Landforms

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共20页 << < 2 3 4 5 6 7 8 9 10 11 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：