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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入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 条记录，以下是31-40 订阅

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

详细简洁

排序：

Pricing Randomized Allocations

Pricing Randomized Allocations

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Briest, Patrick Chawla, Shuchi Kleinberg, Robert Weinberg, S. Matthew Univ Paderborn Dept Comp Sci Paderborn Germany Cornell Univ Dept Comp Sci Ithaca NY 14850 USA Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

ISBN: (纸本)9780898717013

Randomized mechanisms, which map a set of bids to a probability distribution over outcomes rather than a single outcome, are an important but ill-understood area of computational mechanism design. We investigate the role of randomized outcomes (henceforth, "lotteries") in the context of a fundamental and archetypical multi-parameter mechanism design problem: selling heterogeneous items to unit-demand bidders To what extent can a seller improve her revenue by pricing lotteries rather than items, and does this modification of the problem affect its computational tractability? Our results show that the answers to these questions hinge on whether consumers can purchase only one lottery (the buy-one model) or purchase any set of lotteries and receive an independent sample from each (the buy-many model). In the buy-one model, there is a polynomial-time algorithm to compute the revenue-maximizing envy-free prices (thus overcoming the inapproximability of the corresponding item pricing problem) and the revenue of the optimal lottery system can exceed the revenue of the optimal item pricing by an unbounded factor as long as the number of item types is at least 4. In the buy-many model with n item types, the profit achieved by lottery pricing can exceed item pricing by a factor of e(log TO but not more, and optimal lottery pricing cannot be approximated within a factor of O (n(epsilon)) for some epsilon > 0, unless NP subset of boolean AND(delta>0) BPTIME(2(O(n delta))). Our lower bounds rely on a mixture of geometric and algebraic techniques, whereas the upper bounds use a novel rounding scheme to transform a mechanism with randomized outcomes into one with deterministic outcomes while losing only a bounded amount of revenue.

关键词： Costs

来源：评论

学校读者我要写书评

暂无评论

Price of Anarchy for Greedy Auctions

Price of Anarchy for Greedy Auctions

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Lucier, B. Borodin, A. Univ Toronto Dept Comp Sci Toronto ON M5S 1A1 Canada

ISBN: (纸本)9780898717013

We study mechanisms for utilitarian combinatorial allocation problems, where agents are not assumed to be single-minded This class of problems includes combinatorial auctions, multi-unit auctions, unsplittable flow problems, and others. We focus on the problem of designing mechanisms that approximately optimize social welfare at every Bayes-Nash equilibrium (BNE), which is the standard notion of equilibrium in settings of incomplete information. For a broad class of greedy approximation algorithms, we give a general black-box reduction to deterministic mechanisms with almost no loss to the approximation ratio at any BNE We also consider the special case of Nash equilibria in full-information games, where we obtain tightened results. This solution concept is closely related to the well-studied price of anarchy. Furthermore, for a rich subclass of allocation problems, pure Nash equilibria are guaranteed to exist for our mechanisms. For many problems, the approximation factors we obtain at equilibrium improve upon the best known results for deterministic truthful mechanisms In particular, we exhibit a simple deterministic mechanism for general combinatorial auctions that obtains an O(root m) approximation at every BNE.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Generating a d-dimensional linear subspace efficiently

Generating a <i>d</i>-dimensional linear subspace efficientl...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Yuster, Raphael Univ Haifa Dept Math IL-31905 Haifa Israel

ISBN: (纸本)9780898717013

We present an algorithm for computing a d-dimensional subspace of the row space of a matrix For an n x n matrix A with m nonzero entries and with rank(A) >= d the algorithm generates a d x n matrix with full row rank and which is a subspace of Rows(A). If rank(A) < d the algorithm generates a rank(A) x n row-equivalent matrix The running time of the algorithm is O(min{n(2-2)/(w)m(1/w)d(w-2-2+1/)w , n(2)d(w-2)}) where w < 2.376 is the matrix multiplication exponent. An immediate corollary of the algorithm is the construction of a row-reduced equivalent matrix of A, and hence the computation of rank(A), in time O(min{n(2-2)/(w)m(1/w)rank(A)(w-2+1/w), n(2)rank(A)(w-2)}). We note that the running time is sub-quadratic if d < (n(2)/m)(0 528).

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

ALGORITHMIC LOWER BOUNDS FOR PROBLEMS PARAMETERIZED BY CLIQUE-WIDTH

ALGORITHMIC LOWER BOUNDS FOR PROBLEMS PARAMETERIZED BY CLIQU...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Fomin, Fedor V. Golovach, Petr A. Lokshtanov, Daniel Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway

ISBN: (纸本)9780898717013

Many NP-hard problems can be solved efficiently when the input is restricted to graphs of bounded tree-width or clique-width. In particular, by the celebrated result of Courcelle, every decision problem expressible in monadic second older logic is fixed parameter tractable when parameterized by the tree-width of the Input graph. On the other hand if we restrict ourselves to graphs of clique-width at most t, then there are many natural problems for which the running time of the best known algorithms is of the form n(f(t)), where n is the input length and f is some function It was an open question whether natural problems like GRAPH COLORING, MAX-CUT, EDGE DOMINATING SET, and HAMILTONIAN PATH are fixed parameter tractable when parameterized by the clique-width of the input graph. As a first step toward obtaining lower bounds for clique-width parameterizations, in [SODA 2009], we showed that. unless FPT not equal W[1], there is no algorithm with run time O(g(t) . n(c)), for some function g and a constant c not depending on t, for GRAPH COLORING, EDGE DOMINATING SET and HAMILTONIAN PATH. But the lower bounds obtained in [SODA 2009] are weak when compared to the upper bounds on the time complexity of the known algorithms for these problems when parameterized by the clique-width. In this paper, we obtain the asymptotically tight bounds for MAX-CUT and EDGE DOMINATING SET by showing that both problems cannot be solved in time f(t)n(o(t)), unless Exponential Time Hypothesis (ETH) collapses;and can be solved in time n(O(t)), where f is an arbitrary function of t, on input of size n and clique-width at most t. We obtain our lower bounds by giving non-trivial structure-preserving "linear FPT reductions".

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

The (1+β)-Choice Process and Weighted Balls-into-Bins

The (1+β)-Choice Process and Weighted Balls-into-Bins

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Peres, Yuval Talwar, Kunal Wieder, Udi Microsoft Research Redmond United States Microsoft Research Silicon Valley United States

ISBN: (纸本)9780898717013

Suppose in balls are sequentially thrown into n bins where each ball goes into a random bin. It is well-known that the gap between the load of the most loaded bin and the average is circle minus(root m log n/n), for large m. If each ball goes to the lesser loaded of two random bins, this gap dramatically reduces to circle minus(log log n) independent of in. Consider now the following "(1 + beta)-choice" process for some parameter beta is an element of (0, 1): each ball goes to a random bin with probability (1 - beta) and the lesser loaded of two random bins with probability beta. How does the gap for such a process behave? Suppose that the weight of each ball was drawn from a geometric distribution. How is the gap (now defined in terms of weight) affected? In this work, we develop general techniques for analyzing such balls-into-bins processes. Specifically, we show that for the (1 + beta)-choice process above, the gap is circle minus(log n/beta), irrespective of m. Moreover the gap stays at circle minus(log n/beta) in the weighted case for a large class of weight distributions No non-trivial explicit bounds were previously known in the weighted case, even for the 2-choice paradigm.

关键词： Probability distributions

来源：评论

学校读者我要写书评

暂无评论

The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs

The edge disjoint paths problem in Eulerian graphs and 4-edg...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Kawarabayashi, Ken-ichi Kobayashi, Yusuke Res Org Informat & Syst Natl Inst Informat Chiyoda Ku 2-1-2 Hitotsubashi Tokyo 1018430 Japan Univ Tokyo Tokyo 1138654 Japan

ISBN: (纸本)9780898717013

We consider the following well-known problem, which is called the edge-disjoint paths problem Input: A graph C with a vertices and m edges, k pairs of vertices (s(1), t(1)), (s(2), t(2)), ... , (s(k), t(k)) in G Output : Edge-disjoint paths P-1, P-2, ... , P-lambda in G such that P-1 joins s(1) and t(1) for i = 1,2,..., k. Robertson and Seymour's graph minor project gives use to an O(m(3)) algorithm for this problem for any fixed k, but their proof of the correctness needs the whole Graph Minor project, spanning 23 papers and at least 500 pages proof. We give a faster algorithm and a simpler proof of the correctness for the edge-disjoint paths problem for any fixed k. Our results can be summarized as follows: 1. If an input graph C is either 4-edge-connected or Eulerian, then our algorithm only needs to look for the following three simple reductions (i) Excluding vertices of high degree (n) Excluding <= 3-edge-cuts (iii) Excluding large clique minors. 2. When an input graph C;is either 4-edge-connected or Eulerian, the number of terminals k is allowed to be non-trivially superconstant number, up to k = O((log log log n)(1/2 -) epsilon) for any epsilon > 0. Thus our hidden constant in this case is dramatically smaller than Robertson-Seymoin's. In addition, if an input graph is either 4-edge-connected planar or Eulerian planar, kis allowed to be O((log n)(1/2-epsilon)) for any epsilon > 0. The same thing holds for bounded genus graphs Moreover, if an Input graph is either 4-edge-connected H-minor-free or Eulerian H-minor-free for fixed graph H, k is allowed to be O(log log )(1/2-epsilon)) for any epsilon > 0. 3. We also give our own algorithm for the edge-disjoint paths problem in general graphs. We basically follow Robertson-Seymour's algorithm, but we cut half of the proof of the correctness for their algorithm. In addition, the time complexity of our algorithm is O(n(2)), which is faster than Robertson and Seymour's.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Streaming Algorithms for Extent Problems in High Dimensions

Streaming Algorithms for Extent Problems in High Dimensions

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Agarwal, Pankaj K. Sharathkumar, R. Duke Univ Dept Comp Sci Durham NC 27706 USA

ISBN: (纸本)9780898717013

We develop (single-pass) streaming algorithms for maintaining extent measures of a stream S of n points in R-d. We focus on designing streaming algorithms whose working space is polynomial in d (poly(d)) and sub-linear in n. For the problems of computing diameter, width and minimum enclosing ball of S, we obtain lower bounds on the worst-case approximation ratio of any streaming algorithm that uses poly(d) space. On the positive side, we introduce the notion of blurred ball cover and use it for answering approximate farthest-point queries and maintaining approximate minimum enclosing ball and diameter of S. We describe a streaming algorithm for maintaining a blurred ball cover whose working space is linear in d and independent of n.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

How to meet asynchronously (almost) everywhere

How to meet asynchronously (almost) everywhere

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Czyzowicz, Jurek Labourel, Arnaud Pelc, Andrzej Univ Quebec Outaouais Dept Informat Gatineau PQ J8X 3X7 Canada

ISBN: (纸本)9780898717013

Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment The actual walk of each agent also depends on an asynchronous adversary that, may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent m each segment of its route is continuous, does not leave it and covers all of it Meeting in a graph means that, both agents must be at the same tune in some node or in some point inside an edge of the graph, while meeting in a terrain am means that both agents must be at the saute time in some point of the terrain Does time exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerful adversary? We give deterministic rendezvous algorithms rot agents starting at arbitrary nodes of any anonymous connected graph (finite on infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior While our algorithms work in a very general setting - agents can, indeed. meet. almost, everywhere - we show that, none of the above few limitations imposed on the environment can be removed On the other hand our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary ulterior points of a terrain as above, agents will eventually get at an arbitrarily small positive distance from each other

关键词： Landforms

来源：评论

学校读者我要写书评

暂无评论

Property testing and parameter testing for permutations

Property testing and parameter testing for permutations

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Hoppen, Carlos Kohayakawa, Yoshiharu Moreira, Carlos Gustavo Sampaio, Rudini Menezes Univ Sao Paulo Inst Matemat & Estat Rua Matao 1010 BR-05508090 Sao Paulo Brazil

ISBN: (纸本)9780898717013

There has been peat interest in deciding whether a combinatorial structure satisfies some property, or in estimating the value of some numerical function associated with this combinatorial structure, by considering only a randomly chosen substructure of sufficiently large, but constant size These problems ale called property testing and parameter testing, where a property or parameter is said to be testable if it, can be estimated accurately in this way The algorithmic appeal is evident. as, conditional on sampling, this leads to reliable constant-time randomized estimators Our paper addresses property testing and parameter testing for pet mutations in a subpermutation perspective, more precisely. we investigate permutation propel ties and parameters that, can be well-approximated based on randomly chosen subpermutations of much smaller size In this context, we give a permutation counterpart, of a famous result by Alon and Shapna [6] stating that every hereditary graph property is testable Moreover, we develop a. theory of convergence of permutation sequences, which is used to characterize testable permutation parameters along the lines of the work of Borgs et al [12] in the case of graphs This theory is interesting lot its own sake. as it describes the closure of the set of all permutations as a special class of Lebesgue measurable functions in [0,1](2), which in turn may be used to define a new model of tandom permutations

关键词： Parameter estimation

来源：评论

学校读者我要写书评

暂无评论

Efficient Broadcast on Random Geometric Graphs

Efficient Broadcast on Random Geometric Graphs

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Bradonjic, Milan Elsasser, Robert Friedrich, Tobias Sauerwald, Thomas Stauffer, Alexandre Los Alamos Natl Lab Div Theoret Los Alamos NM 87545 USA

ISBN: (纸本)9780898717013

A Random Geometric Graph (RGG) in two dimensions is constructed by distributing it, nodes independently and uniformly at random in [0, root n](2) and cleating edges between every pan of nodes having Euclidean distance at most r, for sonic prescribed r We analyze the following randomized broadcast algorithm on RGGs At the beginning, only one node horn the largest, connected component of the RGG is informed Then, in each round, each informed node chooses a. neighbor independently and uniformly at random and informs it We prove that with probability 1 - O(n(-1)) this algorithm informs every node in the largest connected component, of an RGG within O(root n/r + log n) rounds This holds for any value of r larger than the critical value for the emergence of a connected component;with Q(n) nodes. In order to wove this result, we show that for any two nodes sufficiently distant from each other in [0, 0712, the length of the shortest path between them in the RGG, when such a path exists, is only a. constant factor larger than the optimum This result has independent, interest and, in particular, gives that the diameter of the largest;connected component of an RGG is circle minus(root n/r), which surprisingly has been an open problem so far

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

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

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：