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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

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

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

详细简洁

排序：

A deterministic truthful PTAS for scheduling related machines

A deterministic truthful PTAS for scheduling related machine...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Christodoulou, George Kovacs, Annamaria Max Planck Inst Informat Saarbrucken Germany Goethe Univ Dept Informat Frankfurt Germany

ISBN: (纸本)9780898717013

Scheduling on related machines (Q parallel to C-max) is one of the most important problems in the field of Algorithmic Mechanism Design. Each machine is controlled by a selfish agent and her valuation can be expressed via a single parameter, her speed Archer and Tardos [4] showed that, in contrast to other similar problems, a (non-polynomial) allocation that minimizes the makespan can be truthfully implemented On the other hand, if we leave out the game-theoretic Issues, the complexity of the problem has been completely settled the problem is strongly NP-hard. while there exists a PTAS [9, 8]. This problem is the most well-studied in single-parameter Algorithmic Mechanism Design. It gives an excellent ground to explore the boundary between truthfulness and efficient computation. Since the work of Archer and Tardos, quite a lot of deterministic and randomized mechanisms have been suggested Recently, a breakthrough result [7] showed that a randomized, truthful-In-expectation PTAS exists. On the other hand, for the deterministic case, the best known approximation factor is 2.8 [10, 11]. It has been a major open question whether there exists a deterministic truthful PTAS, or whether truthfulness has an essential, negative impact on the computational complexity of the problem. In this paper we give a definitive answer to this important question by providing a truthful deterministic PTAS.

关键词： Scheduling

来源：评论

学校读者我要写书评

暂无评论

An (almost) Linear Time Algorithm For Odd Cycles Transversal

An (almost) Linear Time Algorithm For Odd Cycles Transversal

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Kawarabayashi, Ken-ichi Reed, Bruce Res Org Informat & Syst Natl Inst Informat Chiyoda Ku 2-1-2 Hitotsubashi Tokyo 1018430 Japan McGill Univ Canada Res Chair Graph Theory Montreal PQ H3A 2T5 Canada CNRS INRIA Lab I3S Sophia Antipolis France

ISBN: (纸本)9780898717013

We consider the following problem, which is called the odd cycles transversal problem Input. A graph G and an integer k. Output . A vertex set X is an element of V(G) with vertical bar X vertical bar <= k such that G - X is bipartite. We present an O(m alpha(m, n)) time algorithm for this problem for any fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function a(in,n) is the inverse of the Ackermann function (see by Tarjan [38]) This improves the time complexity of the algorithm by Reed, Smith and Vetta [29] who gave an O(nm) time algorithm for this problem. Our algorithm also implies the edge version of the problem, i e, there is an edge set X' is an element of E(G) such that G - X' is bipartite. Using this algorithm and the recent result in [16], we give an O(m alpha(m, n) + n log n) algorithm for the following problem for any fixed k Input: A graph G and an integer k. Output . Determine whether or not there is a half-integral k disjoint odd cycles packing, i.e, k odd cycles C-1,...,C-k in G such that each vertex is on at most two of these odd cycles. This improves the time complexity of the algorithm by Reed, Smith and Vetta [29] who gave an O(n(3)) time algorithm for this problem. We also give a much simpler and much shorter proof for the following result by Reed [28] The Erdos-Posa property holds for the half-integral disjoint odd cycles packing problem. I.e. either G has a half-integral k disjoint odd cycles packing or G has a vertex set X of order at most f(k) such that G - X is bipartite for some function f of k. Note that the Erdos-Posa property does not hold for odd cycles in general.

关键词： Nearly linear time algorithm half-integral disjoint odd cycles packing Erdos-Posa property

来源：评论

学校读者我要写书评

暂无评论

An Improved Construction of Progression-Free Sets

An Improved Construction of Progression-Free Sets

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Elkin, Michael Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

ISBN: (纸本)9780898717013

The problem of constructing dense subsets S of {1,2, ..., n} that contain no three-term arithmetic progression was introduced by Erdos and Turan in 1936. They have presented a construction with |S| = Omega(n(log3) (2)) elements Their construction was improved by Salem and Spencer, and further improved by Belli end in 1946. The lower bound of Behrend is |S| = Omega(n/2(2 root 2) root log(2) n log(1/4) n) Since then the problem became one of the most central, most fundamental, and most intensively studied problems in additive number theory Nevertheless: no improvement, of the lower bound of Behrend has been reported since 1946 In this paper we present. a construction that improves the result of Behrendt by a factor of Theta(log n), and shows that;|S| = Omega(n/2(2 root 2) root log(2) n .log(1/4) n) In particular, our result implies that the construction of Behrend is not optimal Our construction and proof are elementary and self-contained Also the construction can be implemented by an efficient algorithm Behrend's construction has numerous applications in Theoretical Computer Science In particular, it is used for fast, matrix multiplication, for property testing, and in the area of communication complexity Plugging in our construction instead of Behrend's construction Hi the matrix multiplication algorithm of Coppersmith and Winograd improves the state-of-the-m upper bound On the complexity of the matrix multiplication by a factor of log(v) n for some fixed constant v > 0 We also present. an application of our technique in Computational Geometry

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

Reconstructing approximate phylogenetic trees from quartet samples

Reconstructing approximate phylogenetic trees from quartet s...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Snir, Sagi Yuster, Raphael Univ Haifa Dept Evolutionary Biol IL-31905 Haifa Israel Univ Haifa Dept Math & Comp Sci IL-31905 Haifa Israel

ISBN: (纸本)9780898717013

The reconstruction of evolutionary trees (also known as phylogenies) is central to many problems in Biology Accurate phylogenetic reconstruction methods are currently limited to a maximum of few dozens of species Therefore, in order to construct a tree over larger sets of species, a method capable of inferring accurately trees over small, overlapping sets, and subsequently merging these sets into a tree over the complete set, is required. A quartet tree is the smallest informative piece of information and quartet based methods are based on combining quartet trees into a big tree. However, even this case is NP-hard, and even when the set of quartet trees is compatible (agree on a certain tree). The general problem of approximating quartets, or maximum quartet consistency (MQC), even for compatible inputs, is open for nearly twenty years Despite its importance, the only rigorous results for approximating quartets are the naive 1/3 approximation that applies to the general case and a PTAS when the input is the complete set of all ((n)(4)) possible quartets Even when it is possible to determine the correct quartet induced by every four taxa, the time needed to generate the complete set of all quartets may be impractical. A faster approach is to sample at random just in << ((n)(4)) quartets, and provide this sample as an input. In this work we present the first approximation algorithm whose guaranteed approximation is strictly better than 1/3 when the input is any random sample of in compatible quartets. The approximation ratio we obtain is 0.425 for general m, and 0.468 when in = (omega) over tilde (n(2)). An important ingredient in our algorithm involves solving a weighted Max-Cut in a certain graph induced by the set of input quartets. We also show an extension of the PTAS algorithm to handle dense, rather than complete, inputs.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Data Structures for Range Minimum Queries in Multidimensional Arrays

Data Structures for Range Minimum Queries in Multidimensiona...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Yuan, Hao Atallah, Mikhail J. Purdue Univ W Lafayette IN 47907 USA

ISBN: (纸本)9780898717013

Given a d-dimensional array A with N entries, the Range Minimum Query (RMQ) asks for the minimum element within a contiguous subarray of A The 1D RMQ problem has been studied intensively because of its relevance to the Nearest Common Ancestor problem and its important use in stringology. If constant-tune query answering is required, linear time and space preprocessing algorithms were known for the ID case, but not for the higher dimensional cases In this paper, we give the first linear-time preprocessing algorithm for arrays with fixed dimension, such that any range minimum query can be answered in constant time

关键词： String searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Energy Efficient Scheduling via Partial Shutdown

Energy Efficient Scheduling via Partial Shutdown

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Khuller, Samir Li, Jian Saha, Barna Univ Maryland Dept Comp Sci College Pk MD 20742 USA

ISBN: (纸本)9780898717013

Motivated by issues of saving energy in data centers we define a collection of new problems referred to as "machine activation" problems The central framework we introduce considers a collection of in machines (unrelated or related) with each machine i having an activation cost of a(i) There is also a collection of n jobs that need to be performed, and p(i,j) is the processing tune of job 3 on machine i Standard scheduling models assume that the set of machines is fixed and all machines are available However, in our setting, we assume that there is an activation cost budget of A we would like to select a subset S of the machines to activate with total cost a(S) <= A and find a schedule for the n jobs on the machines m S minimizing the makespan (or any other metric) We consider both the unrelated machines setting. as well as the setting of scheduling uniformly elated parallel machines: whole machine i has activation cost a, and speed s(i), and the processing tune of job 3 on machine i is p(i,j) = p(j)/s(i), s(i), where p(j) is the processing requirement of job j. For the general unrelated machine activation problem, our main results are that if there is a schedule with makespan T and activation cost A then we can obtain a schedule with makespan (2+epsilon)T and activation cost 2(1+1/c)(In n/OPT+1)A, lot any epsilon > 0. We also consider assignment costs for jobs as in the generalized assignment problem, and using our framework, provide algorithms that minimize the machine activation and the assignment cost simultaneously In addition, we present, a greedy algorithm which only works lot the basic version and yields a makespan of 2T and an activation cost;A(1 + Inn) For the uniformly related parallel machine scheduling problem, we develop a polynomial tune approximation scheme that outputs a schedule with the property that the activation cost of the subset of machines is at most,A and the makespan is at most (1 + epsilon)T for any e > 0 For the special case of m identic

关键词： Chemical activation

来源：评论

学校读者我要写书评

暂无评论

Regular Expression Matching with Multi-Strings and Intervals

Regular Expression Matching with Multi-Strings and Intervals

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Bille, Philip Thorup, Mikkel

ISBN: (纸本)9780898717013

Regular expression matching is a key task (and often computational bottleneck) in a variety of software tools and applications. For instance, the standard grep and sed utilities, scripting languages such as perl. Internet traffic analysis, XML querying, and protein searching. The basic definition of a regular expression is that we combine characters with union, concatenation, and kleene star operators. The length in is proportional to the number of characters. However, often the initial operation is to concatenate characters in fairly long strings, e.g., if we search for certain combinations of words in a firewall. As a result, the number k of strings in the regular expression is significantly smaller than in Our main result is a new algorithm that essentially replaces in with k in the complexity bounds for regular expression matching. More precisely, after an 0(m log k) time and 0(m) space preprocessing of the expression, we can match it in a string presented as a stream of characters in O(k log w/w + log k) time per character, where w is the number of bits in a memory word. For large w, this corresponds to the previous best bound of O(m log w/w + log m). Prior to this work no O(k) bound per character was known. We further extend our solution to efficiently handle character class interval operators C{x, y}. Here, C is a set of characters and C{x, y}, where x and y are integers such that 0 <= x <= y, represents a string of length between x and y from C. These character class intervals generalize variable length gaps which are frequently used for pattern matching in computational biology applications.

关键词： Pattern matching

来源：评论

学校读者我要写书评

暂无评论

Road Network Reconstruction for Organizing Paths

Road Network Reconstruction for Organizing Paths

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Chen, Daniel Guibas, Leonidas J. Hershberger, John Sun, Jian Stanford Univ Dept Comp Sci Palo Alto CA 94305 USA Mentor Graph Corp Wilsonville OR 97070 USA

ISBN: (纸本)9780898717013

We consider the problem of reconstructing a road network from a collection of path traces and provide guarantees on the accuracy of the reconstruction under reasonable assumptions. Our algorithm can be used to process a collection of polygonal paths in the plane so that shared structures (sub paths) among the paths in the collection can be discovered and the collection can be organized to allow efficient path similarity queries against new query paths on the same road network. This is a timely problem, as GPS and other location traces of both people and vehicles are becoming available on a large scale and there is a real need to create appropriate data structures and data bases for such data.

关键词： Roads and streets

来源：评论

学校读者我要写书评

暂无评论

Applications of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures

Applications of Forbidden 0-1 Matrices to Search Tree and Pa...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Pettie, Seth Univ Michigan Ann Arbor MI 48109 USA

ISBN: (纸本)9780898717013

In this paper we improve, reprove, and simplify several theorems on the performance of data structures based on path compression and search trees. We apply a technique very familiar to computational geometers but still foreign to many researchers in (non-geometric) algorithms and data structures, namely, to bound the complexity of an object via its forbidden substructures To analyze an algorithm or data structure in the forbidden substructure framework one proceeds in three discrete steps. First, one transcribes the behavior of the algorithm as sonic combinatorial object M;for example, M may be a graph, sequence, permutation, matrix, set system, or tree. (The size of M should ideally be linear in the running time.) Second, one shows that M excludes some forbidden substructure P, and third, one bounds the size of any object avoiding this substructure. The power of this framework derives from the fact that M lies in a more pristine environment and that upper bounds on the size of a P-free object M may be reused in different contexts. Among our results, we present the first asymptotically sharp bound on the length of arbitrary path compressions on arbitrary trees, improving analyses of Tarjan [35] and Seidel and Sharir [31]. We reprove the linear bound on postordered path compressions, due to Lucas [23] and Loebel and Nesetril [22], the linear bound on deque-ordered path compressions, clue to Buchsbaum, Sundar, and Tarjan [5], and the sequential access theorem for splay trees, originally due to Tarjan [38]. We disprove a conjecture of Aronov et al. [3] related to the efficiency of their data structure for half-plane proximity queries and provide a significantly cleaner analysis of their structure. With the exception of the sequential access theorem, all our proofs are exceptionally simple. Notably absent are calculations of any kind.

关键词： Data structures

来源：评论

学校读者我要写书评

暂无评论

Basis Reduction and the Complexity of Branch-and-Bound

Basis Reduction and the Complexity of Branch-and-Bound

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Pataki, Gabor Tural, Mustafa Wong, Erick B. Univ N Carolina Dept Stat & Operat Res Chapel Hill NC 27515 USA Univ Minnesota Inst Math & Applicat Minneapolis MN 55455 USA Univ British Columbia Dept Math Vancouver BC V5Z 1M9 Canada

ISBN: (纸本)9780898717013

The classical branch-and-bound algorithm for the integer feasibility problem [GRAPHICS] has exponential worst case complexity. We prove that, it. is surprisingly efficient on reformulations of (01), in which the columns of the constraint, matrix are short and near orthogonal, i e, a reduced basis of the generated lattice. when the entries of A ale from {1, ,M} for a large enough M, branch-and-bound solves almost all reformulated instances at the root. node For all A matrices we prove an upper bound on the width of the reformulations along the last. unit vector Out results generalize the results of Furst, and kannan on the solvability of subset sum problems. also, we wove them via branch-and-bound, an algorithm traditionally considered inefficient from the theoretical point, of view We use two main tools. first, we find a bound on the size of the branch-and-bound tree based on the norms of the Gram-Schmidt vectors of the constiant. matrix. Second, building on the ideas of Furst and Kannan, we bound the number of integral matrices for which the shortest nonzero vectors of certain lattices ale long We explore practical aspects of these results We compute numerical values of M which guarantee that 90 and 99 percent of the reformulated problems solve at the root these turn out, to be surprisingly small when the problem size is model ate We also confirm with a computational study that random integer programs become easier, as the coefficients grow.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共20页 << < 6 7 8 9 10 11 12 13 14 15 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：