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

On the minimum hitting set of bundles problem

THEORETICAL COMPUTER SCIENCE 2009年第45期410卷 4534-4542页

作者： Angel, Eric Bampis, Evripidis Gourves, Laurent CNRS FRE 3234 F-75775 Paris France Univ Evry IBISC CNRS Evry France Univ Paris 09 LAMSADE F-75775 Paris France

We consider a natural generalization of the classical MINIMUM HITTING SET problem, the MINIMUM HITTING SET OF BUNDLES problem (MHSB) which is defined as follows. We are given a set epsilon = (e(1), e(2), ... , e(n)} of n elements. Each element e(i) (i = 1, ... , n) has a positive cost c(i). A bundle b is a subset of epsilon. We are also given a collection s = {S-1, S-2, ... , S-m} of m sets of bundles. More precisely, each set S-j (j = 1, ... , m) is composed of g(j) distinct bundles b(j)(1), b(j)(2), ... ,b(j)(g(j)). A solution to MHSB is a subset epsilon' subset of epsilon such that for every S-j is an element of S at least one bundle is covered, i.e. b(j)(l) subset of epsilon' for some l is an element of {1, 2, ... , g(j)}. The total cost of the solution, denoted by C(epsilon'), is Sigma(vertical bar i vertical bar ej is an element of epsilon'vertical bar) ci. The goal is to find a solution with a minimum total cost. We give a deterministic N(1 - (1 - 1/N)(M))-approximation algorithm, where N is the maximum number of bundles per set and M is the maximum number of sets in which an element can appear. This is roughly speaking the best approximation ratio that we can obtain, since by reducing MHSB to the vertex cover problem, it implies that MHSB cannot be approximated within 1.36 when N = 2 and N - 1 - epsilon when N >= 3. It has to be noticed that the application of our algorithm in the case of the MIN k-SAT problem matches the best known approximation ratio. (C) 2009 Elsevier B.V. All rights reserved.

关键词： MINIMUM HITTING SET MIN k-SAT approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Mean analysis of an online algorithm for the vertex cover problem

引用

INFORMATION PROCESSING LETTERS 2009年第9期109卷 436-439页

作者： Birmele, Etienne Delbot, Francois Laforest, Christian Univ Evry INRA 1152 CNRS UMR 8071Lab Stat & Genome F-91000 Evry France Univ Evry CNRS FRE 3190 Lab IBISC F-91000 Evry France Univ B Pascal CNRS UMR 6158 LIMOS F-63173 Aubiere France

In 2005, Demange and Paschos proposed in [M. Demange, ***. Paschos, On-line vertex-covering, Theoret. Comput. Sci. 332 (2005) 83-108] an online algorithm (noted LR here) for the classical vertex cover problem. They shown that. for any graph of maximum degree Delta, LR constructs a vertex cover whose size is at most Delta times the optimal one (this bound is tight in the worst case). Very recently, two of the present authors have shown in [F. Delbot, C. Laforest, A better list heuristic for vertex cover, Inform. Process. Lett. 107 (2008) 125-127] that LR has interesting properties (it is a good "list algorithm" and it can easily be distributed). In addition, LR has good experimental behavior in spite of its 6 approximation (or competitive) ratio and the fact that it can be executed without the knowledge of the full instance at the beginning. In this paper we analyze it deeper and we show that LR has good "average" performances: we prove that its mean approximation ratio is strictly less than 2 for any graph and is equal to 1 + e(-2) approximate to 1.13 in paths. LR is then a very interesting algorithm for constructing small vertex covers, despite its bad worst case behavior. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Graphs Vertex cover approximation algorithm Mean analysis On-line algorithm

来源：评论

学校读者我要写书评

暂无评论

A note on the subadditive network design problem

引用

OPERATIONS RESEARCH LETTERS 2009年第5期37卷 339-344页

作者： Bateni, M. Hajiaghayi, M. Princeton Univ Dept Comp Sci Princeton NJ 08540 USA AT&T Labs Res Florham Pk NJ 07932 USA

We study approximation algorithms for generalized network design where the cost of an edge depends on the identities of the demands using it (as a monotone subadditive function). Our main result is that even a very special case of this problem cannot be approximated to within a factor 2log(1-epsilon vertical bar D vertical bar) if D is the set of demands. (C) 2009 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Network design Hardness of approximation Subadditive cost function

来源：评论

学校读者我要写书评

暂无评论

Approximating the maximum 2-and 3-edge-colorable subgraph problems

引用

DISCRETE APPLIED MATHEMATICS 2009年第17期157卷 3593-3600页

作者： Kosowski, Adrian Gdansk Univ Technol Dept Algorithms & Syst Modeling PL-80952 Gdansk Poland

For a fixed value of a parameter k >= 2, the Maximum k-Edge-Colorable Subgraph Problem consists in finding k edge-disjoint matchings in a simple graph, with the goal of maximising the total number of edges used. The problem is known to be APX-hard for all k, but there exist polynomial time approximation algorithms with approximation ratios tending to 1 as k tends to infinity. Herein we propose improved approximation algorithms for the cases of k = 2 and k = 3, having approximation ratios of 5/6 and 4/5, respectively. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Edge coloring of graphs k-edge-colorable subgraph problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Single-source k-splittable min-cost flows

引用

OPERATIONS RESEARCH LETTERS 2009年第2期37卷 71-74页

作者： Salazar, Fernanda Skutella, Martin Tech Univ Berlin Inst Math D-10623 Berlin Germany Escuela Politec Nacl Dept Matemat Quito Ecuador

Motivated by a famous open question on the single-source unsplittable minimum cost flow problem, we present a new approximation result for the relaxation of the problem where, for a given number k, each commodity must... 详细信息

关键词： approximation algorithm Multi-commodity flow Network flow Routing Unsplittable now k-splittable flow

来源：评论

学校读者我要写书评

暂无评论

Approximating optimum branchings in linear time

引用

INFORMATION PROCESSING LETTERS 2009年第3期109卷 175-178页

作者： Ziegler, Valentin Humboldt Univ Inst Informat D-10099 Berlin Germany

We prove that maximum weight branchings in directed graphs can be approximated in time O(m) tip to a factor of 1 - epsilon. where epsilon > 0 is an arbitrary constant. (C) 2008 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Graph algorithm Branching

来源：评论

学校读者我要写书评

暂无评论

Stochastic Combinatorial Optimization with Controllable Risk Aversion Level

引用

MATHEMATICS OF OPERATIONS RESEARCH 2009年第3期34卷 522-537页

作者： So, Anthony Man-Cho Zhang, Jiawei Ye, Yinyu Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China New York Univ Dept Informat Operat & Management Sci Stern Sch Business New York NY 10012 USA Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

Most of the recent work on 2-stage stochastic combinatorial optimization problems has focused on minimization of the expected cost or the worst-case cost of the solution. Those two objectives can be viewed as two extreme ways of handling risk. In this paper we propose to use a one-parameter family of functionals to interpolate between them. Although such a family has been used in the mathematical finance and stochastic programming literature before, its use in the context of approximation algorithms seems new. We show that under standard assumptions, a broad class of risk-adjusted 2-stage stochastic programs can be efficiently treated by the sample average approximation (SAA) method. In particular, our result shows that it is computationally feasible to incorporate some degree of robustness even when the underlying distribution can only be accessed in a black-box fashion. We also show that when combined with suitable rounding procedures, our result yields new approximation algorithms for many risk-adjusted 2-stage stochastic combinatorial optimization problems under the black-box setting.

关键词： stochastic optimization risk measure sample average approximation (SAA) approximation algorithm combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

On the approximability of the Maximum Agreement SubTree and Maximum Compatible Tree problems

引用

DISCRETE APPLIED MATHEMATICS 2009年第7期157卷 1555-1570页

作者： Guillemot, Sylvain Nicolas, Francois Berry, Vincent Paul, Christophe Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland Univ Montpellier 2 CNRS LIRMM F-34392 Montpellier France Univ Lille 1 INRIA CNRS LIFL F-59655 Villeneuve Dascq France

The aim of this paper is to give a complete picture of approximability for two tree consensus problems which are of particular interest in computational biology: MAXIMUM AGREEMENT SUBTREE (MAST) and MAXIMUM COMPATIBLE TREE (MCT). Both problems take as input a label set and a collection of trees whose leaf sets are each bijectively labeled with the label set. Define the size of a tree as the number of its leaves. The well-known MAST problem consists of finding a maximum-sized tree that is topologically embedded in each input tree, under label-preserving embeddings. Its variant MCT is less stringent, as it allows the input trees to be arbitrarily refined. Our results are as follows. We show that MCT is NP-hard to approximate within bound n(1-epsilon) on rooted trees, where n denotes the size of each input tree;the same approximation lower bound was already known for MAST [J. Jansson, Consensus algorithms for trees and strings, Ph. D. Thesis, Lund University, 2003]. Furthermore, we prove that MCT on two rooted trees is not approximable within bound 2(log1-epsilon) (n), unless all problems in NP are solvable in quasi-polynomial time;the same result was previously established for MAST on three rooted trees [J. Hein, T. Jiang, L. Wang, K. Zhang, On the complexity of comparing evolutionary trees, Discrete Applied Mathematics 71 (1-3) (1996) 153-169] (note that MAST on two trees is solvable in polynomial time [MA Steel, T.J. Warnow, Kaikoura tree theorems: Computing the maximum agreement subtree, information Processing Letters 48 (2) (1993) 77-82]). Let CMAST, resp. CMCT, denote the complement version of MAST, resp. MCT: CMAST, resp. CMCT, consists of finding a tree that is a feasible solution of MAST, resp. MCT, and whose leaf label set excludes a smallest subset of the input labels. The approximation threshold for CMAST, resp. CMCT, on rooted trees is shown to be the same as the approximation threshold for CMAST, resp. CMCT, on unrooted trees;it was already known that bot

关键词： Computational biology Phylogenetics Consensus tree approximation algorithm approximation hardness Maximum agreement subtree Maximum compatible tree Maximum refinement subtree Complement problem Maximum star-forest Minimum dominating set Maximum independent set

来源：评论

学校读者我要写书评

暂无评论

Minimum Weakly Fundamental Cycle Bases Are Hard To Find

引用

algorithmICA 2009年第3期53卷 402-424页

作者： Rizzi, Romeo Univ Udine Fac Ingn Dipartimento Matemat & Informat I-33100 Udine Italy

In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiry. At present, the complexity status of the MCB problem is settled only for undirected, directed, and strictly fundamental cycle bases (SFCB's). Weakly fundamental cycle bases (WFCB's) form a natural superclass of SFCB's. A cycle basis C = {C-1, C-2, ... , C-nu} of a graph G is a WFCB iff nu = 0 or there exists an edge e of G and a circuit C-i in C such that C \ C-i is a WFCB of G \ e. WFCB's still possess several of the nice properties offered by SFCB's. At the same time, several classes of graphs enjoying WFCB's of cost asymptotically inferior to the cost of the cheapest SFCB's have been found and exhibited in the literature. Considered also the computational difficulty of finding cheap SFCB's, these works advocated an in-depth study of WFCB's. In this paper, we settle the complexity status of the MCB problem for WFCB's (the MWFCB problem). The problem turns out to be APX-hard. However, in this paper, we also offer a simple and practical 2inverted right perpendicularlog(2) ninverted left perpendicular-approximation algorithm for the MWFCB problem. In O(n nu) time, this algorithm actually returns a WFCB whose cost is at most 2inverted right perpendicularlog(2)ninverted left perpendicular Sigma(e is an element of E(G)) w(e), thus allowing a fast 2inverted right perpendicularlog(2)ninverted left perpendicular-approximation also for the MCB problem. With this algorithm, we provide tight bounds on the cost of any MCB and MWFCB.

关键词： Graphs Combinatorial optimization Minimum cycle basis problem Weakly fundamental cycle basis Fundamental cycle basis approximation algorithm Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Cost Minimization in Wireless Networks with a Bounded and Unbounded Number of Interfaces

引用

NETWORKS 2009年第3期53卷 266-275页

作者： Klasing, Ralf Kosowski, Adrian Navarra, Alfredo Univ Bordeaux 1 CNRS LaBRI F-33405 Talence France Gdansk Univ Technol Dept Algorithms & Syst Modeling PL-80952 Gdansk Poland Univ Perugia Dipartimento Matemat & Informat I-06123 Perugia Italy

Given a graph G = (V, E) with |V| = n and |E| = m, which models a set of wireless devices (nodes V) connected by multiple radio interfaces (edges E),the aim is to switch on the minimum cost set of interfaces at the nodes to satisfy all the connections. A connection is satisfied when the endpoints of the corresponding edge share at least one active interface. Every node holds a subset of all the possible k interfaces. Depending on whether k is a priori bounded or not, the problem is called Cost Minimization in Multi-Interface Networks or Cost Minimization in Unbounded Multi-interface Networks, respectively. We distinguish two main variations for both problems by treating the cost of maintaining an active interface as uniform (i.e., the same for all interfaces), or nonuniform. For bounded k, we show that the problem is APX-hard while we obtain an approximation factor of min{[k+1/2], 2m/n} for the uniform case and a (k - 1)- approximation for the nonuniform case. For unbounded k, i.e., k is not set a priori but depends on the given instance, we prove that the problem is not approximable within O(log k) while the same approximation factor of the k-bounded case holds in the uniform case, and a min(k - 1, root n(1 + In n)}-approximation factor holds for the nonuniform case. Next, we also provide hardness and approximation results for several classes of networks: with bounded degree, trees, planar, and complete graphs. (C) 2008 Wiley Periodicals, Inc. NETWORKS, Vol. 53(3), 266-275 2009

关键词： cost minimization energy saving wireless network multi-interface network approximation algorithm inapproximability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：