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

EURO 2000 Conference

作者： Hochbaum, DS Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA Univ Calif Berkeley Walter A Haas Sch Business Berkeley CA 94720 USA

We define a class of monotone integer programs with constraints that involve up to three variables each. A generic constraint in such integer program is of the form ax - by≤z + c, where a and b are nonnegative and the variable z appears only in that constraint. We devise an algorithm solving such problems in time polynomial in the length of the input and the range of variables U. The solution is obtained from a minimum cut on a graph with O(nU) nodes and O(mU) arcs where n is the number of variables of the types x and y and m is the number of constraints. Our algorithm is also valid for nonlinear objective functions. Nonmonotone integer programs are optimization problems with constraints of the type ax + by≤z + c without restriction on the signs of a and b. Such problems are in general NP-hard. We devise here an algorithm, relying on a transformation to the monotone case, that delivers half integral superoptimal solutions in polynomial time. Such solutions provide bounds on the optimum value that can only be superior to bounds provided by linear programming relaxation. When the half integral solution can be rounded to an integer feasible solution, this is a 2-approximate solution. In that the technique is a unified 2-approximation technique for a large class of problems. The results apply also for general integer programming problems with worse approximation factors that depend on a quantifier measuring how far the problem is from the class of problems we describe. The algorithm described here has a wide array of problem applications. An additional important consequence of our results is that nonmonotone problems in the framework are MAX SNP-hard and at least as hard to approximate as vertex cover. Problems that are amenable to the analysis provided here are easily recognized. The analysis itself is entirely technical and involves manipulating the constraints and transforming them to a totally unimodular system while losing no more than a factor of 2 in the integral

关键词： approximation algorithm half integrality feasible cut minimum satisfiability vertex cover generalized satisfiability maximum clique superoptimal minimum cut

来源：评论

学校读者我要写书评

暂无评论

An efficient distributed algorithm for constructing small dominating sets

An efficient distributed algorithm for constructing small do...

引用

20th Symposium on Principles of Distributed Computing (PODC 01)

作者： Jia, LJ Rajaraman, R Suel, T Northeastern Univ Coll Comp Sci Boston MA 02115 USA Polytech Univ Dept Comp & Informat Sci Brooklyn NY 11201 USA

The dominating set problem asks for a small subset D of nodes in a graph such that every node is either in D or adjacent to a node in D. This problem arises in a number of distributed network applications, where it is important to locate a small number of centers in the network such that every node is nearby at least one center. Finding a dominating set of minimum size is NP-complete, and the best known approximation is logarithmic in the maximum degree of the graph and is provided by the same simple greedy approach that gives the well-known logarithmic approximation result for the closely related set cover problem. We describe and analyze new randomized distributed algorithms for the dominating set problem that run in polylogarithmic time, independent of the diameter of the network, and that return a dominating set of size within a logarithmic factor from optimal, with high probability. In particular, our best algorithm runs in O (log n log, Delta) rounds with high probability, where n is the number of nodes, Delta is one,plus the maximum degree of any node, and each round involves a constant number of message exchanges among any two neighbors;the size of the dominating set obtained is within O (log Delta) of the optimal in expectation and within O(log n) of the optimal with high probability. We also describe generalizations to the weighted case and the case of multiple covering requirements.

关键词： dominating set distributed computing approximation algorithm ad hoc network

来源：评论

学校读者我要写书评

暂无评论

On approximating the maximum diameter ratio of graphs

On approximating the maximum diameter ratio of graphs

引用

4th Slovenian Graph Theory Conference

作者： Marincek, J Mohar, B Univ Ljubljana Dept Math Ljubljana 1111 Slovenia

It is proved that computing the maximum diameter ratio (also known as the local density) of a graph is APX-complete. The related problem of finding a maximum subgraph of a fixed diameter d greater than or equal to 1 i... 详细信息

关键词： approximation algorithm APX-complete problem local density diameter

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for independent sets in map graphs

引用

JOURNAL OF algorithmS-COGNITION INFORMATICS AND LOGIC 2001年第1期41卷 20-40页

作者： Chen, ZZ Tokyo Denki Univ Dept Math Sci Hatoyama Saitama 3500394 Japan

This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1 + delta can be achieved by a quadratic-time algorithm for any given constant delta > 0, no matter whether each vertex of G is given a weight or not. In case G is given without a map, a ratio of 4 can be achieved by a low-degree polynomial-time algorithm if no vertex is given a weight, while a ratio of 5 can be achieved by a low-degree polynomial-time algorithm otherwise. (C) 2001 Academic Press.

关键词： independent set planar graph map graph approximation algorithm NP-hardness

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for maximum two-dimensional pattern matching

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期255卷 51-62页

作者： Arikati, SR Dessmark, A Lingas, A Marathe, MV Lund Univ Dept Comp Sci S-22100 Lund Sweden Univ Memphis Dept Math Sci Memphis TN 38152 USA Los Alamos Natl Lab Los Alamos NM 87545 USA Max Planck Inst Informat Saarbrucken Germany

We introduce the following optimization version of the classical pattern matching problem (referred to as the maximum pattern matching problem). Given a two-dimensional rectangular text and a two-dimensional rectangular pattern, find the maximum number of non-overlapping occurrences of the pattern in the text. Unlike the classical two-dimensional pattern matching problem, the maximum two-dimensional pattern matching problem is NP-complete. We devise polynomial time approximation algorithms and approximation schemes for this problem. We also briefly discuss how the approximation algorithms can be extended to include a number of other variants of the problem. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： pattern matching NP-hardness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The power of α-points in preemptive single machine scheduling

引用

JOURNAL OF SCHEDULING 2002年第2期5卷 121-133页

作者： Schulz, AS Skutella, M Tech Univ Berlin Fachbereich Math D-10623 Berlin Germany MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA

We consider the NP-hard preemptive single-machine scheduling problem to minimize the total weighted completion time subject to release dates. A natural extension of Smith's ratio rule is to preempt the currently active job whenever a new job arrives that has higher ratio of weight to processing time. We prove that the competitive ratio of this simple on-line algorithm is precisely 2. We also show that list scheduling in order of random alpha-points drawn from the same schedule results in an on-line algorithm with competitive ratio (4)/(3). Since its analysis relies on a well-known integer programming relaxation of the scheduling problem, the relaxation has performance guarantee A as well. On the other hand, we show that it is at best an (8)/(7)-relaxation. Copyright (C) 2002 John Wiley Sons, Ltd.

关键词： scheduling theory approximation algorithm on-line algorithm randomized algorithm LP relaxation combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

A note on approximating the survivable network design problem in hypergraphs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2002年第2期E85D卷 322-326页

作者： Zhao, L Nagamochi, H Ibaraki, T Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan Toyohashi Univ Technol Dept Informat & Comp Sci Toyohashi Aichi 4418580 Japan

We consider to design approximation algorithms for the survivable network design problem in hypergraphs (SNDPHG) based on algorithms developed for the survivable network design problem in graphs (SNDP) or the element connectivity problem in graphs (ECP). Given an instance of the SNDPHG. by replacing each hyperedge e = {v(1),...,v(k)} with a new vertex omega(e) and k edges {omega(e),nu(1)},...,{omega(e),nu(k)} we define an SNDP or ECP in the resulting graph. We show that by approximately solving the. SNDP or ECP defined in this way, several approximation algorithms for the SNDPHG can be obtained. One of our results is a d(max)(+)-approximation algorithm for the SNDPHG with d(max) less than or equal to 3, where d(max) (resp. d(max)(+)) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a d(max)(+)H(r(max))-approximation algorithm for the SNDPHG, where H(i) = Sigma(j=1)(l) 1/j is the harmonic function and r(max) is the maximum connectivity requirement.

关键词： survivable network design problem approximation algorithm connectivity graph hypergraph

来源：评论

学校读者我要写书评

暂无评论

A quasi-solution state evolution algorithm for channel assignment problems in cellular networks

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2002年第5期E85A卷 977-987页

作者： Funabiki, N Nakanishi, T Yokohira, T Tajima, S Higashino, T Okayama Univ Dept Commun Network Engn Okayama 7008530 Japan Osaka Univ Dept Informat & Math Sci Toyonaka Osaka 5608531 Japan

For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (CAP). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (channel span) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (QCAP). To solve hard CAP instances in reasonable time, QCAP evolutes quasi-solution states where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.

关键词： CAP approximation algorithm benchmark NP-hard cellular network

来源：评论

学校读者我要写书评

暂无评论

SEMI-DEFINITE RELAXATION algorithm OF MULTIPLE KNAPSACK PROBLEM

引用

Applied Mathematics(A Journal of Chinese Universities) 2002年第2期17卷 241-250页

作者： Chen Feng Yao EnyuDept.ofMath.,ZhejiangUniv.,Hangzhou310027,China Dept. of Math. Zhejiang Univ. Hangzhou China

The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a capacity *** goal is to find a subset of items of maximum profit such that they have a feasible packing in the ***(B,S,m,n) is strongly NP- Complete and no polynomial- time approximation algorithm can have an approxima- tion ratio better than0 .5 .In the last ten years,semi- definite programming has been empolyed to solve some combinatorial problems *** paper firstly presents a semi- definite re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .

关键词： multiple knapsack problem semi- definite relaxation approximation algorithm combina- torial optimization.

来源：评论

学校读者我要写书评

暂无评论

STATION LAYOUTS IN THE PRESENCE OF LOCATION CONSTRAINTS

引用

Journal of Interconnection Networks 2002年第1N02期3卷 1-17页

作者： PROSENJIT BOSE EVANGELOS KRANAKIS CHRISTOS KAKLAMANIS LEFTERIS M. KIROUSIS DANNY KRIZANC DAVID PELEG Carleton University School of Computer Science Ottawa Ontario K1S 5B6 Canada University of Patras Department of Computer Engineering and Informatics GR-26504 Patras Greece Wesleyan University Department of Mathematics Middletown CT 06459 USA Weizmann Institute of Science Department of Computer Science and Applied Mathematics Rehovot 76100 Israel

In wireless communication, the signal of a typical broadcast station is transmitted from a broadcast center p and reaches objects at a distance, say, r from it. In addition there is a radius r 0 , r 0 < r, such that the signal originating from the center of the station is so strong that human habitation within distance r 0 from the center p should be avoided. In other words, points within distance r 0 from the station comprise a hazardous zone. We consider the following station layout proble: Cover a given planar region that includes a collection of buildings with a minimum number of stations so that every point in the region is within the reach of a station, while at the same time no interior point of any building is within the hazardous zone of a station. We give algorithms for computing such station layouts in both the one- and two-dimensional cases.

关键词： approximation algorithm Broadcast station Health hazards Optimal layout Wireless communication

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：