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

On the Maximum Quadratic Assignment Problem

MATHEMATICS OF OPERATIONS RESEARCH 2009年第4期34卷 859-868页

作者： Nagarajan, Viswanath Sviridenko, Maxim IBM Corp TJ Watson Res Ctr Yorktown Hts NY 10598 USA

Quadratic assignment is a basic problem in combinatorial optimization that generalizes several other problems such as traveling salesman, linear arrangement, dense k subgraph, and clustering with given sizes. The input to the quadratic assignment problem consists of two n x n symmetric nonnegative matrices W = (w(i,j)) and D = (d(i,j)). Given matrices W, D, and a permutation pi: [n] -> [n], the objective function is Q(pi) := Sigma(i,j is an element of[n], i not equal j) w(i,j) . d(pi(i), pi(j)). In this paper, we study the maximum quadratic assignment problem, where the goal is to find a permutation pi that maximizes Q(pi). We give an (O) over tilde (root n)-approximation algorithm, which is the first nontrivial approximation guarantee for this problem. The above guarantee also holds when the matrices W, D are asymmetric. An indication of the hardness of maximum quadratic assignment is that it contains as a special case the dense k subgraph problem, for which the best-known approximation ratio is approximate to n(1/3) (Feige et al. [Feige, U., G. Kortsarz, D. Peleg. 2001. The dense k-subgraph problem. Algorithmica 29(3) 410-421]). When one of the matrices W, D satisfies triangle inequality, we obtain a 2e/(e-1) approximate to 3.16-approximation algorithm. This improves over the previously best-known approximation guarantee of four (Arkin et al. [Arkin, E. M., R. Hassin, M. Sviridenko. 2001. Approximating the maximum quadratic assignment problem. Inform. Processing Lett. 77 13-16]) for this special case of maximum quadratic assignment. The performance guarantee for maximum quadratic assignment with triangle inequality can be proved relative to an optimal solution of a natural linear programming relaxation that has been used earlier in branch-and-bound approaches (see, eg., Adams and Johnson [Adams, W. P., T. A. Johnson. 1994. Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 16 43-77]

关键词： approximation algorithms linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

A cross-monotonic cost sharing method for the facility location game with service installation costs

引用

Science China Mathematics 2009年第11期52卷 2530-2536页

作者： XU DaChuan Department of Applied Mathematics,Beijing University of Technology,Beijing 100124,China Department of Applied Mathematics Beijing University of Technology Beijing China

In this paper,we consider the metric uncapacitated facility location game with service installation costs. Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the install... 详细信息

关键词： facility location game cross-monotonic cost-sharing method linear programming relaxation 90C27 91A12

来源：评论

学校读者我要写书评

暂无评论

linear programming relaxations and marginal productivity index policies for the buffer sharing problem

引用

QUEUEING SYSTEMS 2008年第3-4期60卷 247-269页

作者： Cao, Jianhua Nyberg, Christian Lund Univ Elect & Informat Technol Dept S-22100 Lund Sweden

We study the dynamic admission control for a finite shared buffer with support of multiclass traffic under Markovian assumptions. The problem is often referred to as buffer sharing in the literature. From the linear programming (LP) formulation of the continuous-time Markov decision process (MDP), we construct a hierarchy of increasingly stronger LP relaxations where the hierarchy levels equal the number of job classes. Each relaxation in the hierarchy is obtained by projecting the original achievable performance region onto a polytope of simpler structure. We propose a heuristic policy for admission control, which is based on the theory of Marginal Productivity Index (MPI) and the Lagrangian decomposition of the first order LP relaxation. The dual of the relaxed buffer space constraint in the first order LP relaxation is used as a proxy to the cost of buffer space. Given that each of the decomposed queueing admission control problems satisfies the indexability condition, the proposed heuristic accepts a new arrival if there is enough buffer space left and the MPI of the current job class is greater than the incurred cost of buffer usage. Our numerical examples for the cases of two and eight job classes show the near-optimal performance of the proposed MPI heuristic.

关键词： Buffer sharing problem Multi-class queueing system linear programming relaxation Marginal productivity index policy Markov decision process 60K25 60K30 68M20 90B05 90B22 90B18 90C08 90C40 90C59

来源：评论

学校读者我要写书评

暂无评论

Sherali-Adams relaxations of the Matching Polytope

Sherali-Adams Relaxations of the Matching Polytope

引用

41st Annual ACM Symposium on Theory of Computing

作者： Mathieu, Claire Sinclair, Alistair Brown Univ Dept Comp Sci Providence RI 02912 USA

ISBN: (纸本)9781605586137

We study the Sherali-Adams lift-and-project hierarchy of linear programming relaxations of the matching polytope. Our main result is an asymptotically tight expression 1 + 1/k for the integrality gap after k rounds., of this hierarchy. The result is derived by a detailed analysis of the LP after k round applied to the complete graph K2d+1. We give an explicit recurrence for the value of this LP, and hence show that it's gap exhibits a "phase transition," dropping front close to its maximum value 1 + 1/2d to close to 1 around the threshold k = 2d - Theta(root d). we also show that the rank of the matching polytope (i.e., the number of Sherali-Adams rounds until the integer polytope is reached) is exactly 2d - 1.

关键词： 0-1 programming linear programming relaxation integrality gap lift-and-project matching polytope maximum matching

来源：评论

学校读者我要写书评

暂无评论

The multi-weighted Steiner tree problem: A reformulation by intersection

引用

COMPUTERS & OPERATIONS RESEARCH 2008年第11期35卷 3599-3611页

作者： Gouveia, Luis Telhada, Joao Univ Lisbon Fac Ciencias DEIO CIO P-1649016 Lisbon Portugal

We propose a new formulation for the multi-weighted Steiner tree (MWST) problem. This formulation is based on the fact that a previously proposed formulation for the problem is non-symmetric in the sense that the corresponding linear programming relaxation bounds depend on the node selected as a root of the tree. The new formulation (the reformulation by intersection) is obtained by intersecting the feasible sets of the models corresponding to each possible root selection for the underlying directed problem. Theoretical results will show that the linear programming relaxation of the new formulation dominates the linear programming relaxation of each of the rooted formulations and is comparable with the linear programming bounds of the best formulation known for the problem. A Lagrangean relaxation scheme derived from the new formulation is also proposed and tested, with quite favourable results, on instances with up to 500 nodes and 5000 edges. (c) 2007 Elsevier Ltd. All rights reserved.

关键词： network design spanning trees and Steiner trees linear programming relaxation reformulation techniques Lagrangean relaxation

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithm for facility location with service installation costs

引用

OPERATIONS RESEARCH LETTERS 2008年第1期36卷 46-50页

作者： Xu, Dachuan Zhang, Shuzhong Beijing Univ Technol Dept Appl Math Beijing 100022 Peoples R China Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China

In this paper, we study the uncapacitated facility location problem with service installation costs depending on the type of service required. We propose a polynomial-time approximation algorithm with approximation ratio 1.808 which improves the previous approximation ratio of 2.391 of Shmoys, Swamy, and Levi. (c) 2007 Elsevier B.V. All rights reserved.

关键词： facility location approximation algorithm linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Minimizing the Stabbing Number of Matchings, Trees, and Triangulations

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2008年第4期40卷 595-621页

作者： Fekete, Sandor P. Luebbecke, Marco E. Meijer, Henk Tech Univ Carolo Wilhelmina Braunschweig Dept Comp Sci Algorithms Grp D-38106 Braunschweig Germany Tech Univ Berlin Inst Math D-10623 Berlin Germany Roosevelt Acad Dept Sci Middelburg ZL Netherlands

The (axis-parallel) stabbing number of a given set of line segments is the maximum number of segments that can be intersected by any one (axis-parallel) line. This paper deals with finding perfect matchings, spanning trees, or triangulations of minimum stabbing number for a given set of vertices. The complexity of finding a spanning tree of minimum stabbing number is one of the original 30 questions on "The Open Problems Project" list of outstanding problems in computational geometry by Demaine, Mitchell, and O'Rourke. We show NP-hardness of stabbing problems by means of a general proof technique. For matchings, this also implies a nontrivial lower bound on the approximability. On the positive side, we propose a cut-based integer programming formulation for minimizing the stabbing number of matchings and spanning trees. From the corresponding linear programming relaxation we obtain polynomial-time lower bounds and show that there always is an optimal fractional solution that contains an edge of at least constant weight. We conjecture that the resulting iterated rounding scheme constitutes a constant-factor approximation algorithm.

关键词： Stabbing number Matching Spanning tree Triangulation Complexity linear programming relaxation Iterated rounding

来源：评论

学校读者我要写书评

暂无评论

INTEGRALITY RATIO FOR GROUP STEINER TREES AND DIRECTED STEINER TREES

引用

SIAM JOURNAL ON COMPUTING 2007年第5期36卷 1494-1511页

作者： Halperin, Eran Kortsarz, Guy Krauthgamer, Robert Srinivasan, Aravind Wang, Nan Int Comp Sci Inst Berkeley CA 94704 USA Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA Rutgers State Univ Dept Comp Sci Camden NJ 08102 USA IBM Almaden Res Ctr San Jose CA 95120 USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA Morgan Stanley Inc New York NY 10020 USA

The natural relaxation for the group Steiner tree problem, as well as for its generalization, the directed Steiner tree problem, is a flow-based linear programming relaxation. We prove new lower bounds on the integrality ratio of this relaxation. For the group Steiner tree problem, we show that the integrality ratio is Omega(log(2) k), where k denotes the number of groups;this holds even for input graphs that are hierarchically well-separated trees, introduced by Bartal [in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, pp. 184-193], in which case this lower bound is tight. This also applies for the directed Steiner tree problem. In terms of the number n of vertices, our results for the directed Steiner problem imply an Omega(log(2) n/(log log n)(2)) integrality ratio. For both problems, these are the first lower bounds on the integrality ratio that are superlogarithmic in the input size. This exhibits, for the first time, a relaxation of a natural optimization problem whose integrality ratio is known to be superlogarithmic but subpolynomial. Our results and techniques have been used by Halperin and Krauthgamer [in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585-594] to show comparable inapproximability results, assuming that NP has no quasi-polynomial Las Vegas algorithms. We also show algorithmically that the integrality ratio for the group Steiner tree problem is much better for certain families of instances, which helps pinpoint the types of instances (parametrized by optimal solutions to their flow-based relaxations) that appear to be most difficult to approximate.

关键词： group Steiner tree directed Steiner tree flow-based relaxation linear programming relaxation integrality ratio approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for network design with metric costs

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2007年第3期21卷 612-636页

作者： Cheriyan, Joseph Vetta, Adrian Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada McGill Univ Sch Comp Sci Dept Math & Stat Montreal PQ H3A 2A7 Canada

We study undirected networks with edge costs that satisfy the triangle inequality. Let n denote the number of nodes. We present an O(1)-approximation algorithm for a generalization of the metric-cost subset k-node-connectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. A corollary is that, for metric costs and for each k = 1, 2,..., n - 1, there exists a k-node connected graph whose cost is within a factor of 22 of the cost of any simple k-edge connected graph. Based on our O( 1)- approximation algorithm, we present an O(log r(max))-approximation algorithm for the metric-cost node-connectivity survivable network design problem, where rmax denotes the maximum requirement over all pairs of nodes. Our results contrast with the case of edge costs of 0 or 1, where Kortsarz, Krauthgamer, and Lee. [SIAM J. Comput., 33 (2004), pp. 704-720] recently proved, assuming NP not subset of DTIME(n(polylog(n))), a hardness-of-approximation lower bound of 2(log1-epsilon) (n) for the subset k-node-connectivity problem, where epsilon denotes a small positive number.

关键词： approximation algorithm linear programming relaxation network design vertex-connectivity edge-connectivity

来源：评论

学校读者我要写书评

暂无评论

A linear programming approach to max-sum problem: A review

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2007年第7期29卷 1165-1179页

作者： Werner, Tomas Czech Tech Univ Fac Elect Engn Dept Cybernet Prague Czech Republic

The max-sum labeling problem, defined as maximizing a sum of binary (i.e., pairwise) functions of discrete variables, is a general NP-hard optimization problem with many applications, such as computing the MAP configuration of a Markov random field. We review a not widely known approach to the problem, developed by Ukrainian researchers Schlesinger et al. in 1976, and show how it contributes to recent results, most importantly, those on the convex combination of trees and tree-reweighted max-product. In particular, we review Schlesinger et al.' s upper bound on the max-sum criterion, its minimization by equivalent transformations, its relation to the constraint satisfaction problem, the fact that this minimization is dual to a linear programming relaxation of the original problem, and the three kinds of consistency necessary for optimality of the upper bound. We revisit problems with Boolean variables and supermodular problems. We describe two algorithms for decreasing the upper bound. We present an example application for structural image analysis.

关键词： Markov random fields undirected graphical models constraint satisfaction belief propagation linear programming relaxation max-sum max-plus max-product supermodular optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：