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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

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

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

详细简洁

排序：

Genus and the geometry of the cut graph

Genus and the geometry of the cut graph

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Lee, James R. Sidiropoulos, Anastasios Univ Washington Seattle WA 98195 USA

ISBN: (纸本)9780898717013

We study the quantitative geometry of graphs in terms of their genus, using the structure of certain "cut graphs," i.e. subgraphs whose removal leaves a planar graph In particular, we give optimal bounds for random partitioning schemes, as well as various types of embeddings. Using these geometric primitives, we present exponentially improved dependence on genus for a number of problems like approximate max-flow/min-cut theorems, approximations for uniform and non-uniform Sparsest Cut, treewidth approximation, Laplacian eigenvalue bounds, and Lipschitz extension theorems and related metric labeling problems. We list here a sample of these improvements. All the following statements refer to graphs of genus g, unless otherwise noted. We show that such graphs admit an O(log g)-approximate multi-commodity max-fiow/min-cut theorem for the case of uniform demands. This bound is optimal, and improves over the previous bound of O(g) [KPR93, FT03]. For general demands, we show that, the worst possible gap is O(log g + C-P), where C-P is the gap for planar graphs. This dependence is optimal, and already yields a bound of O(log g + root log n), improving over the previous bound of O(root g log n) [KLMN04]. We give an O(root log g)-approximation for the uniform Sparsest Cut, balanced vertex separator, amid treewidth problems, improving over the previous bound of O(g) [FHL05]. If a graph G has genus g and maximum degree D, we show that the kth Laplacian eigenvalue of G is (log g)(2) . O(kgD/n), improving over the previous bound of g(2) . O(kgD/n) [KLPT09]. There is a lower bound of Omega(kgD/n), making this result almost tight. We show that if (X, d) is the shortest-path metric on a graph of genus g and S subset of X, then every L-Lipschitz map f : S --> Z into a Banach space Z admits an O(L log g)-Lipschitz extension f : X --> Z. This improves over the previous bound of O(Lg) [LN05], and compares to a lower bound of Omega(L root log g). In a related way, we show that there is a

关键词： Banach spaces

来源：评论

学校读者我要写书评

暂无评论

Approximability of Robust Network Design

Approximability of Robust Network Design

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Olver, Neil Shepherd, F. Bruce McGill Univ Dept Math & Stat Montreal PQ H3A 2T5 Canada

ISBN: (纸本)9780898717013

We consider robust network design problems where the set of feasible demands may be given by an arbitrary polytope or convex body more generally This model, introduced by Ben-Ameur and Kerivin [2], generalizes the well studied virtual private network (VPN) problem. Most research in this area has focused on finding constant factor approximations for specific polytope of demands, such as the class of hose matrices used in the definition of VPN As pointed out in (41, however, the general problem was only known to be APX-hard (based on a reduction from the Steiner tree problem). We show that the general robust design is hard to approximate to within polylogarithmic factors. We establish this by showing a general reduction of buy-at-bulk network design to the robust network design problem. In the second part of the paper, we introduce a natural generalization of the VPN problem. In this model, the set of feasible demands is determined by a tree with edge capacities;a demand matrix is feasible if it can be routed on the tree. We give a constant factor approximation algorithm for this problem that achieves factor 8 in general;and 2 for the case where the tree has unit capacities.

关键词： Virtual private networks

来源：评论

学校读者我要写书评

暂无评论

Utilitarian Mechanism Design for Multi-Objective Optimization

Utilitarian Mechanism Design for Multi-Objective Optimizatio...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Grandoni, Fabrizio Krysta, Piotr Leonardi, Stefano Ventre, Carmine Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod Via Politecn 1 I-00133 Rome Italy Univ Liverpool Dipartimento Informat Liverpool L69 3BX Merseyside England Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00185 Rome Italy Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

ISBN: (纸本)9780898717013

In a classic optimization problem the complete input data is known to the algorithm. This assumption may not be true anymore in optimization problems motivated by the Internet where part of the input data is private knowledge of independent selfish agents. The goal of algorithmic mechanism design is to provide (in polynomial time) a solution to the optimization problem and a set of incentives for the agents such that disclosing the input data is a dominant strategy for the agents. In case of NP-hard problems, the solution computed should also be a good approximation of the optimum. In this paper we focus on mechanism design for multi-objective optimization problems, where we are given the main objective function, and a set of secondary objectives which are modeled via budget constraints. Multi-objective optimization is a natural setting for mechanism design as many economical choices ask for a compromise between different, partially conflicting, goals. Our main contribution is showing that two of the main tools for the design of approximation algorithms for multi-objective optimization problems, namely approximate Pareto curves and Lagrangian relaxation, can lead to truthful approximation schemes. By exploiting the method of approximate Pareto curves, we devise truthful FPTASs for multi-objective optimization problems whose exact version admits a pseudo-polynomial-time algorithm, as for instance the multi-budgeted versions of minimum spanning tree, shortest path, maximum (perfect) matching, and matroid intersection. Our technique applies also to multi-dimensional knapsack and multi-unit combinatorial auctions Our FPTASs compute a (1 + epsilon)-pproximate solution violating each budget constraint by a factor (1 + epsilon). For a relevant sub-class of the mentioned problems we also present a PTAS (not violating any constraint), which combines the approach above with a novel monotone way to guess the heaviest elements in the optimum solution. Finally, we present a univ

关键词： Multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

Bounding Variance and Expectation of Longest Path Lengths in DAGs

Bounding Variance and Expectation of Longest Path Lengths in...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Edmonds, Jeff Chakraborty, Supratik York Univ N York ON M3J 1P3 Canada IIT Bombay Maharashtra India

ISBN: (纸本)9780898717013

We consider the problem of computing bounds on the variance mid expectation of the longest path length in a DAG from knowledge of variance and expectation of edge lengths. We focus primarily on the case where all edge lengths ale non-negative and the DAG has a single source and sink node. We present analytic bounds for various simple DAG structures, and present a new algorithm to compute bounds for more general DAG;structures Our algorithm is motivated by an analogy with balance of forces in a network of "strange" swings.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Flow-Cut Gaps for Integer and Fractional Multiflows

Flow-Cut Gaps for Integer and Fractional Multiflows

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Chekuri, Chandra Shepherd, F. Bruce Weibel, Christophe Univ Illinois Dept Comp Sci 201 N Goodwin Ave Urbana IL 61801 USA McGill Univ Dept Math & Stat Montreal PQ H3A 2T5 Canada

ISBN: (纸本)9780898717013

Consider a routing problem instance consisting of a demand graph H = (V, E(H)) and a supply graph G = (V, E(C)) If the pair obeys the cut condition, then the flaw-cut gap for this instance is the minimum value C such that there exists a feasible multi flow for H if each edge of C is given capacity C It is well-known that the flow-cut gap may be greater than I even in the case where G is the (series-parallel) graph K-2,K-3 In this paper we are primarily interested in the "inteeer" flow-cut gap What is the minimum value C such that there exists a feasible integer valued multiflow for If if each edge of G is oven capacity C-9 We formulate a conjecture that states that the integer flow-cut gap is quantitatively related to the fractional flow-cut gap In particular this strengthens the well-known conjecture that the flow-cut gap in planar and minor-free graphs is O(1) [12] to suggest that the integer flow-cut gap is O(1). We give several technical tools and results on non-trivial special classes of graphs to give evidence for the conjecture and further explore the "primal" method for understanding flow-cut gaps, this is in contrast to and orthogonal to the highly successful metric embeddings approach Our results include the following Let G be obtained by series-parallel operations starting from an edge st, and consider orienting all edges in G in the direction from to I A demand is compliant if its endpoints are joined by a directed path in the resulting oriented graph We show that if the cut condition holds for a compliant instance and G + H is Eulenan, then an integral routing of H exists This result includes, as a special case, routine on a ring, but is not a special case of the Okamura-Seymour theorem Using the above result, we show that the integer flow-cut gap in series-parallel graphs is 5. The integer flow-cut gap in k-Outerplanar graphs is c(O(lambda)) for some fixed constant c. A simple proof that the flow-cut gap is O(log k*) where k is the size of a node-cover

关键词： Flow graphs

来源：评论

学校读者我要写书评

暂无评论

Improved Approximation Algorithms for the Minimum Latency Problem via Prize-Collecting Strolls

Improved Approximation Algorithms for the Minimum Latency Pr...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Archer, Aaron Blasiak, Anna AT&T Labs Res 180 Pk Ave Florham Pk NJ 07932 USA Cornell Univ Dept Comp Sci Ithaca NY 14853 USA

ISBN: (纸本)9780898717013

The minimum latency problem (MO) is a well-studied variant of the traveling salesman problem (TSP). In the MLR the server's goal is to minimize the average latency that the clients experience prior to being served, rather than the total latency experienced by the server (as in the TSP). The MLP sometimes goes by other names, such as the traveling repairman problem, or the deliveryman problem. Unlike most combinatorial optimization problems, the MLP is NP-hard even on trees (Sitters, 2001). Our main result is an improved approximation algorithm for the MLP on trees, upon which we build improved approximation algorithms for a much wider class of graphs The MLP on trees is interesting for several reasons. First. many of the aspects that make the problem difficult on general graphs are already present in the tree case. Second, all existing approximation algorithms for general graphs are built on approximation algorithms for the tree case. Third, there has been no improvement for the tree case since the 3.59-approximation of Goemans and Kleinberg, first introduced 14 years ago in 1996. Fourth, in the intervening period, the best ratio for general metrics has been improved to match the 3.59 for trees (Chaudhuri et al, 2003). In this paper, we improve the approximation ratio for trees to 3.03. In fact, our 3.03-approximation algorithm works for any class of graphs in which the related prize-collecting stroll (PCS) problem is solvable in polynomial time, such as graphs of constant treewidth. More generally, for any class or graphs that admit a Lagrangian-preserving beta-approximation algorithm, we can use this algorithm as a black box to achieve a 3 03 beta-approximation for the MLP. Sadly, this does not immediately improve the ratio of 3 59 for general graphs, because the current best value of beta for that case is 2. One interesting piece of our analysis is the solution of an infinite-dimensional linear program, used to analyze a finite-dimensional factor-revealing linear

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Algorithms and Complexity for Periodic Real-Time Scheduling

Algorithms and Complexity for Periodic Real-Time Scheduling

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Bonifaci, Vincenzo Chan, Ho-Leung Marchetti-Spaccamela, Alberto Megow, Nicole Max Planck Inst Informat Saarbrucken Germany Univ Hong Kong Hong Kong Peoples R China Sapienza Univ Rome Rome Italy

ISBN: (纸本)9780898717013

We investigate the preemptive scheduling of pet iodic tasks with lend deadlines We show that, even in the umprocessor case, no polynomial tune algorithm can test the feasibility of a task system within a constant speedup bound, unless P = NP This result contrasts with recent minks for sporadic task systems For two special cases, synchronous task systems and systems with a constant number of different task types, we provide the first polynomial time constant-speedup feasibility tests for multiprocessor platforms. Furthermore, we show that the problem of testing feasibility is coNP-hard for synchronous multiprocessor task systems The complexity of some of these problems has been open for a. long tune We also propose a profit maximization variant of the feasibility problem, where every task has a non-negative profit, and the goal is to find a subset of tasks that can be scheduled feasibly with maximum profit We give the first constant-speed, constant-approximation algorithm for the case of synchronous task systems, together with related hardness results.

关键词： Profitability

来源：评论

学校读者我要写书评

暂无评论

Testing additive integrality gaps

Testing additive integrality gaps

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Eisenbrand, Friedrich Haehnle, Nicolai Palvoelgyi, Doemoetoer Shmonin, Gennady Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland

ISBN: (纸本)9780898717013

We consider the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant This can be viewed as a generalization of the integer rounding property, which can be tested in polynomial time if the number of constraints is fixed. It turns out that this generalization is NP-hard even if the number of constraints is fixed. However, if, in addition, the objective is the all-one vector, then one can test in polynomial time whether the additive gap is bounded by a constant.

关键词： Integer programming

来源：评论

学校读者我要写书评

暂无评论

EDF-schedulability of synchronous periodic task systems is coNP-hard

EDF-schedulability of synchronous periodic task systems is c...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Eisenbrand, Friedrich Rothvoss, Thomas Ecole Polytech Fed Lausanne Inst Math CH-1015 Lausanne Switzerland

ISBN: (纸本)9780898717013

In the synchronous periodic task model, a set tau(1), ..., tau(n) of tasks is given, each releasing jobs of running time c(iota) with relative deadline d(iota), at each integer multiple of the period p. It is a classical result that Earliest Deadline First (EDF) is an optimal preemptive uni-processor scheduling policy. For constrained deadlines, i.e. d(iota) <= p(iota), the EDF-schedule is feasible if and only if [GRAPHICS] Though an enormous amount of literature deals with this topic, the complexity status of this test has remained unknown. We prove that testing EDF-schedulability of such a task system is (weakly) coNP-hard. This solves Problem 2 from the survey "Open Problems in Real-time Scheduling" by Baruah & Pruhs. The hardness result is achieved by applying recent results on inapproximability of Diophantine approximation.

关键词： Scheduling

来源：评论

学校读者我要写书评

暂无评论

A QPTAS for TSP with Fat, Weakly Disjoint Neighborhoods in Doubling Metrics

A QPTAS for TSP with Fat, Weakly Disjoint Neighborhoods in D...

引用

21st Annual ACM/SIAM Symposium on Discrete Algorithms

作者： Chan, T-H. Hubert Elbassioni, Khaled Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Max Planck Inst Informat D-66123 Saarbrucken Germany

ISBN: (纸本)9780898717013

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics The goal is to find a shortest, tour that visits each of a collection of n subsets (regions or neighborhoods) in the underlying metric space We give a QPTAS when the legions are what we call a-fat weakly disjoint Tins notion combines the existing notions of diameter variation, fatness and disjointness for geometric objects and generalizes these notions to any arbitrary metric space Intuitively, the regions can be grouped into a bounded number of types, where in each type, the regions have similar upper bounds for their diameters, and each such region can designate a. point such that, these points are far away from one another Our result generalizes the PTAS for TSPN on the Euclidean plane by Mitchell [27] and the QPTAS for TSP on doubling metrics by Talwar [30] We also observe dial our techniques directly extend to a QPTAS for the Group Steiner Tree Problem on doubling metrics, with the same assumption on the groups

关键词： Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共20页 << < 9 10 11 12 13 14 15 16 17 18 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：