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

approximation algorithms for homogeneous polynomial optimization with quadratic constraints

MATHEMATICAL PROGRAMMING 2010年第2期125卷 353-383页

作者： He, Simai Li, Zhening Zhang, Shuzhong Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China City Univ Hong Kong Dept Management Sci Kowloon Tong Hong Kong Peoples R China

In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function, subject to homogeneous quadratic constraints. Such optimization models have wide applications, e.g., in signal processing, magnetic resonance imaging (MRI), data training, approximation theory, and portfolio selection. Since polynomial functions are non-convex, the problems under consideration are all NP-hard in general. In this paper we shall focus on polynomial-time approximation algorithms. In particular, we first study optimization of a multi-linear tensor function over the Cartesian product of spheres. We shall propose approximation algorithms for such problem and derive worst-case performance ratios, which are shown to be dependent only on the dimensions of the model. The methods are then extended to optimize a generic multi-variate homogeneous polynomial function with spherical constraint. Likewise, approximation algorithms are proposed with provable approximation performance ratios. Furthermore, the constraint set is relaxed to be an intersection of co-centered ellipsoids;namely, we consider maximization of a homogeneous polynomial over the intersection of ellipsoids centered at the origin, and propose polynomial-time approximation algorithms with provable worst-case performance ratios. Numerical results are reported, illustrating the effectiveness of the approximation algorithms studied.

关键词： Multi-linear tensor form Polynomial function optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for base station placement in wireless sensor networks

Approximation algorithm for base station placement in wirele...

引用

4th Annual IEEE-Communications-Society Conference on Sensor, Mesh and AD HOC Communications and Networks

作者： Shi, Yi Hou, Y. Thomas Virginia Tech Bradley Dept Elect & Comp Engn Blacksburg VA 24061 USA

ISBN: (纸本)9781424412679

Base station location has significant impact on network lifetime performance for a sensor network. For a multi-hop sensor network, this problem is particular challenging as we need to jointly consider base station placement and data routing strategy to maximize network lifetime performance. This paper presents an approximation algorithm that can guarantee (1 - epsilon) optimal network lifetime performance for base station placement problem with any desired error bound epsilon > 0. The proposed (1 - epsilon) optimal approximation algorithm is based on several novel techniques that enable to reduce an infinite search space to a finite-element search space for base station location. The first technique used in this reduction is to discretize cost parameters (with performance guarantee) associated with energy consumption. Subsequently, the continuous search space can be broken up into a finite number of subareas. The second technique is to exploit the cost property of each subarea and represent it by a novel notion called "fictitious cost point," each with guaranteed cost bounds. This approximation algorithm offers a simpler and in most cases practically faster algorithm than a state-of-the-art algorithm and represents the best known result to this important problem.

关键词： theory approximation algorithm base station placement network lifetime sensor network

来源：评论

学校读者我要写书评

暂无评论

A Fully Polynomial approximation Scheme for a Knapsack Problem with a Minimum Filling Constraint (Extended Abstract)

A Fully Polynomial Approximation Scheme for a Knapsack Probl...

引用

12th algorithms and Data Structures Symposium (WADS 2011)

作者： Xu, Zhou Lai, Xiaofan Hong Kong Polytech Univ Fac Business Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China

ISBN: (纸本)9783642222993

We study a variant of the knapsack problem, where a minimum filling constraint is imposed such that the total weight of selected items cannot be less than a given threshold. We consider the case when the ratio of the threshold to the capacity equals a given constant alpha with 0 <= alpha <= 1. For any such constant alpha, since finding an optimal solution is NP-hard, we develop the first FPTAS for the problem, which has a time complexity polynomial in 1/(1 - alpha).

关键词： approximation algorithm FPTAS knapsack problem minimum filling constraint

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for homogeneous polynomial optimization with quadratic constraints

Approximation algorithms for homogeneous polynomial optimiza...

引用

20th International Symposium of Mathematical Programming (ISMP)

关键词： Multi-linear tensor form Polynomial function optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation and Heuristic algorithms for End-System Based Application-Layer Multicast for Voice Conferences

Approximation and Heuristic Algorithms for End-System Based ...

引用

25th IEEE International Conference on Advanced Information Networking and Applications (AINA)

作者： Lin, Hwa-Chun Yang, Hsiu-Ming Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30013 Taiwan Natl Tsing Hua Univ Inst Commun Engn Hsinchu Taiwan

ISBN: (纸本)9780769543376

This paper studies the problem of constructing application-layer multicast trees for end-system based voice conferences in which voice mixing and replication are performed at end systems. This problem is formulated as a degree-constrained node-weighted Steiner tree problem with a degree-dependent cost associated with each node, which is a generalization of the degree-constrained node-weighted Steiner tree problem with a fixed cost associated with each node. This paper devises a novel technique to deal with degree-dependent nodal costs and develops a bicriteria approximation algorithm, with the degree of each node and the cost of the tree as two objectives, for this more general Steiner tree problem. The bound on the degree of each node and the bound on the cost of the tree constructed by the bicriteria approximation algorithm are derived. Two heuristic algorithms which construct multicast trees that obey the degree constraint on each node are obtained by modifying the bicriteria approximation algorithm. The performances of the two heuristic algorithms are studied via simulations.

关键词： Application-layer multicast voice conferences approximation algorithm heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

Single-Vehicle Scheduling Problems with Release and Service Times on a Line

引用

NETWORKS 2011年第2期57卷 128-134页

作者： Yu, Wei Liu, Zhaohui E China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

We consider the following vehicle scheduling problem. There are some customers on a line that will be served by a single vehicle. Each customer is associated with a release time and a service time. The objective is to schedule the vehicle to minimize the makespan. For the tour version, where the makespan means the time when the vehicle has served all customers and returned back to its initial location, we present a 3/2-approximation algorithm. For the path version, where the makespan is defined as the time by which the last customer has been served completely, we present a 5/3-approximation algorithm. (C) 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 128-134 2011

关键词： vehicle routing vehicle scheduling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Two-agent scheduling to minimize the total cost

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2011年第1期215卷 39-44页

作者： Nong, Q. Q. Cheng, T. C. E. Ng, C. T. Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Ocean Univ China Coll Math Sci Qingdao 266100 Shandong Peoples R China

Two agents, each having his own set of jobs, compete to perform their own jobs on a common processing resource. Each job of the agents has a weight that specifies its importance. The cost of the first agent is the maximum weighted completion time of his jobs while the cost of the second agent is the total weighted completion time of his jobs. We consider the scheduling problem of determining the sequence of the jobs such that the total cost of the two agents is minimized. We provide a 2-approximation algorithm for the problem, show that the case where the number of jobs of the first agent is fixed is NP-hard, and devise a polynomial time approximation scheme for this case. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Scheduling Multi-agent approximation algorithm Polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A Distributed algorithm for the Replica Placement Problem

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2011年第9期22卷 1455-1468页

作者： Zaman, Sharrukh Grosu, Daniel Wayne State Univ Dept Comp Sci Detroit MI 48202 USA

Caching and replication of popular data objects contribute significantly to the reduction of the network bandwidth usage and the overall access time to data. Our focus is to improve the efficiency of object replication within a given distributed replication group. Such a group consists of servers that dedicate certain amount of memory for replicating objects requested by their clients. The content replication problem we are solving is defined as follows: Given the request rates for the objects and the server capacities, find the replica allocation that minimizes the access time over all servers and objects. We design a distributed approximation algorithm that solves this problem and prove that it provides a 2-approximation solution. We also show that the communication and computational complexity of the algorithm is polynomial with respect to the number of servers, the number of objects, and the sum of the capacities of all servers. Finally, we perform simulation experiments to investigate the performance of our algorithm. The experiments show that our algorithm outperforms the best existing distributed algorithm that solves the replica placement problem.

关键词： Replication distributed replication group distributed algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithm for Constructing Minimum Size Wireless Sensor Networks to Fully Cover Critical Square Grids

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2011年第4期10卷 1154-1164页

作者： Ke, Wei-Chieh Liu, Bing-Hong Tsai, Ming-Jer Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30013 Taiwan Natl Kaohsiung Univ Appl Sci Dept Elect Engn Kaohsiung 80778 Taiwan

Wireless sensor networks are formed by connected sensors that each have the ability to collect, process, and store environmental information as well as communicate with others via inter-sensor wireless communication. These characteristics allow wireless sensor networks to be used in a wide range of applications. In many applications, such as environmental monitoring, battlefield surveillance, nuclear, biological, and chemical (NBC) attack detection, and so on, critical areas and common areas must be distinguished adequately, and it is more practical and efficient to monitor critical areas rather than common areas if the sensor field is large, or the available budget cannot provide enough sensors to fully cover the entire sensor field. This provides the motivation for the problem of deploying the minimum sensors on grid points to construct a connected wireless sensor network able to fully cover critical square grids, termed CRITICAL-SQUARE-GRID COVERAGE. In this paper, we propose an approximation algorithm for CRITICAL-SQUARE-GRID COVERAGE. Simulations show that the proposed algorithm provides a good solution for CRITICAL-SQUARE-GRID COVERAGE.

关键词： Wireless sensor network coverage problem NP-Complete problem sensor deployment approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices

引用

DISCRETE OPTIMIZATION 2011年第4期8卷 525-539页

作者： Boyd, Sylvia Carr, Robert Univ Ottawa SITE Ottawa ON K1N 6N5 Canada Sandia Labs Albuquerque NM 87185 USA

Consider the traveling salesman problem (TSP) defined on the complete graph, where the edge costs satisfy the triangle inequality. Let TOUR denote the optimal solution value for the TSP. Two well-known relaxations of the TSP are the subtour elimination problem and the 2-matching problem. If we let SUBT and 2M represent the optimal solution values for these two relaxations, then it has been conjectured that TOUR/SUBT <= 4/3, and that 2M/SUBT <= 10/9. In this paper, we exploit the structure of certain 1/2-integer solutions for the subtour elimination problem in order to obtain low cost TSP and 2-matching solutions. In particular, we show that for cost functions for which the optimal subtour elimination solution found falls into our classes, the above two conjectures are true. Our proofs are constructive and could be implemented in polynomial time, and thus, for such cost functions, provide a 4/3 (or better) approximation algorithm for the TSP. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Traveling salesman problem 2-matching approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：