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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

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

分类表

所选分类

>> <<

限定检索结果

文献类型

2,427 篇 期刊文献
770 篇 会议
24 篇 学位论文
4 册 图书

馆藏范围

3,225 篇 电子文献
0 种 纸本馆藏

日期分布

学科分类号

2,344 篇 工学
- 2,004 篇 计算机科学与技术...
- 476 篇 电气工程
- 378 篇 信息与通信工程
- 337 篇 软件工程
- 76 篇 机械工程
- 74 篇 控制科学与工程
- 69 篇 电子科学与技术（可...
- 29 篇 交通运输工程
- 28 篇 仪器科学与技术
- 11 篇 材料科学与工程（可...
- 8 篇 土木工程
- 6 篇 力学（可授工学、理...
- 6 篇 测绘科学与技术
- 6 篇 石油与天然气工程
- 6 篇 生物工程
1,648 篇 理学
- 1,595 篇 数学
- 28 篇 生物学
- 26 篇 统计学（可授理学、...
- 18 篇 物理学
- 11 篇 系统科学
- 10 篇 化学
- 3 篇 地球物理学
897 篇 管理学
- 889 篇 管理科学与工程(可...
- 236 篇 工商管理
- 5 篇 图书情报与档案管...
243 篇 经济学
- 235 篇 应用经济学
- 7 篇 理论经济学
11 篇 法学
- 8 篇 法学
- 3 篇 社会学
10 篇 医学
- 5 篇 临床医学
8 篇 军事学
4 篇 农学
2 篇 艺术学
1 篇 教育学

主题

3,225 篇 approximation al...
222 篇 scheduling
81 篇 combinatorial op...
73 篇 approximation al...
68 篇 np-hard
68 篇 computational co...
65 篇 np-hardness
64 篇 linear programmi...
61 篇 np-complete
56 篇 optimization
53 篇 facility locatio...
51 篇 traveling salesm...
51 篇 graph algorithm
45 篇 worst-case analy...
45 篇 wireless sensor ...
45 篇 vertex cover
45 篇 makespan
45 篇 network design
43 篇 computational ge...
43 篇 dynamic programm...

机构

52 篇 univ alberta dep...
49 篇 univ texas dalla...
38 篇 shandong jianzhu...
37 篇 iit dept comp sc...
36 篇 nanjing univ sta...
34 篇 tianjin univ tec...
33 篇 city univ hong k...
32 篇 univ new brunswi...
31 篇 shandong normal ...
29 篇 shandong univ sc...
27 篇 renmin univ chin...
24 篇 yunnan univ sch ...
24 篇 chinese acad sci...
23 篇 hangzhou dianzi ...
20 篇 beijing univ tec...
18 篇 zhejiang normal ...
17 篇 beijing univ tec...
17 篇 beijing univ tec...
17 篇 univ wisconsin d...
16 篇 univ texas dalla...

作者

92 篇 xu dachuan
52 篇 du donglei
49 篇 wu weili
47 篇 lin guohui
44 篇 wu chenchen
44 篇 zhang zhao
42 篇 li deying
34 篇 zhang dongmei
30 篇 li min
30 篇 du ding-zhu
29 篇 chen yong
28 篇 zhang an
27 篇 yu wei
25 篇 liu zhaohui
25 篇 wang wei
25 篇 li weidong
25 篇 chen guihai
24 篇 dai haipeng
24 篇 dumitrescu adria...
24 篇 zhang peng

语言

2,996 篇 英文
216 篇 其他
13 篇 中文
3 篇 法文
2 篇 德文

检索条件"主题词=approximation algorithm"

共 3225 条记录，以下是381-390 订阅

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

详细简洁

排序：

A Constant approximation algorithm for Link Scheduling in Arbitrary Networks under Physical Interference Model

A Constant Approximation Algorithm for Link Scheduling in Ar...

引用

2nd ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing

作者： Xu, XiaoHua Tang, ShaoJie IIT Dept Comp Sci Chicago IL 60616 USA

ISBN: (纸本)9781605585239

Link scheduling is crucial in improving the throughput in wireless networks and it has been widely studied under various interference models. In this paper, we study the link scheduling problem under physical interference model where all senders of the links transmit at a given power P and a link can transmit successfully if and only if the Signal-to-Interference-plus-Noise-Ratio (SINR) at the corresponding receiver is at least a certain threshold. The link scheduling problem is to find a maximum -independent set" (MIS) of links, i.e., the maximum number of links that can transmit successfully in one time-slot, given a set of input links. This problem has been shown to be with a constant approximation ratio for arbitrary background noise N >= 0. When each link l has a weight w(l) > 0, we propose a method for weighted MIS with approximation ratio O(min(log maxl is an element of L w(l)/minl is an element of L w(l), log maxl is an element of L parallel to l parallel to/minl is an element of L parallel to l parallel to)), where parallel to l parallel to is the Euclidean length of a link l.

关键词： Link scheduling independent set physical interference model approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Subpolynomial approximation algorithm for Graph Crossing Number in Low-Degree Graphs* 2022

A Subpolynomial Approximation Algorithm for Graph Crossing N...

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Chuzhoy, Julia Tan, Zihan Toyota Technol Inst Chicago Chicago IL 60637 USA Univ Chicago Chicago IL USA

ISBN: (纸本)9781450392648

We consider the classical Minimum Crossing Number problem: given an n-vertex graph G, compute a drawing of G in the plane, while minimizing the number of crossings between the images of its edges. This is a fundamental and extensively studied problem, whose approximability status is widely open. In all currently known approximation algorithms, the approximation factor depends polynomially on. - the maximum vertex degree in G. The best current approximation algorithm achieves an O(n(1/2)-is an element of poly(Delta. logn))-approximation, for a small fixed constant is an element of, while the best negative result is APX-hardness, leaving a large gap in our understanding of this basic problem. In this paper we design a randomized O (2(O((log n)7/8 log log n)) . poly(Delta)) -approximation algorithm for Minimum Crossing Number. This is the first approximation algorithm for the problem that achieves a subpolynomial in n approximation factor (albeit only in graphs whose maximum vertex degree is subpolynomial in n). In order to achieve this approximation factor, we design a new algorithm for a closely related problem called Crossing Number with Rotation System, in which, for every vertex upsilon is an element of V (G), the circular ordering, in which the images of the edges incident to v must enter the image of v in the drawing is fixed as part of input. Combining this result with the recent reduction of [Chuzhoy, Mahabadi, Tan '20] immediately yields the improved approximation algorithm for Minimum Crossing Number.

关键词： Crossing Number approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Constant Factor approximation algorithm for Boxicity of Circular Arc Graphs

A Constant Factor Approximation Algorithm for Boxicity of Ci...

引用

12th International Symposium on algorithms and Data Structures (WADS)

作者： Adiga, Abhijin Babu, Jasine Chandran, L. Sunil Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India

ISBN: (纸本)9783642222993

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in R-k. Equivalently, it is the minimum number of interval graphs on the vertex set V such that the intersection of their edge sets is E. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below O(n(0.5-epsilon))-factor, for any epsilon > 0 in polynomial time unless NP = ZPP. Till date, there is no well known graph class of unbounded boxicity for which even an n(epsilon)-factor approximation algorithm for computing boxicity is known, for any epsilon < 1. In this paper, we study the boxicity problem on Circular Arc graphs intersection graphs of arcs of a circle. We give a (2+1/k)-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where k >= 1 is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is O(mn+n(2)) in both these cases and in O(mn+kn(2)) which is at most O(n(3)) time we also get their corresponding box representations, where a is the number of vertices of the graph and m is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.

关键词： Boxicity Circular Arc Graphs approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Worst-Case Analysis of an approximation algorithm for Single Machine Scheduling Problem 16

Worst-Case Analysis of an Approximation Algorithm for Single...

引用

16th Conference on Computer Science and Intelligence Systems (FedCSIS)

作者： Grigoreva, Natalia St Petersburg State Univ Univ Skay Nab 7-9 St Petersburg Russia

ISBN: (纸本)9788395918384

The problem of minimizing the maximum delivery times while scheduling jobs on the single processor is a classical combinatorial optimization problem. This problem is denoted by 1|r(j), q(j)|C-max, has many applications, and it is NP-hard in strong sense. The goal of this paper is to propose a new 3/2-approximation algorithm, which runs in O(n log n) time. We proved that the bound of 3/2 is tight. To check the efficiency of the algorithm we tested it on random generated problems of up to 5000 jobs.

关键词： single-machine scheduling problem release and delivery times approximation algorithm worst-case performance ratio

来源：评论

学校读者我要写书评

暂无评论

Clever Steady Strategy algorithm: A simple and efficient approximation algorithm for minimum vertex cover problem 13

<i>Clever Steady Strategy Algorithm</i>: A simple and effici...

引用

13th International Conference Frontiers Information Technology (FIT 2015)

作者： Fayaz, Muhammad Arshad, Shakeel Univ Malakand Dept Comp Sci & Informat Technol Kpk Pakistan

ISBN: (纸本)9781509003297

This paper presents a simple and fast polynomial time algorithm, the clever, steady strategy algorithm (CSSA). The proposed algorithm consists of three stages which produces optimal or approximate vertex cover for any unknown un-weighted and undirected G = (V, E). In the first step the degree of each node of the given graph is calculated. In second step the minimum degree node(s) is find and also the adjacent nodes of minimum degree nodes are find. In the third stage the minimum degree node in all adjacent nodes of minimum degree is searched out and is selected as a candidate for MVC and all its edges are deleted. These three steps are processed repeatedly until no edge remains in the graph. The CSSA is tested on small as well as on large benchmark instances. The experimental results and comparative analysis show that the CSSA yields better and fast solution than those approximation algorithms found in literature for solving minimum vertex cover problem.

关键词： Minimum vertex cover (MVC) maximum independent set (MIS) NP-complete problem optimization problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An Improved Constant-Factor approximation algorithm for Planar Visibility Counting Problem 22nd

An Improved Constant-Factor Approximation Algorithm for Plan...

引用

22nd International Computing and Combinatorics Conference (COCOON)

作者： Alipour, Sharareh Ghodsi, Mohammad Jafari, Amir Sharif Univ Technol Tehran Iran Inst Res Fundamental Sci IPM Tehran Iran

ISBN: (纸本)9783319426341;9783319426334

Given a set S of n disjoint line segments in R-2, the visibility counting problem (VCP) is to preprocess S such that the number of segments in S visible from any query point p can be computed quickly. This problem can trivially be solved in logarithmic query time using O(n(4)) preprocessing time and space. Gudmundsson and Morin proposed a 2-approximation algorithm for this problem with a trade-off between the space and the query time. They answer any query in O epsilon(n (1-alpha)) with O epsilon (n(2+2 alpha)) of preprocessing time and space, where alpha is a constant 0 <= alpha <= 1, epsilon > 0 is another constant that can be made arbitrarily small, and O epsilon(f(n)) = O(f( n)n(epsilon)). In this paper, we propose a randomized approximation algorithm for VCP with a tradeoff between the space and the query time. We will show that for an arbitrary constants 0 <= beta <= 2/3 and 0 < delta < 1, the expected preprocessing time, the expected space, and the query time of our algorithm are O( n(4-3 beta) log n), O(n(4-3 beta)), and O(1/delta(3)n(beta) log n), respectively. The algorithm computes the number of visible segments from p, or mp, exactly if m(p) <= (1)/(3)(delta)n(beta) log ***, it computes a ( 1+ delta)-approximation m'(p) with the probability of at least 1- 1/log n, where m(p) <= m'(p) <= ( 1 + delta) m(p).

关键词： Computational geometry Visibility Randomized algorithm approximation algorithm Graph theory

来源：评论

学校读者我要写书评

暂无评论

A 2-approximation algorithm for the Graph 2-Clustering Problem 18th

A 2-Approximation Algorithm for the Graph 2-Clustering Probl...

引用

18th International Conference on Mathematical Optimization Theory and Operations Research (MOTOR)

作者： Il'ev, Victor Il'eva, Svetlana Morshinin, Alexander Dostoevsky Omsk State Univ Omsk Russia RAS Sobolev Inst Math SB Omsk Russia

ISBN: (纸本)9783030226299;9783030226282

We study a version of the graph 2-clustering problem. In this version, for a given undirected graph, one has to find a nearest 2-cluster graph, i.e., the graph on the same vertex set with exactly 2 non-empty connected components each of which is a complete graph. The distance between two graphs is the number of noncoinciding edges. The problem under consideration is NP-hard. In 2004, Bansal, Blum, and Chawla presented a simple polynomial time 3-approximation algorithm for the similar correlation clustering problem in which the number of clusters doesn't exceed 2. In 2008, Coleman, Saunderson, and Wirth presented a 2-approximation algorithm for this problem applying local search to every feasible solution obtained by the 3-approximation algorithm of Bansal, Blum, and Chawla. Unfortunately, the method of proving the performance guarantee of the Coleman, Saunderson, and Wirth's algorithm is not suitable for the graph 2-clustering. Coleman, Saunderson, and Wirth used switching technique that allows to reduce clustering any graph to the equivalent problem whose optimal solution is the complete graph, i.e., the cluster graph consisting of the single cluster. In the graph 2-clustering problem any optimal solution has to consist of exactly 2 clusters, so we need another approximation algorithm and another method of proving a bound on its worst-case behaviour. We present a polynomial time 2-approximation algorithm for the 2-clustering problem on general graphs. In contrast to the proof of Coleman, Saunderson, and Wirth, our proof of the performance guarantee of this algorithm doesn't use switchings.

关键词： Graph clustering approximation algorithm Performance guarantee

来源：评论

学校读者我要写书评

暂无评论

An Improved approximation algorithm for the Ancient Scheduling Problem with Deadlines

An Improved Approximation Algorithm for the Ancient Scheduli...

引用

International Conference on Control, Decision and Information Technologies (CoDIT)

作者： Levner, Eugene Elalouf, Amir Ashkelon Acad Coll Sch Econ Ashqelon Israel Bar Ilan Univ Dept Management Ramat Gan Israel

ISBN: (纸本)9781479967735

The aim of this paper is to develop an improved polynomial-time approximation algorithm belonging to the family of the fully polynomial time approximation schemes (FPTAS), for an ancient scheduling problem with deadlines. The algorithm permits to answer a question posed more than three decades ago in Gens & Levner (1981): "Can an epsilon-approximation algorithm be found for the minimization version of the job-sequencing-with-deadlines problem running with the same complexity as the algorithms for the maximization form of the problem?" The new algorithm provides the positive answer.

关键词： job-sequencing-with-deadlines scheduling problem approximation algorithm FPTAS

来源：评论

学校读者我要写书评

暂无评论

A 3/2-approximation algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs

A 3/2-Approximation Algorithm for Finding Spanning Trees wit...

引用

34th International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Bonsma, Paul Zickfeld, Florian Tech Univ Berlin Inst Math D-10623 Berlin Germany

ISBN: (纸本)9783540922476

We consider the problem of finding a spanning tree that maximizes the number of leaves (MAXLEAF). We provide a 3/2-approximation algorithm for this problem when restricted to cubic graphs, improving on the previous 5/3-approximation for this class. To obtain this approximation we define a graph parameter x(G), and construct a tree with at least (n - x(G) + 4)/3 leaves, and prove that no tree with more than (n - x(G) + 2)/2 leaves exists. In contrast to previous approximation algorithms for MAXLEAF;our algorithm works with connected dominating sets instead of constructing a tree directly. The algorithm also yields a 4/3-approximation for Minimum Connected Dominating Set in cubic graphs.

关键词： approximation algorithm maximum leaf connected dominating set cubic graph

来源：评论

学校读者我要写书评

暂无评论

Improved Inapproximability Gap and approximation algorithm for Scaffold Filling to Maximize Increased Duo-Preservations 1

引用

20th International Symposium on Bioinformatics Research and Applications (ISBRA)

作者： Wu, Jinting Jiang, Haitao Shandong Univ Sch Comp Sci & Technol Qingdao Shandong Peoples R China

ISBN: (数字)9789819750870

ISBN: (纸本)9789819750863;9789819750870

Scaffold filling is a critical step in DNA assembly. In the scaffold filling problem, we are given a reference (complete) genome, and a scaffold composed of contigs which are matched to fix positions on the reference genome, as well as some unmatched fragments, the purpose is to insert the unmatched fragments between the contigs in the scaffold, such that the resulting genome is similar to the reference genome. Let M be a one-to-one matching between common letters of the scaffold and the reference genome. A duo-preservation is an ordered pair of consecutive letters in the scaffold, which are matched to two consecutive letters in the reference genome based on M. The problem of scaffold filling to maximize increased duo-preservations is described as: given an incomplete scaffold with some fragments missing and a reference genome, inserting the missing fragments back into the incomplete scaffold to maximize the number of increased duo-preservations between the filled scaffold and the reference genome. In [19], this problem was shown to be MAX-SNP-complete and can not be approximated within 16263/16262. In this paper, we firstly improve the inapproximability gap to 2363/2362, then we devise a new approximation algorithm with an approximation factor of 3/2 + epsilon by a local search method. The running time of the approximation algorithm is O(n(O(1/epsilon))), where epsilon is an arbitrary small constant. Finally, we apply our algorithm to simulated genomic data, yielding the average approximation factors of 1.034 for s = 1 and 1.030 for s = 2, where s denotes the range of local search, indicating the maximum number of elements substituted in the current solution per iteration. The experimental findings show that our algorithm's approximation factor primarily reflects a theoretical worst-case. However, practical datasets rarely encounter such extremes cases. Therefore, our approximation algorithm shows exceptional performance in real-world datasets compared with the the

关键词： Scaffold Filling Inapproximability Gap approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共323页 << < 35 36 37 38 39 40 41 42 43 44 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：