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

Improved approximation algorithms for broadcast scheduling

SIAM JOURNAL ON COMPUTING 2008年第3期38卷 1157-1174页

作者： Bansal, Nikhil Coppersmith, Don Sviridenko, Maxim IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Ctr Commun Res IDA Princeton NJ 08540 USA

We consider scheduling policies in a client-server system where the server delivers data by broadcasting it to the users. In thesimplest model of the problem, there is a single server that holds n pages of unit size. Multiple requests for these pages arrive over time. At each time slot the server broadcasts exactly one page which satisfies all of the outstanding requests for this page at that time. We consider the problem of minimizing the average response time of requests, where the response time of the request is the duration since the request is placed until the time it is satisfied. For the offline version of this problem we give an algorithm with an approximation ratio of O(log(2)(n)/log log(n)). More generally, for any epsilon > 0, the algorithm achieves an average response time of (2 + epsilon) . OPT + O(log n . log(1 + epsilon)(n)), which is useful when the optimum value is large. This substantially improves the previously best known approximation factor of O(root n) for the problem [N. Bansal, M. Charikar, S. Khanna, and J. Naor, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete algorithms, Vancouver, British Columbia, ACM, New York, SIAM, Philadelphia, 2005, pp. 215 - 221]. Our result is based on iteratively relaxing and rounding an auxiliary linear program derived from a natural linear programming relaxation of the problem.

关键词： LP rounding approximation algorithm broadcast scheduling

来源：评论

学校读者我要写书评

暂无评论

Network Design with Edge-Connectivity and Degree Constraints

Network Design with Edge-Connectivity and Degree Constraints

引用

4th International Workshop on approximation and Online algorithms

作者： Fukunaga, Takuro Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto 606 Japan

ISBN: (纸本)9783540695134

We consider the following network design problem;Given a vertex set V with a metric cost c on V, an integer ka parts per thousand yen1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex vaV is equal to b(v). This problem generalizes metric TSP. In this paper, we show that the problem admits a rho-approximation algorithm if b(v)a parts per thousand yen2, vaV, where rho=2.5 if k is even, and rho=2.5+1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP.

关键词： approximation algorithm Degree constraint Edge-connectivity (m, n)-VRP TSP Vehicle routing problem

来源：评论

学校读者我要写书评

暂无评论

Nonlinear Optimization over a Weighted Independence System

Nonlinear Optimization over a Weighted Independence System

引用

5th International Conference on algorithmic Aspects in Information and Management

作者： Lee, Jon Onn, Shmuel Weismantel, Robert IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Technion Israel Inst Technol Haifa 32000 Israel Otto von Guericke Univ D-39106 Magdeburg Germany

ISBN: (纸本)9783642021572

We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear optimization oracle. We provide a polynomial-time algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r is a constant depending on certain Frobenius numbers of the weights and is independent of the size of the ground set. In contrast, we show that finding an optimal (0-best) solution requires exponential time even in a very special case of the problem.

关键词： independence system matroid oracle computation exponential running time combinatorial optimization integer programming nonlinear optimization approximation algorithm Frobenius number

来源：评论

学校读者我要写书评

暂无评论

Interference and Power Constrained Broadcasting and Multicasting in Wireless Ad Hoc Networks with Directional Antennas

Interference and Power Constrained Broadcasting and Multicas...

引用

6th International Conference on Mobile Adhoc and Sensor Systems

作者： Li, Zheng Li, Deying Liu, Ming Renmin Univ China MOE Sch Informat Key Lab Data Engn & Knowledge Engn Beijing Peoples R China Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China

ISBN: (纸本)9781424451142

Broadcasting/Multicasting problems have been well studied in wireless ad hoc networks. However, only a few approaches take into account the low interference and energy efficiency as the optimization objective simultaneously. In this paper, we study the interference and power constrained broadcast/multicast and the delay-bounded interference and power constrained broadcast/multicast routing problems in wireless ad hoc networks using directional antennas. We propose an approximation and a heuristic algorithm for the two problems, respectively. Importantly, motivated by the study of above optimization problems, we propose approximation schemes for two multi-constrained directed Steiner tree problems, respectively. Broadcast/Multicast message by using the trees found by our algorithms tend to have less channel collisions and higher network throughput. The theoretical results are corroborated by simulation studies.

关键词： wireless ad hoc networks directional antennas broadcasting/multicasting energy efficient interference approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Scheduling with Rejection to Minimize the Makespan

Scheduling with Rejection to Minimize the Makespan

引用

3rd International Conference on Combinatorial Optimization and Applications

作者： Zhang, Yuzhong Ren, Jianfeng Wang, Chengfei Qufu Normal Univ Inst Operat Res Rizhao 276826 Peoples R China

ISBN: (纸本)9783642020254

In this paper, we consider the scheduling with rejection. The objective functions are to minimize the maximum completion time of the processed ones when the total compression cost is given. Firstly, we prove that the problem 1 vertical bar rej vertical bar C(max)/TCP is NP-hard, which implying that P(m)vertical bar rej vertical bar C(max)/TCP, 1 vertical bar rej, r(j)vertical bar C(max)/TCP, 1 vertical bar rej, on - line vertical bar C(max)/TCP are all NP-hard. Secondly, for problem P(m)vertical bar rej vertical bar C(max)/TCP we design a pseudopolynomial time dynamic programming algorithm that solves it exactly and an FPTAS (full polynomial time approximation scheme) when,in is a constant. We also design a pseudopolynomial time dynamic programming algorithm and an FPTAS for the case of non-identical job arrival problem 1 vertical bar rej, r(j)vertical bar C(max)/TCP. In the end, we consider the on-line problem 1 vertical bar rej, on - line vertical bar C(max)/TCP and prove that there doesn't exist any on-line algorithm with a constant competitive ratio for it, even if the jobs only have two different release times.

关键词： approximation algorithm scheduling with rejection dynamic programming worst case performance ratio

来源：评论

学校读者我要写书评

暂无评论

Guarding Strategic Points of a Gallery

Guarding Strategic Points of a Gallery

引用

International Conference on Computer Technology and Development

作者： Moghaddam, Mohammad Hosseinzadeh Bagheri, Alireza Mamaghani, Ali Safari Afshord, Saied Taghavi Islamic Azad Univ Hashtrood Branch Hashtrood Iran Amirkabir Univ Technol Comp Engn Dept Tehran Iran Islamic Azad Univ Comp Engn Dept Bonab Iran Islamic Azad Univ Shabestar Iran

ISBN: (纸本)9780769538921

Many problems have posed in the art gallery theorem. Most of them are NP-hard. In this paper, we pose the new problem of Guarding strategic points of a gallery. Given a polygon P with n vertices and m strategic points which are in that polygon, determine minimum number of guards for guarding the strategic points. In this paper, we present approximation algorithms for point, vertex and edge guard versions of this new problem.

关键词： computational geometry art gallery approximation algorithm strategic points

来源：评论

学校读者我要写书评

暂无评论

A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs

A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs

引用

3rd International Conference on Combinatorial Optimization and Applications (COCOA 2009)

作者： Li, Xianyue Xu, Xiao-Hua Zou, Feng Du, Hongwei Wan, Pengjun Wang, Yuexuan Wu, Weili Lanzhou Univ Sch Math & Stat Lanzhou 730000 Gansu Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA IIT Dept Comp Sci Chicago IL 60616 USA Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China

ISBN: (纸本)9783642020254

The node-weighted Steiner tree problem is a variation of classical Steiner minimum tree problem. Given a graph G = (V, E) with node weight function C : V --> R+ and a subset X of V, the node-weighted Steiner tree problem is to find a Steiner tree for the set X such that its total weight is minimum. In this paper, we study this problem in unit disk graphs and present a (1+epsilon)-approximation algorithm for any epsilon > 0, when the given set of vertices is c-local. As an application, we use node-weighted Steiner tree to solve the node-weighted connected dominating set problem in unit disk graphs and obtain a (5+epsilon)-approximation algorithm.

关键词： Node-weighted Steiner tree minimum weighted connected dominating set polynomial-time approximation scheme approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Connectivity in Multi-interface Networks

Connectivity in Multi-interface Networks

引用

4th International Symposium on Trustworthy Global Computing

作者： Kosowski, Adrian Navarra, Alfredo Pinotti, Cristina M. Univ Bordeaux 1 LaBRI 351 Cours Liberat F-33405 Talence France Gdansk Univ Technol Dept Algorithms & Syst Modeling PL-80952 Gdansk Poland Univ Perugia Dipartimento Matemat Informat I-06123 Perugia Italy

ISBN: (纸本)9783642009440

Let G = (V, E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). In general, every node holds a subset of all the possible k interfaces. Such networks are known as multi-interface networks. In this setting, we study a basic problem called Connectivity, corresponding to the well-known Minimum Spanning Tree problem in graph theory. In practice, we need to cover a subgraph of G of minimum cost which contains a spanning tree of G. A connection is covered (activated) when the endpoints of the corresponding edge share at least one active interface. The connectivity problem turns out to be APX-hard in general and for many restricted graph classes, however it is possible to provide approximation algorithms: 2-approximation in general and (2-1/k)-approximation for unit cost interfaces. We also consider the problem in special graph classes, such as graphs of bounded degree, planar graphs, graphs of bounded treewidth, complete graphs.

关键词： Energy saving wireless network multi-interface network approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Solve Fractal Dimension of Shanghai Stock Market by RBF Neural Networks

Solve Fractal Dimension of Shanghai Stock Market by RBF Neur...

引用

16th International Conference on Management Science and Engineering

作者： Wang Xu-lei Sun Chun-wei Shanghai Univ Sch Management Shanghai 200444 Peoples R China Qingdao Agr Univ Coll Econ & Management Qingdao 266109 Peoples R China Qingdao Agr Univ Coll Sci Qingdao 266109 Peoples R China

ISBN: (纸本)9781424439706

The actual financial time series is random walk process which is biased, and has significant fractal features and long-term memory effect. Research results also show the existence of low dimension chaos in stock market. Fractal dimension is the salient features of stock market chaos, and the next integer larger than correlation dimension is the number of the independent system variable which is required by setting up the system dynamics model. In this paper, we get the fractal dimension of Shanghai stock market through function approximation algorithm of RBF neural networks and discuss the influence of sample size and growth trend. It provides a measurement method for fractal dimension.

关键词： Chaos theory fractal dimension RBF neutral networks approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Two New approximation algorithms for the Maximum Planar Subgraph Problem

引用

ACTA CYBERNETICA 2008年第3期18卷 503-527页

作者： Poranen, Timo Univ Tampere Dept Comp Sci POB 607 FIN-33014 Tampere Finland

The maximum planar subgraph problem (MPS) is defined as follows: given a graph G, find a largest planar subgraph of G. The problem is NP-hard and it has applications in graph drawing and resource location optimization. Calinescu et al. [J. Alg. 27, 269-302 (1998)] presented the first approximation algorithms for MPS with nontrivial performance ratios. Two algorithms were given, a simple algorithm which runs in linear time for bounded-degree graphs with a ratio 7/18 and a more complicated algorithm with a ratio 4/9. Both algorithms produce outerplanar subgraphs. In this article we present two new versions of the simpler algorithm. The first new algorithm still runs in the same time, produces outerplanar sub graphs, has at least the same performance ratio as the original algorithm, but in practice it finds larger planar subgraphs than the original algorithm. The second new algorithm has similar properties to the first algorithm, but it produces only planar subgraphs. We conjecture that the performance ratios of our algorithms are at least 4/9 for MPS. We experimentally compare the new algorithms against the original simple algorithm. We also apply the new algorithms for approximating the thickness and outerthickness of a graph. Experiments show that the new algorithms produce clearly better approximations than the original simple algorithm by Calinescu et al.

关键词： maximum planar subgraph maximum outerplanar subgraph thickness outerthickness triangular cactus heuristic approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：