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

The capacitated team orienteering problem with incomplete service

OPTIMIZATION LETTERS 2013年第7期7卷 1405-1417页

作者： Archetti, Claudia Bianchessi, Nicola Speranza, M. Grazia Univ Brescia Dept Quantitat Methods Brescia Italy Univ Brescia Dept Informat Engn Brescia Italy

In this paper we study the capacitated version of the Team Orienteering Problem (TOP), that is the Capacitated TOP (CTOP) and the impact of relaxing the assumption that a customer, if served, must be completely served. We prove that the profit collected by the CTOP with Incomplete Service (CTOP-IS) may be as large as twice the profit collected by the CTOP. A computational study is also performed to evaluate the average increase of the profit due to allowing incomplete service. The results show that the increase of the profit strongly depends on the specific instance. On the tested instances the profit increase ranges between 0 and 50 %. We complete the computational study with the increase of the profit of the CTOP due to split deliveries, that is multiple visits to the same customer, and to split deliveries combined with incomplete service.

关键词： Capacitated Team Orienteering Problem Incomplete service Split deliveries exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Partition Into Triangles on Bounded Degree Graphs

引用

THEORY OF COMPUTING SYSTEMS 2013年第4期52卷 687-718页

作者： van Rooij, Johan M. M. Niekerk, Marcel E. van Kooten Bodlaender, Hans L. Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands

We consider the Partition Into Triangles problem on bounded degree graphs. We show that this problem is polynomial-time solvable on graphs of maximum degree three by giving a linear-time algorithm. We also show that this problem becomes -complete on graphs of maximum degree four. Moreover, we show that there is no subexponential-time algorithm for this problem on graphs of maximum degree four unless the Exponential-Time Hypothesis fails. However, the Partition Into Triangles problem on graphs of maximum degree at most four is in many cases practically solvable as we give an algorithm for this problem that runs in time and linear space.

关键词： algorithms exact algorithms Partition into triangles Graph algorithms Bounded degree graphs Satisfiability

来源：评论

学校读者我要写书评

暂无评论

Sort and Search: exact algorithms for generalized domination

引用

INFORMATION PROCESSING LETTERS 2009年第14期109卷 795-798页

作者： Fomin, Fedor V. Golovach, Petr A. Kratochvil, Jan Kratsch, Dieter Liedloff, Mathieu Univ Bergen Dept Informat N-5020 Bergen Norway Charles Univ Prague Dept Appl Math CR-11800 Prague 1 Czech Republic Charles Univ Prague Inst Theoret Comp Sci CR-11800 Prague 1 Czech Republic Univ Paul Verlaine Lab Informat Theor & Appl F-57045 Metz 01 France Univ Orleans Lab Informat Fondamentale Orleans F-45067 Orleans 2 France

In 1994, Telle introduced the following notion of domination, which generalizes many domination-type graph invariants. Let sigma and rho be two sets of non-negative integers. A vertex subset S subset of V of an undirected graph G = (V, E) is called a (sigma, rho)-dominating set of G if |N(v) boolean AND S| is an element of sigma for all v is an element of S and |N(v) boolean AND S| is an element of rho for all v is an element of V \ S. In this paper, we prove that decision, optimization, and counting variants of ({p}, {q})-domination are solvable in time 2(|V|/2), |V|(0(1)). We also show how to extend these results for infinite sigma = {p + M . l: l is an element of N-0} and rho = {q + m . l: l is an element of N-0}. For the case |sigma| + |rho| = 3, these problems can be solved in time 3(|V|/2). |V|(0(1)), and similarly to the case |sigma| = |rho| = 1 it is possible to extend the algorithm for some infinite sets. (C) 2009 Elsevier B.V. All rights reserved.

关键词： exact algorithms Domination Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Pattern-Guided k-Anonymity

引用

algorithms 2013年第4期6卷 678-701页

作者： Bredereck, Robert Nichterlein, Andre Niedermeier, Rolf TU Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany

We suggest a user-oriented approach to combinatorial data anonymization. A data matrix is called k-anonymous if every row appears at least k times-the goal of the NP-hard k-ANONYMITY problem then is to make a given matrix k-anonymous by suppressing (blanking out) as few entries as possible. Building on previous work and coping with corresponding deficiencies, we describe an enhanced k -anonymization problem called PATTERN-GUIDED k-ANONYMITY, where the users specify in which combinations suppressions may occur. In this way, the user of the anonymized data can express the differing importance of various data features. We show that PATTERN-GUIDED k-ANONYMITY is NP-hard. We complement this by a fixed-parameter tractability result based on a "data-driven parameterization" and, based on this, develop an exact integer linear program (ILP)-based solution method, as well as a simple, but very effective, greedy heuristic. Experiments on several real-world datasets show that our heuristic easily matches up to the established "Mondrian" algorithm for k-ANONYMITY in terms of the quality of the anonymization and outperforms it in terms of running time.

关键词： NP-hardness parameterized complexity integer linear programming exact algorithms heuristics experiments

来源：评论

学校读者我要写书评

暂无评论

Editorial: Special Issue on Graph algorithms

引用

algorithms 2013年第3期6卷 457-458页

作者： Jansson, Jesper Kyoto Univ Inst Chem Res Bioinformat Ctr Lab Math Bioinformat Uji Kyoto 6110011 Japan

This special issue of algorithms is devoted to the design and analysis of algorithms for solving combinatorial problems of a theoretical or practical nature involving graphs, with a focus on computational complexity.

关键词： graph algorithms computational complexity fixed-parameter tractability exact algorithms approximation algorithms heuristics computational studies

来源：评论

学校读者我要写书评

暂无评论

COUNTING AND DETECTING SMALL SUBGRAPHS VIA EQUATIONS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2013年第2期27卷 892-909页

作者： Kowaluk, Miroslaw Lingas, Andrzej Lundell, Eva-Marta Warsaw Univ Inst Informat Warsaw Poland Lund Univ Dept Comp Sci S-22100 Lund Sweden

We present a general technique for detecting and counting small subgraphs. It consists of forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph. These combinations can be efficiently computed by rectangular matrix multiplication. Our two main results utilizing the technique are as follows. Let H be a fixed graph with k vertices and an independent set of size s. 1. Detecting if an n-vertex graph contains a (not necessarily induced) subgraph isomorphic to H can be done in time O(n(omega(inverte right perpendicular(k-s)/2inverted letf perpendicular,1,1 right perpendicular(k- s)/2inverted letf perpendicular))), where omega(p, q, r) is the exponent of fast arithmetic matrix multiplication of an n(p) x n(q) matrix by an n(q) x n(r) matrix. 2. When s = 2, counting the number of (not necessarily induced) subgraphs isomorphic to H can be done in the same time, i.e., in time O(n(omega(inverted right perpendicular(k-2)/2inverted left perpendicular,1, inverted right perpendicular(k-2)/2inverted left perpendicular))). It follows in particular that we can count the number of subgraphs isomorphic to any H on four vertices that is not K-4 in time O(n(omega)), where omega = omega(1, 1, 1) is known to be smaller than 2.373. Similarly, we can count the number of subgraphs isomorphic to any H on five vertices that is not K-5 in time O(n(omega(2,1,1))), where omega(2, 1, 1) is known to be smaller than 3.257. Finally, we derive input-sensitive variants of our time upper bounds. They are partially expressed in terms of the number m of edges of the input graph and do not rely on fast matrix multiplication.

关键词： subgraph and induced subgraph isomorphism counting and detection of subgraphs linear equations exact algorithms rectangular matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

An exact Algorithm for Blockmodeling of Two-Mode Network Data

引用

JOURNAL OF MATHEMATICAL SOCIOLOGY 2013年第2期37卷 61-84页

作者： Brusco, Michael Doreian, Patrick Mrvar, Andrej Steinley, Douglas Florida State Univ Coll Business Tallahassee FL 32306 USA Univ Pittsburgh Dept Sociol Pittsburgh PA 15260 USA Univ Ljubljana Fac Social Sci Ljubljana Slovenia Univ Missouri Columbia Dept Psychol Sci Columbia MO USA

We consider problems where relationships between two sets (or modes) of objects are available in the form of a binary matrix with elements of 1 (0) indicating a bond (lack of a bond) between corresponding row and column objects. The goal is to establish a partition of the row objects and, simultaneously, a partition of the column objects to form blocks that consist of either exclusively 1s or exclusively 0s to the greatest extent possible. This two-mode blockmodeling problem arises in several scientific domains. In the social sciences, two-mode blockmodeling is particularly relevant for social network analysis, where the goal is to simultaneously partition a set of individuals and another set of objects (e.g., events they attended, organizations they are affiliated with, etc.). The inherent computational challenge of simultaneously constructing partitions for two distinct sets of objects has fostered a reliance on heuristics for two-mode blockmodeling. We offer an exact algorithm and demonstrate its efficacy in a simulation study. Two applications to real-world networks are also provided.

关键词： branch-and-bound exact algorithms generalized blockmodeling social networks two-mode networks

来源：评论

学校读者我要写书评

暂无评论

IMPROVING EXHAUSTIVE SEARCH IMPLIES SUPERPOLYNOMIAL LOWER BOUNDS

引用

SIAM JOURNAL ON COMPUTING 2013年第3期42卷 1218-1244页

作者： Williams, Ryan IBM Almaden Res Ctr Principles & Methodol Grp San Jose CA 94538 USA

The P vs. NP problem arose from the question of whether exhaustive search is necessary for problems with short verifiable solutions. We do not know if even a slight algorithmic improvement over exhaustive search is universally possible for all NP problems, and to date no major consequences have been derived from the assumption that an improvement exists. We show that there are natural NP and BPP problems for which minor algorithmic improvements over the trivial deterministic simulation already entail lower bounds such as NEXP not subset of P/poly and LOGSPACE not equal NP. These results are especially interesting given that similar improvements have been found for many other hard problems. Optimistically, one might hope our results suggest a new path to lower bounds;pessimistically, they show that carrying out the seemingly modest program of finding slightly better algorithms for all search problems may be extremely difficult (if not impossible). We also prove unconditional superpolynomial time-space lower bounds for improving on exhaustive search: there is a problem verifiable with k(n) length witnesses in O(n(a)) time (for some a and some function k(n) <= n) that cannot be solved in k(n)(c)n(a+o(1)) time and k(n)(c)n(o(1)) space, for every c >= 1. While such problems can always be solved by exhaustive search in O(2(k(n))n(a)) time and O(k(n)+n(a)) space, we can prove a superpolynomial lower bound in the parameter k(n) when space usage is restricted.

关键词： lower bounds improved exponential algorithms exact algorithms time-space trade-offs circuit complexity

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for MIN INDEPENDENT DOMINATING SET

引用

DISCRETE APPLIED MATHEMATICS 2013年第4-5期161卷 558-572页

作者： Bourgeois, N. Della Croce, F. Escoffier, B. Paschos, V. Th. CNRS LAMSADE F-75700 Paris France Univ Paris 09 F-75775 Paris 16 France Politecn Torino DAI Turin Italy

We first devise a branching algorithm that computes a minimum independent dominating set with running time O*(1.3351(n)) = O*(2(0.417n)) and polynomial space. This improves upon the best state of the art algorithms for this problem. We then study approximation of the problem by moderately exponential time algorithms and show that it can be approximated within ratio 1 + epsilon, for any epsilon > 0, in a time smaller than the one of exact computation and exponentially decreasing with epsilon. We also propose approximation algorithms with better running times for ratios greater than 3 in general graphs and give improved moderately exponential time approximation results in triangle-free and bipartite graphs. These latter results are based upon a new bound on the number of maximal independent sets of a given size in these graphs, which is a result interesting per se. (C) 2012 Elsevier B.V. All rights reserved.

关键词： MIN INDEPENDENT DOMINATING SET Exponential algorithms exact algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Polynomial-Space algorithms Using Inclusion-Exclusion

引用

ALGORITHMICA 2013年第4期65卷 868-884页

作者： Nederlof, Jesper Univ Bergen Dept Informat N-5020 Bergen Norway

Given a graph with n vertices, k terminals and positive integer weights not larger than c, we compute a minimum Steiner Tree in time and space, where the notation omits terms bounded by a polynomial in the input-size. We obtain the result by defining a generalization of walks, called branching walks, and combining it with the Inclusion-Exclusion technique. Using this combination we also give -time polynomial space algorithms for Degree Constrained Spanning Tree, Maximum Internal Spanning Tree and #Spanning Forest with a given number of components. Furthermore, using related techniques, we also present new polynomial space algorithms for computing the Cover Polynomial of a graph, Convex Tree Coloring and counting the number of perfect matchings of a graph.

关键词： Inclusion-Exclusion Fixed parameter tractability exact algorithms Polynomial space Steiner tree

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：