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

A survey on multi-constrained optimal path computation exact and approximate algorithms

COMPUTER NETWORKS 2010年第17期54卷 3081-3107页

作者： Garroppo, Rosario G. Giordano, Stefano Tavanti, Luca Univ Pisa Dip Ingn Informaz I-56122 Pisa Italy

The paper presents a survey on the techniques to solve the multi-constrained optimal path (MCOP) problem Computing the MCOP is a task shared by many research areas from transportation systems to telecommunication networks In the latter the MCOP is often related to the issue of Quality of Service (QoS) routing which consists in finding a route between a couple of nodes that meets a series of QoS requirements such as bounded delay pack et loss and other parameters The MCOP problem has been faced by several authors and a plethora of solving methods is now available In the present work we draw the state of the art of exact and approximate MCOP computation algorithms with particular attention to the networking area We describe and analyse the most representative methods and for each of them we derive the worst case computational complexity In addition we provide the reader with a uniform notation and with the detailed pseudo-code of various algorithms so that the paper can indeed serve as a workable starting point for further studies on the MCOP problem (C) 2010 Elsevier B V All rights reserved

关键词： Multi Constrained Optimal Path (MCOP) Multi Objective Optimal Path (MOOP) Multi Constrained Path (MCP) Restricted Shortest Path (RSP) Quality of Service (QoS) Routing exact algorithms Approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

exact and approximation algorithms for weighted matroid intersection

引用

MATHEMATICAL PROGRAMMING 2019年第1-2期177卷 85-112页

作者： Huang, Chien-Chung Kakimura, Naonori Kamiyama, Naoyuki PSL Ecole Normale Super CNRS Paris France Keio Univ Dept Math Yokohama Kanagawa Japan Kyushu Univ Inst Math Ind Fukuoka Fukuoka Japan

In this paper, we propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a (1-E)-approximate solution with a running time significantly faster than most known exact algorithms. The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. More precisely, we show that we can solve the weighted matroid intersection problem via solving W instances of the unweighted matroid intersection problem, where W is the largest given weight, assuming that all given weights are integral. Furthermore, we can find a (1-E)-approximate solution via solving O(E-1logr) instances of the unweighted matroid intersection problem, where r is the smaller rank of the two given matroids. Our algorithms make use of the weight-splitting approach of Frank (J algorithms 2(4):328-336, 1981) and the geometric scaling scheme of Duan and Pettie (J ACM 61(1):1, 2014). Our algorithms are simple and flexible: they can be adapted to special cases of the weighted matroid intersection problem, using specialized unweighted matroid intersection algorithms. In addition, we give a further application of our decomposition technique: we solve efficiently the rank-maximal matroid intersection problem, a problem motivated by matching problems under preferences.

关键词： Weighted matroid intersection exact algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A note on exact and heuristic algorithms for the identical parallel machine scheduling problem

引用

JOURNAL OF HEURISTICS 2012年第6期18卷 939-942页

作者： Dell'Amico, Mauro Iori, Manuel Martello, Silvano Monaci, Michele Univ Bologna DEIS I-40136 Bologna Italy Univ Modena & Reggio Emilia DISMI I-42122 Reggio Emilia Italy Univ Padua DEI I-35131 Padua Italy

A recent paper (Davidovic et al., J. Heuristics, 18:549-569, 2012) presented a bee colony metaheuristic for scheduling independent tasks to identical processors, evaluating its performance on a benchmark set of instances from the literature. We examine two exact algorithms from the literature, the former published in 1995, the latter in 2008 (and not cited by the authors). We show that both such algorithms solve to proven optimality all the considered instances in a computing time that is several orders of magnitude smaller than the time taken by the new algorithm to produce an approximate solution.

关键词： Identical parallel machine scheduling exact algorithms Metaheuristic algorithms

来源：评论

学校读者我要写书评

暂无评论

exact and Approximation algorithms for Geometric and Capacitated Set Cover Problems

引用

ALGORITHMICA 2012年第2期64卷 295-310页

作者： Berman, Piotr Karpinski, Marek Lingas, Andrzej Lund Univ Dept Comp Sci S-22100 Lund Sweden Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA Univ Bonn Dept Comp Sci Bonn Germany

First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time exact solutions. Next, we consider the following general (non-necessarily geometric) capacitated set cover problem. There is given a set of elements with real weights and a family of sets of the elements. One can use a set if it is a subset of one of the sets in the family and the sum of the weights of its elements is at most one. The goal is to cover all the elements with the allowed sets. We show that any polynomial-time algorithm that approximates the uncapacitated version of the set cover problem with ratio r can be converted to an approximation algorithm for the capacitated version with ratio r+1.357. In particular, the composition of these two results yields a polynomial-time approximation algorithm for the problem of covering a set of customers represented by a weighted n-point set with a minimum number of antennas of variable angular range and fixed capacity with ratio 2.357. This substantially improves on the best known approximation ratio for the latter antenna problem equal to 3. Furthermore, we provide a PTAS for the dual problem where the number of sets (e.g., antennas) to use is fixed and the task is to minimize the maximum set load, in case the sets correspond to line intervals or arcs. Finally, we discuss the approximability of the generalization of the antenna problem to include several base stations for antennas, and in particular show its APX-hardness already in the uncapacitated case.

关键词： Set cover Geometric set cover Capacitated set cover Assignment of directional antenna Shipping with deadlines Approximation algorithms Polynomial-time approximation scheme APX-hardness exact algorithms Time complexity

来源：评论

学校读者我要写书评

暂无评论

exact and Parameterized algorithms for the Independent Cutset Problem 24th

Exact and Parameterized Algorithms for the Independent Cutse...

引用

24th International Symposium on Fundamentals of Computation Theory (FCT)

作者： Rauch, Johannes Rautenbach, Dieter Souza, Ueverton S. Univ Ulm Inst Optimizat & Operat Res Ulm Germany Univ Fed Fluminense Inst Computacao Niteroi RJ Brazil

ISBN: (纸本)9783031435867;9783031435874

The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. Such a problem is NP-complete even when the input graph is planar and has maximum degree five. In this paper, we first present a O* (1.4423n)-time algorithm to compute a minimum independent cutset (if any). Since the property of having an independent cutset is MSO1-expressible, our main results are concerned with structural parameterizations for the problem considering parameters incomparable with clique-width. We present FPT-time algorithms for the problem considering the following parameters: the dual of the maximum degree, the dual of the solution size, the size of a dominating set (where a dominating set is given as an additional input), the size of an odd cycle transversal, the distance to chordal graphs, and the distance to P5-free graphs. We close by introducing the notion of a-domination, which allows us to identify more fixed-parameter tractable and polynomial-time solvable cases.

关键词： exact algorithms parameterized algorithms independent cutset

来源：评论

学校读者我要写书评

暂无评论

On exact and approximation algorithms for distinguishing substring selection

引用

14th International Symposium on Fundamentals of Computation Theory

作者： Gramm, J Guo, J Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

ISBN: (纸本)3540405437

The NP-complete DISTINGUISHING SUBSTRING SELECTION problem (DSSS for short) asks, given a set of "good" strings and a, set of "bad" strings, for a solution string which is, with respect to Hamming metric, "away" from the good strings and "close" to the bad strings. Studying the parameterized complexity of DSSS, we show that DSSS is W[1]-hard with respect to its natural parameters. This, in particular, implies that a recently given polynomial-time approximation scheme (PTAS) by Deng et al. cannot be replaced by a so-called efficient polynomial-time approximation scheme (EPTAS) unless an unlikely collapse in parameterized complexity theory occurs. By way of contrast, for a special case of DSSS, we present an exact fixed-parameter algorithm solving the problem efficiently. In this way, we exhibit a sharp border between fixed-parameter tractability and intractability results.

关键词： algorithms and complexity parameterized complexity approximation algorithms exact algorithms computational biology

来源：评论

学校读者我要写书评

暂无评论

exact AND APPROXIMATE algorithms FOR SCHEDULING NONIDENTICAL PROCESSORS

引用

JOURNAL OF THE ACM 1976年第2期23卷 317-327页

作者： HOROWITZ, E SAHNI, S UNIV SO CALIF PROGRAM COMP SCI LOS ANGELES CA 90007 USA UNIV MINNESOTA DEPT COMP INFORMATION & CONTROL SCI MINNEAPOLIS MN 55455 USA

exact and approximate algorithms are presented for scheduling independent tasks in a multiprocessor environment in which the processors have different speeds. Dynamic programming type algorithms are presented which minimize finish time and weighted mean flow time on two processors. The generalization to m processors is direct. These algorithms have a worst-case complexity which is exponential in the number of tasks. Therefore approximation algorithms of low polynomial complexity are also obtained for the above problems. These algorithms are guaranteed to obtain solutions that are close to the optimal. For the case of minimizing mean flow time on m-processors an algorithm is given whose complexity is O(n log mn).

关键词： approximate algorithm complexity exact algorithms finish time mean flow time scheduling independent tasks uniform processors unrelated processors weighted mean flow time

来源：评论

学校读者我要写书评

暂无评论

Two exact algorithms for the vehicle routing problem on trees

引用

Naval Research Logistics (NRL) 1999年第1期46卷

作者： Pontien Mbaraga André Langevin Gilbert Laporte Département de Mathématiques et de Génie Industriel École Polytechnique de Montréal Case Postale 6079 Succursale “Centre‐ville” Montréal H3C 3J7 Canada Centre de Recherche sur les Transports Université de Montréal Case Postale 6128 Succursale “Centre‐ville” Montréal H3C 3J7 Canada GERAD and École des Hautes Études Commerciales 3000 Chemin de la Côte‐Sainte‐Catherine Montréal H3T 2A7 Canada

This article describes a heuristic and two exact algorithms for several classes of vehicle routing problems defined on tree networks. These include capacitated and time‐constrained vehicle routing problems. One of the exact algorithms is based on the computation of bin packing lower bounds. The other uses column generation. The first algorithm performs better on problems containing small customer demands and in which all vehicles are identical. Otherwise, the second algorithm is more powerful and more versatile. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 75–89, 1999

关键词： vehicle routing problem on trees bin packing column generation exact algorithms heuristic

来源：评论

学校读者我要写书评

暂无评论

On the exact quantum query complexity of MOD and exact functions

引用

Frontiers of Computer Science 2025年第4期19卷 91-98页

作者： Penghui YAO Zekun YE State Key Laboratory for Novel Software Technology Nanjing UniversityNanjing 210023China Hefei National Laboratory Hefei 230088China

In this paper,we consider the exact quantum query complexity of two fundamental symmetric functions.1)MOD_(m)^(n),which calculates the Hamming weight of an-bit string modulo;2)exact_(k,l)^(n),which determines if the Hamming weight of an-bit string is exactly k or *** these two symmetric functions have received considerable attention,their exact quantum query complexities have not been fully ***,our results are as follows:1)We design an optimal quantum query algorithm to compute MOD_(m)^(n)exactly and thus provide a tight characterization of its exact quantum query complexity,which settles a previous *** on this algorithm,we demonstrate that a broad class of symmetric functions is not evasive in the quantum model,i.e.,there exist quantum algorithms to compute these functions exactly when the number of queries is less than their input size.2)By proposing a quantum algorithm that utilizes the minimum number of queries to compute exact_(k,l)^(n)exactly for some specific values of k and l,we give a tight characterization of its exact quantum query complexity in these scenarios.

关键词： quantum computing query complexity symmetric functions exact algorithms evasiveness

来源：评论

学校读者我要写书评

暂无评论

A model-based algorithm for the Probabilistic Orienteering Problem

引用

COMPUTERS & OPERATIONS RESEARCH 2025年 176卷

作者： Montemanni, Roberto Smith, Derek H. Univ Modena & Reggio Emilia Dept Sci & Methods Engn Via Amendola 2 I-42122 Reggio Emilia Italy Univ South Wales Comp & Math Pontypridd CF37 1DL Wales

The Orienteering Problem is a routing problem aiming at selecting a subset of a given set of customers to visited within a given time budget, so that a total revenue is maximized. Multiple variants of the problem have been studied. The Probabilistic Orienteering Problem is one of these variants, where customers will require visit according to a certain given probability. Stochasticity makes the model more practical, but concurrently more difficult to solve. Effective approaches to solve the problem potentially lead to higher quality planning in real-life logistics, thanks to the exploitation of the probabilistic informations that can normally be derived from historical data. In this paper we present an iterative model-based algorithm that solves a sequence of deterministic problems and is able to retrieve and certify optimal solutions if run for sufficient time. Experimental results show that the new approach is performing well when compared against both the exact (proven optimality) and heuristic (high quality solutions) algorithms available in the literature.

关键词： Probabilistic Orienteering Problem Heuristic algorithms exact algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：