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

DISCRETE APPLIED MATHEMATICS 2012年第4-5期160卷 494-504页

作者： Cygan, Marek Pilipczuk, Marcin Univ Warsaw Fac Math Comp Sci & Mech PL-02092 Warsaw Poland

In this paper we merge recent developments on exact algorithms for finding an ordering of vertices of a given graph that minimizes bandwidth (the BANDWIDTH problem) and for finding an embedding of a given graph into a line that minimizes distortion (the DISTORTION problem). For both problems we develop algorithms that work in O(9.363(n)) time and polynomial space. For BANDWIDTH, this improves O*(10(n)) algorithm by Feige and Kilian from 2000, for DISTORTION this is the first polynomial space exact algorithm that works in O(c(n)) time we are aware of. As a byproduct, we enhance the O(5(n+o(n)))-time and O*(2(n))-space algorithm for DISTORTION by Fomin et al. to an algorithm working in O(4.383(n))-time and space. (c) 2011 Elsevier B.V. All rights reserved.

关键词： Bandwidth Distortion exact algorithms Exponential algorithms

来源：评论

学校读者我要写书评

暂无评论

Research trends in combinatorial optimization

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2022年第2期29卷 667-705页

作者： Weinand, Jann Michael Sorensen, Kenneth San Segundo, Pablo Kleinebrahm, Max McKenna, Russell Karlsruhe Inst Technol Inst Ind Prod Chair Energy Econ D-76131 Karlsruhe Germany Univ Antwerp Dept Engn Management B-2000 Antwerp Belgium Univ Politecn Madrid Ctr Automat & Robot Madrid 28040 Spain Univ Aberdeen Sch Engn Chair Energy Transit Aberdeen AB24 3FX Scotland

Real-world problems are becoming highly complex and therefore have to be solved with combinatorial optimization (CO) techniques. Motivated by the strong increase in publications on CO, 8393 articles from this research field are subjected to a bibliometric analysis. The corpus of literature is examined using mathematical methods and a novel algorithm for keyword analysis. In addition to the most relevant countries, organizations, and authors as well as their collaborations, the most pertinent CO problems, solution methods, and application areas are presented. Publications on CO focus mainly on the development or enhancement of metaheuristics like genetic algorithms. The increasingly problem-oriented studies deal particularly with real-world applications within the energy sector, production sector, or data management, which are of increasing relevance due to various global developments. The demonstration of global research trends in CO can support researchers in identifying the relevant issues regarding this expanding and transforming research area.

关键词： combinatorial optimization bibliometric analysis metaheuristics genetic algorithms exact algorithms OR in energy

来源：评论

学校读者我要写书评

暂无评论

Models, relaxations and exact approaches for the capacitated vehicle routing problem

引用

DISCRETE APPLIED MATHEMATICS 2002年第1-3期123卷 487-512页

作者： Toth, P Vigo, D Univ Bologna Dipartimento Elettron Informat & Sistemist I-40136 Bologna Italy

In this paper we review the exact algorithms based on the branch and bound approach proposed in the last years for the solution of the basic version of the vehicle routing problem (VRP), where only the vehicle capacity constraints are considered. These algorithms have considerably increased the size of VRPs that can be solved with respect to earlier approaches. Moreover, at least for the case in which the cost matrix is asymmetric, branch and bound algorithms still represent the state-of-the-art with respect to the exact solution. Computational results comparing the performance of different relaxations and algorithms on a set of benchmark instances are presented. We conclude by examining possible future directions of research in this field. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： vehicle routing problem exact algorithms branch and bound relaxations

来源：评论

学校读者我要写书评

暂无评论

Floating Steiner trees

引用

IEEE TRANSACTIONS ON COMPUTERS 1998年第2期47卷 197-211页

作者： Sarrafzadeh, M Lin, WL Wong, CK Northwestern Univ Dept Elect & Comp Engn Evanston IL 60208 USA Intel Corp Hillsboro OR 97124 USA Chinese Univ Hong Kong Dept Comp Sci Shatin Hong Kong

We study the reproducing placement problem, which finds application in layout-driven logic synthesis. In each phase, a module (or gate) is decomposed into two (or more) simpler modules. The goal is to find a "good" placement in each phase. The problem, being iterative in nature, requires an iterative algorithm. In solving the RPP, we introduce the notion of minimum floating Steiner trees (MFST). We employ an MFST algorithm as a central step in solving the RPP. A Hanan-like theorem is established for the MFST problem, and two approximation algorithms are proposed. Experiments on commonly employed benchmarks verify the effectiveness of the proposed technique.

关键词： Steiner trees exact algorithms optimization placement problem gate level design

来源：评论

学校读者我要写书评

暂无评论

On parameterized exponential time complexity

引用

THEORETICAL COMPUTER SCIENCE 2009年第27-29期410卷 2641-2648页

作者： Chen, Jianer Kanj, Iyad A. Xia, Ge Lafayette Coll Dept Comp Sci Easton PA 18042 USA Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Depaul Univ Sch Comp Chicago IL 60604 USA

In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2(o(f(k)))p(n) time if and only if it is solvable in time O(2(delta f(k))q(n)) for any constant delta>0, where p and q are polynomials. We then illustrate how this equivalence can be used to show that special instances of parameterized NP-hard problems are as difficult as the general instances. For example, we show that the PLANAR DOMINATING SET problem on degree-3 graphs can be solved in 2(0(root k))p(n) parameterized time if and only if the general PLANAR DOMINATING SET problem can. Apart from their complexity theoretic implications, our results have some interesting algorithmic implications as well. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Parameterized complexity Subexponential time complexity Parameterized algorithms exact algorithms

来源：评论

学校读者我要写书评

暂无评论

A MORE RELAXED MODEL FOR GRAPH-BASED DATA CLUSTERING: s-PLEX CLUSTER EDITING

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2010年第4期24卷 1662-1683页

作者： Guo, Jiong Komusiewicz, Christian Niedermeier, Rolf Uhlmann, Johannes Univ Saarland D-66123 Saarbrucken Germany Univ Jena Inst Informat D-07743 Jena Germany

We introduce the s-Plex Cluster Editing problem as a generalization of the well-studied Cluster Editing problem;both are NP-hard and both are motivated by graph-based data clustering. Instead of transforming a given graph by a minimum number of edge modifications into a disjoint union of cliques (this is Cluster Editing), the task in the case of s-Plex Cluster Editing is to transform a graph into a cluster graph consisting of a disjoint union of so-called s-plexes. Herein, an s-plex is a vertex set S inducing a subgraph in which every vertex has degree at least vertical bar S vertical bar - s. Cliques are 1-plexes. The advantage of s-plexes for s >= 2 is that they allow us to model a more relaxed cluster notion (s-plexes instead of cliques), better reflecting inaccuracies of the input data. We develop a provably effective preprocessing based on data reduction (yielding a so-called problem kernel), a forbidden subgraph characterization of s-plex cluster graphs, and a depth-bounded search tree which is used to find optimal edge modification sets. Altogether, this yields efficient algorithms in case of moderate numbers of edge modifications;this is often a reasonable assumption under a maximum parsimony model for data clustering.

关键词： NP-hard problems exact algorithms fixed-parameter tractability data reduction graph modification k-plex dense subgraphs forbidden subgraph characterization

来源：评论

学校读者我要写书评

暂无评论

Optimal placement of multiple types of detectors under a small vessel attack threat to port security

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2016年 93卷 71-94页

作者： Yan, Xihong Nie, Xiaofeng Taiyuan Normal Univ Higher Educ Key Lab Engn & Sci Comp Taiyuan 030012 Peoples R China Nanyang Technol Univ Sch Mech & Aerosp Engn Singapore 639798 Singapore

We focus on a threat scenario where a terrorist would utilize a small vessel to attack a maritime target. We consider how to place multiple types of detectors to protect maritime targets from such an attack. Detectors are not perfectly reliable. The resulting detector placement problem is formulated as a nonlinear binary integer program such that the expected damage cost caused by the small vessel attack is minimized. Two exact algorithms and a greedy adding heuristic are proposed. Moreover, we conduct a detailed computational study and provide a case study in New York Harbor. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Port security Small vessel attack Detector deployment exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards effective exact methods for the Maximum Balanced Biclique Problem in bipartite graphs

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第3期269卷 834-843页

作者： Zhou, Yi Rossi, Andre Hao, Jin-Kao Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 617731 Sichuan Peoples R China Univ Angers LERIA 2 Bd Lavoisier F-49045 Angers France Inst Univ France 1 Rue Descartes F-75231 Paris France

The Maximum Balanced Biclique Problem (MBBP) is a prominent model with numerous applications. Yet. the problem is NP-hard and thus computationally challenging. We propose novel ideas for designing effective exact algorithms for MBBP in bipartite graphs. First, an Upper Bound Propagation (UBP) procedure to pre-compute an upper bound involving each vertex is introduced. Then we extend a simple Branchand-Bound (B&B) algorithm by integrating the pre-computed upper bounds. Based on UBP, we also study a new integer linear programming model of MBBP which is more compact than an existing formulation (Dawande, Keskinocak, Swaminathan, & Tayur, 2001). We introduce new valid inequalities induced from the upper bounds to tighten these mathematical formulations for MBBP. Experiments with random bipartite graphs demonstrate the efficiency of the extended B&B algorithm and the valid inequalities generated on demand. Further tests with 30 real-life instances show that, for at least three very large graphs, the new approaches improve the computational time with four orders of magnitude compared to the original B&B. (C) 2018 E(C)sevier B.V. All rights reserved.

关键词： Combinatorial optimization Clique exact algorithms Techniques for tight bounds Mathematical formulation

来源：评论

学校读者我要写书评

暂无评论

On soft predicates in subdivision motion planning

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2015年第8期48卷 589-605页

作者： Wang, Cong Chiang, Yi-Jen Yap, Chee NYU Polytech Sch Engn Dept Comp Sci & Engn Brooklyn NY 11201 USA NYU Dept Comp Sci New York NY USA

We propose to design new algorithms for motion planning problems using the well-known Domain Subdivision paradigm, coupled with "soft" predicates. Unlike the traditional exact predicates in computational geometry, our primitives are only exact in the limit. We introduce the notion of resolution-exact algorithms in motion planning: such an algorithm has an "accuracy" constant K > 1, and takes an arbitrary input "resolution" parameter epsilon > 0 such that: if there is a path with clearance K epsilon, it will output a path with clearance epsilon/K;if there are no paths with clearance epsilon/K, it reports "NO PATH". Besides the focus on soft predicates, our framework also admits a variety of global search strategies including forms of the A* search and probabilistic search. Our algorithms are theoretically sound, practical, easy to implement, without implementation gaps, and have adaptive complexity. Our deterministic and probabilistic strategies avoid the Halting Problem of current probabilistically complete algorithms. We develop the first provably resolution-exact algorithms for motion-planning problems in SE(2) = R-2 x S-1. To validate this approach, we implement our algorithms and the experiments demonstrate the efficiency of our approach, even compared to probabilistic algorithms. (C) 2015 Elsevier B.V. All rights reserved.

关键词： exact algorithms Subdivision algorithms Motion planning Soft predicates Resolution-exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing Tree-Depth Faster Than 2ⁿ

引用

ALGORITHMICA 2015年第1期73卷 202-216页

作者： Fomin, Fedor V. Giannopoulou, Archontia C. Pilipczuk, Michal Univ Bergen Dept Informat N-5020 Bergen Norway

A connected graph has tree-depth at most if it is a subgraph of the closure of a rooted tree whose height is at most . We give an algorithm which for a given -vertex graph , in time computes the tree-depth of . Our al... 详细信息

关键词： exact algorithms Tree-depth 2(n) Barrier

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：