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

Optimal Spectrum-Efficient Routing in Multihop Wireless Networks

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2009年第12期8卷 5822-5826页

作者： Saad, Mohamed Univ Sharjah Dept Elect & Comp Engn Sharjah U Arab Emirates

This paper addresses the problem of finding the route with maximum end-to-end spectral efficiency, under the constraint of equal bandwidth sharing, in multihop wireless networks. This problem has been addressed recently in the literature, and only exhaustive search with exponential computational complexity or suboptimal heuristics are known. This paper closes the algorithmic gap by introducing two algorithms that provide provably optimal solutions to the problem in polynomial-time. The proposed algorithms rely on the iterative use of a shortest path procedure. Our computational results further illustrate the efficiency of the proposed approach.

关键词： Multihop wireless networks spectrum-efficient routing polynomial-time algorithms divide-and-conquer

来源：评论

学校读者我要写书评

暂无评论

A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case

引用

DISCRETE APPLIED MATHEMATICS 2009年第2期157卷 339-355页

作者： Kats, Vladimir Levner, Eugene Holon Inst Technol IL-58102 Holon Israel Inst Ind Math IL-84105 Beer Sheva Israel

In this paper we consider the problem of no-wait cyclic scheduling of identical parts in an m-machine production line in which a robot is responsible for moving each part from a machine to another. The aim is to rind the minimum cycle time for the so-called 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. The earlier known polynomial-time algorithms for this problem are applicable only under the additional assumption that the robot travel times satisfy the triangle inequalities. We lift this assumption on robot travel times and present a polynomial-time algorithm with the same time complexity as in the metric case, O(m(5) log m). (C) 2008 Elsevier B.V. All rights reserved.

关键词： Cyclic scheduling Robotic scheduling polynomial-time algorithms Complexity No-wait condition Euler formula

来源：评论

学校读者我要写书评

暂无评论

PREEMPTIVE SCHEDULING algorithms WITH NESTED PROCESSING SET RESTRICTION

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2009年第6期20卷 1147-1160页

作者： Huo, Yumei Leung, Joseph Y-T Wang, Xin CUNY Dept Comp Sci Staten Isl NY 10314 USA New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA Bloomberg LP R&D Dept New York NY 10022 USA

We consider the problem of preemptively scheduling n independent jobs {J(1),J(2), ..., J(n)} on m parallel machines {M(1),M(2), ..., M(m)}, where each job J(j) can only be processed on a prespecified subset M(j) of machines called its processing set. The machines are linearly ordered, and the processing set of J(j) is specified by two machine indexes a(j) and b(j);i.e., M(j) = {M(aj),M(aj+1), ..., M(bj)}. The processing sets are nested;i.e., for i not equal j, we have M(i) subset of M(j), or M(j) subset of M(i),or M(j) boolean AND M(i) = phi..Our goal is to minimize the makespan. We first give an O(n logn)-time algorithm to find an optimal schedule. We then give an O(mn + nlogn)-time algorithm to find a maximal schedule, where a schedule is said to be maximal if it processes as much work as any other schedule in any time interval [0, t], t>0.

关键词： Preemptive scheduling nested processing set inclusive processing set makespan minimization polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for multivariate linear problems with finite-order weights: Worst case setting

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2005年第4期5卷 451-491页

作者： Wasilkowski, GW Wozniakowski-, H Univ Kentucky Dept Comp Sci Lexington KY 40506 USA Columbia Univ Dept Comp Sci New York NY 10027 USA Univ Warsaw Inst Appl Math PL-02097 Warsaw Poland

We consider approximation of linear multivariate problems defined over weighted tensor product Hilbert spaces with finite-order weights. This means we consider functions of d variables that can be represented as sums of functions of at most q* variables. Here, q* is fixed (and presumably small) and d may be arbitrarily large. For the univariate problem, d = 1, we assume we know algorithms A(1,epsilon) that use O(epsilon(-p)) function or linear functional evaluations to achieve an error epsilon in the worst case setting. Based on these algorithms A(1,epsilon), we provide a construction of polynomial-time algorithms A(d,epsilon) for the general d-variate problem with the number of evaluations bounded roughly by epsilon(-p)d(q*) to achieve an error epsilon in the worst case setting.

关键词： multivariate linear problems tractability polynomial-time algorithms finite-order weights small effective dimension

来源：评论

学校读者我要写书评

暂无评论

A pricing approach for bandwidth allocation in differentiated service networks

引用

COMPUTERS & OPERATIONS RESEARCH 2008年第12期35卷 3769-3786页

作者： Guan, Yongpei Yang, Weilai Owen, Henry Blough, Douglas A. Univ Oklahoma Sch Ind Engn Norman OK 73019 USA Georgia Inst Technol Sch Elect & Comp Engn Atlanta GA 30332 USA

We present a decentralized auction-based scheme for bandwidth allocation and pricing in a differentiated service-based network. Different classes of clients provide their own expected bandwidth price and required amount of bandwidth. A service provider decides the admission price and differentiated service provided for each class of clients. We introduce mathematical formulations and provide a solution approach to maximize the service provider's revenue. For a single bottleneck link case, a polynomial-time algorithm is developed to obtain an optimal solution. For a multiple bottleneck link case, a heuristic algorithm is developed to solve the problem. The effectiveness of our solution approach is validated by simulation results, which compare our algorithms against the traditional flat-rate pricing approach. (c) 2007 Elsevier Ltd. All rights reserved.

关键词： telecommunication network pricing polynomial-time algorithms heuristics simulation

来源：评论

学校读者我要写书评

暂无评论

Resilient network coding in the presence of Byzantine adversaries

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第6期54卷 2596-2603页

作者： Jaggi, Sidharth Langberg, Michael Katti, Sachin Ho, Tracey Katabi, Dina Medard, Muriel Effros, Michelle Chinese Univ Hong Kong Dept Informat Engn Shatin Hong Kong Peoples R China Open Univ Israel Div Comp Sci IL-43107 Raanana Israel MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA CALTECH Dept Elect Engn Pasadena CA 91125 USA MIT Lab Informat & Decis Syst Cambridge MA 02139 USA

Network coding substantially increases network throughput. But since it involves mixing of information inside the network, a single corrupted packet generated by a malicious node can end up contaminating all the information reaching a destination, preventing decoding. This paper introduces distributed polynomial-time rate-optimal network codes that work in the presence of Byzantine nodes. We present algorithms that target adversaries with different attacking capabilities. When the adversary can eavesdrop on all links and jam z(O) links, our first algorithm achieves a rate of C - 2z(O), where C is the network capacity. In contrast,, when the adversary has limited eavesdropping capabilities, we provide algorithms that achieve the higher rate of C - z(O). Our algorithms attain the optimal rate given the strength of the adversary. They are information-theoretically secure. They operate in a distributed manner, assume no knowledge of the topology, and can be designed and implemented in polynomial time. Furthermore, only the source and destination need to be modified;nonmalicious nodes inside the network are oblivious to the presence of adversaries and implement a classical distributed network code. Finally, our algorithms work over wired and wireless networks.

关键词： Byzantine adversaries distributed network error-correcting codes eavesdroppers information-theoretically optimal list decoding polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing the cores of strategic games with punishment-dominance relations

引用

INTERNATIONAL JOURNAL OF GAME THEORY 2008年第2期37卷 185-201页

作者： Masuzawa, Takuya Osaka Univ Econ Fac Econ Higashi Yodogawa Ku Osaka Japan

In this paper, we discuss the computational complexity of the strategic cores of a class of n-person games defined by Masuzawa (Int J Game Theory 32:479-483, 2003), which includes economic situations with monotone externality. We propose an algorithm for finding an alpha-core strategy of any game in this class which, counting the evaluation of a payoff for a strategy profile as one step, terminates after O(n(3). M) operations, where M is the maximum size of a strategy set of any of the n players. The idea underlying this method is based on the property of reduced games.

关键词： polynomial-time algorithms NTU games the alpha-core reduced games public good provision

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time algorithm to estimate returns to scale in FDH models

引用

COMPUTERS & OPERATIONS RESEARCH 2007年第7期34卷 2168-2176页

作者： Soleimani-damaneh, M. Reshadi, M. Teacher Training Univ Fac Math Sci & Comp Engn Tehran 15618 Iran Azad Univ Res & Sci Branch Dept Math Tehran Iran

This paper provides a polynomial-time algorithm to estimate returns to scale in FDH models, having many strong computational advantages. The equivalence of this method and the only current approach is proved. (c) 2005... 详细信息

关键词： DEA FDH returns-to-scale polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

PhySIC:: A veto supertree method with desirable properties

引用

SYSTEMATIC BIOLOGY 2007年第5期56卷 798-817页

作者： Ranwez, Vincent Berry, Vincent Criscuolo, Alexis Fabre, Pierre-Henri Guillemot, Sylvain Scornavacca, Celine Douzery, Emmanuel J. P. Univ Montpellier I Inst Sci Evolut CNRS ISEMUMR 5554 F-34095 Montpellier France Univ Montpellier 2 CNRS Lab Informat Robot Microelectron LIRMMUMR 5506 F-34392 Montpellier France

This paper focuses on veto supertree methods;i.e., methods that aim at producing a conservative synthesis of the relationships agreed upon by all source trees. We propose desirable properties that a supertree should satisfy in this framework, namely the non-contradiction property (PC) and the induction property (PI). The former requires that the supertree does not contain relationships that contradict one or a combination of the source topologies, whereas the latter requires that all topological information contained in the supertree is present in a source tree or collectively induced by several source trees. We provide simple examples to illustrate their relevance and that allow a comparison with previously advocated properties. We show that these properties can be checked in polynomial time for any given rooted supertree. Moreover, we introduce the PhySIC method (PHYlogenetic Signal with induction and non-Contradiction). For k input trees spanning a set of n taxa, this method produces a supertree that satisfies the above-mentioned properties in O(kn(3) + n(4)) computing time. The polytornies of the produced supertree are also tagged by labels indicating areas of conflict as well as those with insufficient overlap. As a whole, PhySIC enables the user to quickly summarize consensual information of a set of trees and localize groups of taxa for which the data require consolidation. Lastly, we illustrate the behaviour of PhySIC on primate data sets of various sizes, and propose a supertree covering 95% of all primate extant genera. The PhySIC algorithm is available at http:/ /***/cgi-bin/PhySIC. [Formal properties;phylogenetics;polynomial-time algorithms;primates;software;supertrees;triplets;veto methods.]

关键词： Formal properties phylogenetics polynomial-time algorithms primates software supertrees triplets veto methods

来源：评论

学校读者我要写书评

暂无评论

Minimizing Total Completion time on Uniform Machines with Deadline Constraints

引用

ACM TRANSACTIONS ON algorithms 2006年第1期2卷 95-115页

作者： Gonzalez, Teofilo F. Leung, Joseph Y. -T. Pinedo, Michael Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA NYU Stern Sch Business New York NY 10012 USA

Consider n independent jobs and m uniform machines in parallel. Each job has a processing requirement and a deadline. All jobs are available for processing at time t = 0. Job j must complete its processing before or at its deadline and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines. We present a polynomial-time algorithm that given a feasible set of jobs, constructs a schedule that minimizes the total completion time Sigma C-j. In the classical alpha vertical bar beta vertical bar gamma scheduling notation, this problem is referred to as Qm vertical bar prmt, (d) over bar (j )vertical bar Sigma C-j. It is well known that a generalization of this problem with regard to its machine environment results in an NP-hard problem.

关键词： Mean flow time uniform machines deadline constraints polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：