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

IEEE International Conference on Communications (ICC 2004)

作者： Amaldi, E Capone, A Malucelli, F Villa, G Politecn Milan DEI I-20133 Milan Italy

ISBN: (纸本)0780385330

Beam forming techniques of adaptive antenna arrays (smart antennas) allow to reduce the mutual interference of simultaneous transmission in wireless access systems exploiting angular separation of user terminals. At the radio resource management layer the information on the arrival direction of signals can be taken into account by the scheduling algorithm so that transmissions of too close user terminals can be scheduled in different time-slots, while transmissions of users with an enough angular separation can be simultaneous. In other words, time diversity is exploited by the scheduling algorithm when spatial diversity is not sufficient to obtain good quality transmissions. In this paper we propose a novel approach to the problem of packet scheduling with smart antennas using mathematical programming. Based on a simplified system model we formulate two combinatorial optimization problems. In the first problem we have to select a subset of users which can be simultaneously served in a given time slot so as to maximize the number or the total priority of the users served. An arc-circular model is proposed together with an exact polynomial-time algorithm which searches for a path of maximum total weight in an appropriate graph. In the second problem users must be partitioned into non-interfering subsets so as to minimize the number of time slots needed to transmit all the given packets. For both problems heuristics have been devised in order to obtain approximate solutions in the short time available for packet scheduling in real systems.

关键词： packet scheduling smart antennas SDMA cross-layer optimization radio resource management exact algorithms heuristics

来源：评论

学校读者我要写书评

暂无评论

Random knapsack in expected polynomial time

Random knapsack in expected polynomial time

引用

35th Annual ACM Symposium on Theory of Computing

作者： Beier, R Vöcking, B Max Planck Inst Informat D-66123 Saarbrucken Germany Univ Dortmund Fachbereich Informat D-4600 Dortmund Germany

We present the first average-case analysis proving a polynomial upper bound on the expected running time of an exact algorithm for the 0/1 knapsack problem. In particular, we prove for various input distributions, that the number of Pareto-optimal knapsack fillings is polynomially bounded in the number of available items. An algorithm by Nemhauser and Ullmann can enumerate these solutions very efficiently so that a polynomial upper bound on the number of Pareto-optimal solutions implies an algorithm with expected polynomial running time. The random input model underlying our analysis is quite general and not restricted to a particular input distribution. We assume adversarial weights and randomly drawn profits (or vice versa). Our analysis covers general probability distributions with finite mean and, in its most general form, can even handle different probability distributions for the profits of different items. This feature enables us to study the effects of correlations between profits and weights. Our analysis confirms and explains practical studies showing that so-called strongly correlated instances are harder to solve than weakly correlated ones. (C) 2004 Elsevier Inc. All rights reserved.

关键词： knapsack problem exact algorithms average case analysis

来源：评论

学校读者我要写书评

暂无评论

Faster exact algorithms for hard problems: A parameterized point of view

引用

DISCRETE MATHEMATICS 2001年第1-3期229卷 3-27页

作者： Alber, J Gramm, J Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

Recent times have seen quite some progress in the development of 'efficient' exponential-time algorithms for NP-hard problems. These results are also tightly related to the so-called theory of fixed parameter tractability. In this incomplete, personally biased survey, we reflect on some recent developments and prospects in the field of fixed parameter algorithms. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： NP-complete problems parameterized complexity fixed parameter tractability W-hierarchy exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Fixed-parameter algorithms for CLOSEST STRING and related problems

引用

ALGORITHMICA 2003年第1期37卷 25-42页

作者： Gramm, J Niedermeier, R Rossmanith, P Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany Rhein Westfal TH Aachen Lehrgebiet Theoret Informat D-52056 Aachen Germany

CLOSEST STRING is one of the core problems in the field of consensus word analysis with particular importance for computational biology. Given k strings of the same length and a nonnegative integer d, find a "center string" s such that none of the given strings has the Hamming distance greater than d from s. CLOSEST STRING is NP-complete. In biological applications, however, d is usually,very small. We show how to solve CLOSEST STRING in linear time for fixed d-the exponential growth in d is bounded by O(d(d)). We extend this result to the closely related problems d-MISMATCH and DISTINGUISHING STRING SELECTION. Moreover, we also show that CLOSEST STRING is solvable in linear time when k is fixed and d is arbitrary. In summary, this means that CLOSEST STRING is fixed-parameter tractable with respect to parameter d and with respect to parameter k. Finally, the practical usefulness of our findings is substantiated by some experimental results.

关键词： consensus word analysis NP-complete exact algorithms fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Graph-modeled data clustering:: Fixed-parameter algorithms for clique generation

引用

5th Italian Conference on algorithms and Complexity

作者： Gramm, J Guo, J Hüffner, F Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

ISBN: (纸本)3540401768

We present efficient fixed-parameter algorithms for the NP-complete edge modification problems CLUSTER EDITING and CLUSTER DELETION. Here, the goal is to make the fewest changes to the edge set of an input graph such that the new graph is a vertex-disjoint union of cliques. Allowing up to k edge additions and deletions (CLUSTER EDITING), we solve this problem in O(2.27(k) + \V\(3)) time;allowing only up to k edge deletions (CLUSTER DELETION), we solve this problem in O(1.77(k) + \V\(3)) time. The key ingredients of our algorithms are two easy to implement bounded search tree algorithms and a reduction to a problem kernel of size O(k(3)). This improves and complements previous work.

关键词： NP-complete problems edge modification problems data clustering fixed-parameter tractability exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Random knapsack in expected polynomial time 03

Random knapsack in expected polynomial time

引用

Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

作者： Rene Beier Berthold Vöcking Max-Planck-Institut für Informatik Saarbrücken Germany Universität Dortmund Germany

ISBN: (纸本)9781581136746

In this paper, we present the first average-case analysis proving an expected polynomial running time for an exact algorithm for the 0/1 knapsack problem. In particular, we prove, for various input distributions, that the number of dominating solutions (i.e., Pareto-optimal knapsack fillings) to this problem is polynomially bounded in the number of available items. An algorithm by Nemhauser and Ullmann can enumerate these solutions very efficiently so that a polynomial upper bound on the number of dominating solutions implies an algorithm with expected polynomial running *** random input model underlying our analysis is very general and not restricted to a particular input distribution. We assume adversarial weights and randomly drawn profits (or vice versa). Our analysis covers general probability distributions with finite mean, and, in its most general form, can even handle different probability distributions for the profits of different items. This feature enables us to study the effects of correlations between profits and weights. Our analysis confirms and explains practical studies showing that so-called strongly correlated instances are harder to solve than weakly correlated ones.

关键词： exact algorithms knapsack problem average case analysis

来源：评论

学校读者我要写书评

暂无评论

Fast and exact transistor sizing based on iterative relaxation

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2002年第5期21卷 568-581页

作者： Sundararajan, V Sapatnekar, SS Parhi, KK Texas Instruments Inc Wireless Infrastruct Branch Dallas TX 75243 USA Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA

This paper presents MINFLOTRANSIT, a new transistor sizing tool for fast sizing of combinational circuits with minimal cost. MINFLOTRANSIT is an iterative relaxation-based tool that has two alternating phases. For a circuit with \V\ transistors and \E\ wires, the first phase (D-phase) is based on minimum cost network How, which in our application, has a worst case complexity of O(\Vparallel toE\ log(log(\V\))). The second phase (W-phase) has a worst case complexity of O(\Vparallel toE\). In practice, during our simulations both the D-phase and W-phase show a near linear run-time dependence on the size of the circuit, comparable to TILOS. Simulation results show excellent run-time behavior for MINFLOTRANSIT on all the ISCAS85 benchmark circuits. For reasonable delay targets, MINFLOTRANSIT shows up to 16.5% area savings (in relatively large circuits) over a circuit sized using a TILOS-like algorithm. In our opinion, the primary contribution of this paper is to take advantage of the structure of the transistor sizing problem and devise an iterative relaxation based gradient descent approach (D-phase) that has excellent convergence properties.

关键词： exact algorithms general/convex delay models gradient descent gate sizing iterative relaxation minimum cost network flow simple discrete monotonic programming speed of convergence transistor sizing

来源：评论

学校读者我要写书评

暂无评论

Models, relaxations and exact approaches for the capacitated vehicle routing problem

引用

DISCRETE APPLIED MATHEMATICS 2002年第1-3期123卷 487-512页

作者： Toth, P Vigo, D Univ Bologna Dipartimento Elettron Informat & Sistemist I-40136 Bologna Italy

In this paper we review the exact algorithms based on the branch and bound approach proposed in the last years for the solution of the basic version of the vehicle routing problem (VRP), where only the vehicle capacity constraints are considered. These algorithms have considerably increased the size of VRPs that can be solved with respect to earlier approaches. Moreover, at least for the case in which the cost matrix is asymmetric, branch and bound algorithms still represent the state-of-the-art with respect to the exact solution. Computational results comparing the performance of different relaxations and algorithms on a set of benchmark instances are presented. We conclude by examining possible future directions of research in this field. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： vehicle routing problem exact algorithms branch and bound relaxations

来源：评论

学校读者我要写书评

暂无评论

Performance evaluation of local ROI algorithms for exact ROI reconstruction in spiral cone-beam computed tomography

引用

IEEE TRANSACTIONS ON NUCLEAR SCIENCE 2001年第3期48卷 697-702页

作者： Sourbelle, K Lauritsch, G Tam, KC Noo, F Kalender, WA Inst Med Phys D-91054 Erlangen Germany Siemens Med Engn D-91050 Erlangen Germany Siemens Corp Res Princeton NJ 08540 USA Inst Elect Montefiore B-4000 Liege Belgium

This paper investigates the performance of exact reconstruction algorithms for spiral cone-beam computed tomography. We compare two different approaches of exact algorithms: the first one is the Radon algorithm with explicit calculation of radon data and subsequent direct inversion, the second approach is a reformulation of the Radon algorithm as a three-dimensional (3-D) filtered backprojection (FBP) method. Both algorithms are able to reconstruct a region of interest (ROI) of a long object by using the local ROI technique. The goal of this study is to identify which algorithm has the better performance with respect to image quality and practicability. The properties of the algorithms are analyzed. Image quality is evaluated regarding artifacts, spatial as well as contrast resolution, and noise properties. The 3-D point spread function (PSF) is examined for violations of isotropy and spatial invariance. In-plane and axial resolutions are derived from the in-plane modulation transfer function (MTF) and the slice sensitivity profile (SSP), respectively. The results show that for the two implementations investigated in this study, the image quality is similar, with a slight advantage of the FBP case. The algorithms yield images almost free of artifacts but with a poor spatial resolution. Regarding practicability, however, the FBP approach seems to be a more convenient and more flexible method because of the sequential processing of the projections and the easy control of image characteristics.

关键词： cone-beam CT contrast resolution exact algorithms image quality local object problem local ROI noise spatial resolution

来源：评论

学校读者我要写书评

暂无评论

Performance evaluation of local ROI algorithms for exact ROI reconstruction in spiral cone-beam computed tomography

Performance evaluation of local ROI algorithms for exact ROI...

引用

Medical Imaging Conference (MIC)

关键词： cone-beam CT contrast resolution exact algorithms image quality local object problem local ROI noise spatial resolution

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：