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

The budgeted maximum coverage problem

INFORMATION PROCESSING LETTERS 1999年第1期70卷 39-45页

作者： Khuller, S Moss, A Naor, JS Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Univ Maryland Dept Comp Sci College Pk MD 20742 USA

The budgeted maximum coverage problem is: given a collection S of sets with associated costs defined over a domain of weighted elements, and a budget L, find a subset of S' subset of or equal to S such that the total cost of sets in S' does not exceed L, and the total weight of elements covered by SI is maximized. This problem is NP-hard. For the special case of this problem, where each set has unit cost, a (1 - 1/e)-approximation is known. Yet, prior to this work, no approximation results were known for the general cost version. The contribution of this paper is a (1 - 1/e)-approximation algorithm for the budgeted maximum coverage problem. We also argue that this approximation factor is the best possible, unless NP subset of or equal to DTIME(n(O(log log n))). (C) 1999 Published by Elsevier Science B.V. All rights reserved.

关键词： algorithms maximum coverage problem performance guarantee

来源：评论

学校读者我要写书评

暂无评论

Generation of an equipment module database - A maximum coverage problem

引用

CHEMICAL ENGINEERING RESEARCH & DESIGN 2019年 148卷 164-168页

作者： Eilermann, Martin Schach, Constantin Sander, Peer Bramsiepe, Christian Schembecker, Gerhard TU Dortmund Univ Dept Biochem & Chem Engn Lab Plant & Proc Design Emil Figge Str 70 D-44227 Dortmund Germany Evonik Technol & Infrastruct GmbH Paul Baumann Str 1 D-45772 Marl Germany

Current challenges for (bio-)chemical industry require shorter project lead times. To reduce the lead time, the concept of module-based plant design was developed. Suitable equipment modules are selected from an equipment module database instead of time-consuming tailor-made equipment design. The quality of module-based plant design strongly depends on the quality of the equipment module database. An equipment module database should contain the least number of equipment modules covering as many industrial applications as possible. Hence, the generation of an equipment module database is a maximum coverage problem known from other disciplines, such as facility location. Within this work, the corresponding maximum coverage problem is formulated and solved by a randomized greedy algorithm. The approach for the generation of an equipment module database presented is exemplarily applied for liquid/liquid heat transfer applications provided by Evonik. It is shown, that less equipment modules are required for the same coverage of applications if the equipment module database is generated based on the maximum coverage problem than based on the existing methodology presented by Eilermann et al. (2017). Additionally, less computational effort is required. (C) 2019 Published by Elsevier B.V. on behalf of Institution of Chemical Engineers.

关键词： Module-based plant design Equipment module database maximum coverage problem Greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

The Robust maximum-coverage problem

The Robust Maximum-Coverage Problem

引用

IEEE Systems and Information Engineering Design Symposium (SIEDS)

作者： Sturdy, Ian Kincaid, Rex Coll William & Mary Dept Comp Sci Williamsburg VA 23187 USA Coll William & Mary Dept Math Williamsburg VA 23187 USA

ISBN: (纸本)9781479948369

The maximum coverage problem is a staple of facility location theory, and has more recently been extended to the covering facility interdiction problem, in which covering facilities are chosen for interdiction so as to minimize the resultant coverage. This paper considers the opposite to the interdiction problem, selecting facilities to maximize coverage after the worst-case interdiction. Solutions to this problem would inform facility placement when intentional disruption is feared, or when guaranteeing minimum coverages in the presence of random facility outages. Several approaches to the problem are considered, primarily derivatives of approaches to the structurally similar maximum coverage problem. An integer linear program formulation proves infeasible for problems of even modest size, despite exclusion of many non-binding constraints, but heuristic approaches (again adaptations of maximum coverage heuristics) show promise in both efficiency and solutions quality.

关键词： Facility Location Interdiction problem maximum coverage problem

来源：评论

学校读者我要写书评

暂无评论

Finding most favorite products based on reverse top- queries

引用

VLDB JOURNAL 2014年第4期23卷 541-564页

作者： Koh, Jia-Ling Lin, Chen-Yi Chen, Arbee L. P. Natl Taiwan Normal Univ Dept Comp Sci & Informat Engn Taipei Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30043 Taiwan Natl Chengchi Univ Dept Comp Sci Taipei 11623 Taiwan

A reverse top-t query for a product returns a set of customers, named potential customers, who regard the product as one of their top-t favorites. Given a set of customers with different preferences on the features of the products, we want to select at most products from a pool of candidate products such that their total number of potential customers is maximized. Two versions of the problem are defined according to whether the competitive existing products are given. For solving this NP-hard problem, we first propose an incremental greedy approach to find an approximate solution of the problem with quality guaranteed. For further speeding up this basic greedy approach, we exploit several properties of the top- queries and skyline queries to reduce the solution space of the problem. In addition, an upper bound of the potential customers is estimated to reduce the cost of computing the reverse top- queries for the candidate products. Finally, when the candidate products are formed from multiple component tables, we propose a strategy to reduce the number of the accessed tuples in the component tables such that only the tuples that are possibly components of the top- favorites of the customers need to be accessed. By applying these pruning strategies, we propose another faster greedy approach. The experiment results demonstrate that the proposed pruning strategies work very well and make the faster greedy algorithms for both versions of the problem achieve excellent performance on both efficiency and memory utilization.

关键词： Reverse top-t query Potential customers Query processing maximum coverage problem

来源：评论

学校读者我要写书评

暂无评论

Democratic elections and centralized decisions: Condorcet and Approval Voting compared with Median and coverage locations

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2016年第1期253卷 195-203页

作者： Menezes, Mozart B. C. da Silveira, Giovani J. C. Drezner, Zvi Kedge Business Sch Bordeaux Dept Operat Management 680 Cours Liberat F-33405 Talence France Univ Calgary Haskayne Sch Business 2500 Univ Dr Calgary AB T2N 1N4 Canada Calif State Univ Fullerton Steven G Mihaylo Coll Business & Econ Fullerton CA 92834 USA

In this study, we focus on the quality of Condorcet and Approval Voting winners using Median and maximum coverage problems as benchmarks. We assess the quality of solutions by democratic processes assuming many dimensions for evaluating candidates. We use different norms to map multidimensional preferences into single values. We perform extensive numerical experiments. The Condorcet winner, when he/she exists, may have very high quality measured by the Median objective function, but poor quality measured by the maximum coverage problem. We show that the Approval Voting winner is optimal when the quality is measured by the maximum coverage objective and fairs well when the Median objective is employed. The analyses further indicate that the number of voters and the distance norm may increase, while the number of candidates and dimensions may decrease the quality of democratic methods. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Voting Condorcet Approval Voting Median problem maximum coverage problem

来源：评论

学校读者我要写书评

暂无评论

Locating network monitors: Complexity, heuristics, and coverage

引用

COMPUTER COMMUNICATIONS 2006年第10期29卷 1564-1577页

作者： Suh, Kyoungwon Guo, Yang Kurose, Jim Towsley, Don Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA Thomson Inc Corp Res Ctr Princeton NJ 08540 USA

There is an increasing interest in passive monitoring of IP flows at multiple locations within an IP network. The objective of such a distributed monitoring system is to sample packets belonging to a large fraction of IP flows in a cost-effective manner by carefully placing monitors and controlling their sampling rates. In this paper, we consider the problem of where to place monitors within the network and how to control their sampling. To address the tradeoff between monitoring cost and monitoring coverage, we propose and study minimum cost and maximum coverage problems under various budget constraints and in the presence of routing changes caused by link failures. We show that all of the problem formulations are NP-hard. We propose greedy heuristics, and show that the heuristics provide solutions quite close to the optimal solutions through experiments using synthetic and real network topologies. In addition, our experiments show that a small number of monitors often suffices to monitor most of the traffic in an entire IP network. (c) 2005 Elsevier B.V. All rights reserved.

关键词： network monitoring mathematical programming/optimization approximation algorithms set cover problem maximum coverage problem minimum cost problem packet sampling

来源：评论

学校读者我要写书评

暂无评论

Sequential pattern mining for ICT risk assessment and management

引用

JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING 2019年 102卷 1-16页

作者： D'Andreagiovanni, Michele Baiardi, Fabrizio Lipilini, Jacopo Ruggieri, Salvatore Tonelli, Federico Univ Pisa Dipartimento Informat Largo B Pontecorvo 3 I-56127 Pisa Italy Haruspex SRL Via Vittorio Veneto 126 I-19124 La Spezia Italy

ICT risk assessment and management relies on the analysis of data on the joint behavior of a target system and its attackers. The tools in the Haruspex suite model intelligent, goal-oriented attackers that reach their goals through sequences of attacks. The tools synthetically generate these sequences through a Monte Carlo method that runs multiple simulations of the attacker behavior. This paper presents a sequential pattern mining analysis of the attack sequence database to extract a high-level and succinct understanding of the attacker strategies against the system to assess. Such an understanding is expressed as a set of sequential patterns that cover, and possibly partition, the attack sequences. This set can be extracted in isolation, or in contrast with the behavior of other attackers. In the latter case, the patterns represent a signature of the behavior of an attacker. The dynamic tools of the suite use this signature to deploy dynamic counter-measures that reduce the security risk. We formally motivate the need for using the class of maximal sequential patterns in covering attack sequences, instead of frequent or closed sequential patterns. When contrasting the behavior of different attackers, we resort to distinguishing sequential patterns. We report an extensive experimentation on a system with 36 nodes, 6 attackers, and 600K attack sequences. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Security risk assessment Attack sequences Sequential pattern mining maximum coverage problem

来源：评论

学校读者我要写书评

暂无评论

Learning ensembles of priority rules for online scheduling by hybrid evolutionary algorithms

引用

INTEGRATED COMPUTER-AIDED ENGINEERING 2021年第1期28卷 65-80页

作者： Gil-Gala, Francisco J. Mencia, Carlos Sierra, Maria R. Varela, Ramiro Univ Oviedo Dept Comp Sci Gijon 33204 Spain

This paper studies the computation of ensembles of priority rules for the One Machine Scheduling problem with variable capacity and total tardiness minimization Concretely, we address the problem of building optimal ensembles of priority rules, starting from a pool of rules evolved by a Genetic Programming approach. Building on earlier work, we propose a number of new algorithms. These include an iterated greedy search method, a local search algorithm and a memetic algorithm. Experimental results show the potential of the proposed approaches.

关键词： Online scheduling one machine scheduling hyper-heuristic priority rules ensemble learning maximum coverage problem

来源：评论

学校读者我要写书评

暂无评论

Finding the tradeoffs between the reserve design and representation

引用

ENVIRONMENTAL MANAGEMENT 2006年第3期38卷 327-337页

作者： Rothley, Kristina D. Simon Fraser Univ Sch Resource & Environm Management Burnaby BC V5A 1S6 Canada

Many reserve selection tools have been created to solve the minimum representation problem, selecting the least costly set of sites such that all conservation surrogate targets are met. However, there are practical problems and risks associated with this method for finding reserve network alternatives, including the treatment of persistence-promoting design considerations as secondary objectives. Here, reserve networks are generated for a hypothetical landscape where the objectives are to maximize representation and to maximize conformance with persistence-promoting design principles, subject to a constraint on the number of sites in the networks. The efficiency of potential networks is calculated as the total number of species captured in the included sites. Effectiveness is measured as a function of the size of individual patches, total reserve size, and extent of interpatch connectivity. A series of tradeoff curves are produced showing the nondominated compromise alternatives between representation and design for organisms with varying dispersal capabilities, Each alternative comprises a list of selected sites and covers species, as well as the identities and locations of the interpatch edges connecting the sites. Potential ways to use the results are discussed.

关键词： reserve design representativeness connectivity minimum representation problem spatial reserve design principles maximum coverage problem

来源：评论

学校读者我要写书评

暂无评论

Local Feature Reliability Measure Consistent with Match Conditions for Mobile Visual Search

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2018年第12期E101D卷 3170-3180页

作者： Matsuzaki, Kohei Tasaka, Kazuyuki Yanagihara, Hiromasa KDDI Res Inc Media Recognit Lab Fujimino 3568502 Japan KDDI Res Inc Fujimino 3568502 Japan KDDI Res Inc Media ICT Div Fujimino 3568502 Japan

We propose a feature design method for a mobile visual search based on binary features and a bag-of-visual words framework. In mobile visual search, detection error and quantization error are unavoidable due to viewpoint changes and cause performance degradation. Typical approaches to visual search extract features from a single view of reference images, though such features are insufficient to manage detection and quantization errors. In this paper, we extract features from multiview synthetic images. These features are selected according to our novel reliability measure which enables robust recognition against various viewpoint changes. We regard feature selection as a maximum coverage problem. That is, we find a finite set of features maximizing an objective function under certain constraints. As this problem is NP-hard and thus computationally infeasible, we explore approximate solutions based on a greedy algorithm. For this purpose, we propose novel constraint functions which are designed to be consistent with the match conditions in the visual search method. Experiments show that the proposed method improves retrieval accuracy by 12.7 percentage points without increasing the database size or changing the search procedure. In other words, the proposed method enables more accurate search without adversely affecting the database size, computational cost, and memory requirement.

关键词： mobile visual search binary feature feature selection maximum coverage problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：