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

The Minimum Feasible Tileset Problem

algorithmICA 2019年第3期81卷 1126-1151页

作者： Disser, Yann Kratsch, Stefan Sorge, Manuel Tech Univ Darmstadt Grad Sch CE Inst Math Darmstadt Germany Humboldt Univ Inst Informat Berlin Germany TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel

We introduce and study the Minimum Feasible Tileset problem: given a set of symbols and subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols (tiles) such that each scenario can be formed by selecting at most one symbol from each tile. We show that this problem is APX-hard and that it is NP-hard even if each scenario contains at most three symbols. Our main result is a 4/3-approximation algorithm for the general case. In addition, we show that the Minimum Feasible Tileset problem is fixed-parameter tractable both when parameterized with the number of scenarios and with the number of symbols.

关键词： Set packing approximation algorithm APX hardness Parameterized complexity Minimum feasible tileset

来源：评论

学校读者我要写书评

暂无评论

A Constant Factor approximation algorithm for Reordering Buffer Management 13

A Constant Factor Approximation Algorithm for Reordering Buf...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Noa Avigdor-Elgrabli Yuval Rabani Computer Science Department Technion-Israel Institute of Technology The Rachel and Selim Benin School of Computer Science and Engineering and the Center of Excellence on Algorithms The Hebrew University of Jerusalem

ISBN: (纸本)9781611972511

In the reordering buffer management problem (RBM) a sequence of n colored items enters a buffer with limited capacity k. When the buffer is full, one item is removed to the output sequence, making room for the next input item. This step is repeated until the input sequence is exhausted and the buffer is empty. The objective is to find a sequence of removals that minimizes the total number of color changes in the output sequence. The problem formalizes numerous applications in computer and production systems, and is known to be NP-hard. We give the first constant factor approximation guarantee for RBM. Our algorithm is based on an intricate "rounding" of the solution to an LP relaxation for RBM, so it also establishes a constant upper bound on the integrality gap of this relaxation. Our results improve upon the best previous bound of O({the square root of}log k) of Adamaszek et al. (STOC 2011) that used different methods and gave an online algorithm. Our constant factor approximation beats the super-constant lower bounds on the competitive ratio given by Adamaszek et al. This is the first demonstration of a polynomial time of-fine algorithm for RBM that is provably better than any online algorithm.

关键词： approximation algorithm Reordering Buffer Management first demonstration approximation algorithms buffers Input sequence Constants Sequences

来源：评论

学校读者我要写书评

暂无评论

Minimum Connected Dominating Set Under Routing Cost Constraint in Wireless Sensor Networks With Different Transmission Ranges

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2019年第2期27卷 546-559页

作者： Song, Liang Liu, Chunyan Huang, Hejiao Du, Hongwei Jia, Xiaohua Xiamen Univ Dept Software Engn Xiamen 361005 Peoples R China Nanjing Univ Aeronaut & Astronaut Dept Comp Sci & Technol Nanjing 211106 Jiangsu Peoples R China Harbin Inst Technol Dept Comp Sci & Technol Shenzhen 518055 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

Wireless sensor networks (WSNs) are used to cover destination areas for a lot of practical applications. To enhance the performance of the WSN, the virtual backbone based on the connected dominating set is an efficient way with respect to the routing cost between sensors, lifetime of entire network, and so on. In this paper, especially for the WSN with different transmission radii among different sensors, we study the problem of constructing the minimum rho-range connected dominating set under the constraint alpha-times of the minimum routing cost (alpha MOC-rho CDS), where alpha >= 5 and rho is the ratio of the maximum-to-minimum transmission radius. Our contributions are three folds. First, we propose a polynomial time approximation scheme which generates the alpha MOC-rho CDS with the size of at most (1 + epsilon) times of the optimum solution, where epsilon is the error parameter. Second, we propose a polynomial time algorithm and prove that it has two approximation ratios (6 rho + 1)(2)(2 rho + 1)(2) and 10 inverted right perpendicular (2 pi/theta)inverted left perpendicular right perpendicular (ln 3 rho/(ln(1/cos theta))) left perpendicular right perpendicular (ln rho/(ln(2 cos(pi/5)))) left perpendicular, where theta < arcsin(1/3 rho). Finally, we propose the distributed version of the constant approximation ratio algorithm which has both the time complexity and message complexity O(n(3)), where n is the number of sensor nodes. Besides, the simulation results demonstrate the efficiency of our algorithms.

关键词： WSN alpha MOC-rho CDS PTAS approximation algorithm distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximizing profit of multiple adoptions in social networks with a martingale approach

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第1期38卷 1-20页

作者： Liu, Bin Yan, Yuxia Fang, Qizhi Dong, Junyu Wu, Weili Wang, Huijuan Ocean Univ China Sch Math Sci Qingdao 266100 Shandong Peoples R China Ocean Univ China Coll Informat Sci & Engn Qingdao 266100 Shandong Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA Qingdao Univ Sch Math & Stat Qingdao 266071 Shandong Peoples R China

Information propagation plays an important role in social network, which helps shaping consumer's purchasing decisions. Most of existing works focus on maximizing the influence of one product. But in our reality life, the majority of the companies produce various products for meeting customer needs. So it is important to learn about how to distribute the limited budget to maximize the companies profits. In this paper, we use the martingale technique to handle the Profit Maximization with Multiple Adoptions (PM2A) problem, which aims to identify a seed set for each product with overall activation cost at most B such that the expected total profit is maximized. We design a PM2AM algorithm which returns a (-epsilon)-approximate solution and runs in O expected time.

关键词： Profit maximization Social network approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimizing Egalitarian Performance when Colocating Tasks with Types for Cloud Data Center Resource Management

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2019年第11期30卷 2523-2535页

作者： Pascual, Fanny Rzadca, Krzysztof Sorbonne Univ CNRS Lab Informat Paris 6 F-75005 Paris France Univ Warsaw Inst Informat PL-00927 Warsaw Poland

In data centers, up to dozens of tasks are colocated on a single physical machine. Machines are used more efficiently, but the performance of the tasks deteriorates, as the colocated tasks compete for shared resources. Since the tasks are heterogeneous, the resulting performance dependencies are complex. In our previous work [1] , [2] we proposed a new combinatorial optimization model that uses two parameters of a task - its size and its type - to characterize how a task influences the performance of other tasks allocated to the same machine. In this paper, we study the egalitarian optimization goal: the aim is to optimize the performance of the worst-off task. This problem generalizes the classic makespan minimization on multiple processors ($P||C_{\max }$P||Cmax). We prove that polynomially-solvable variants of $P||C_{\max }$P||Cmax are NP-hard for this generalization, and that the problem is hard to approximate when the number of types is not constant. For a constant number of types, we propose a PTAS, a fast approximation algorithm, and a series of heuristics. We simulate the algorithms on instances derived from a trace of one of Google clusters. Compared with baseline algorithms solving $P||C_{\max }$P||Cmax, our proposed algorithms aware of the types of the jobs lead to significantly better tasks' performance. The notion of type enables us to extend standard combinatorial optimization methods to handle degradation of performance caused by colocation. Types add a layer of additional complexity. However, our results - approximation algorithms and good average-case performance - show that types can be handled efficiently.

关键词： Task analysis approximation algorithms Data centers Resource management Clustering algorithms Computational modeling Load modeling Cloud computing scheduling complexity approximation algorithm heterogeneity co-tenancy workload co-location

来源：评论

学校读者我要写书评

暂无评论

Complexity and online algorithms for minimum skyline coloring of intervals

引用

THEORETICAL COMPUTER SCIENCE 2019年 788卷 66-78页

作者： Erlebach, Thomas Liu, Fu-Hong Liu, Hsiang-Hsuan Shalom, Mordechai Wong, Prudence W. H. Zaks, Shmuel Univ Leicester Dept Informat Leicester Leics England Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan Univ Wroclaw Inst Comp Sci Wroclaw Poland TelHai Coll IL-12210 Upper Galilee Israel Univ Liverpool Dept Comp Sci Liverpool Merseyside England Technion Dept Comp Sci Haifa Israel Ruppin Acad Ctr Sch Engn Netanya Israel

Motivated by applications in optical networks and job scheduling, we consider the interval coloring problem in a setting where an increasing cost is associated with using a higher color index. The cost of a coloring at any point of the line is the cost of the maximum color index used at that point, and the cost of the overall coloring is the integral of the cost over all points on the line. A coloring of minimum cost is called a minimum skyline coloring. We prove that the problem of computing a minimum skyline coloring is NP-hard and initiate the study of the online setting, where intervals arrive one by one. We give an asymptotically optimal online algorithm for the case of linear color costs and present further results for some variations and generalizations of the problem. Furthermore, we consider the variant of the minimum skyline coloring problem where the intervals are already partitioned into color classes and we only need permute the colors so as to minimize the cost of the coloring. We show that this problem variant is NP-hard and present a 2-approximation algorithm for it. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Skyline coloring of intervals Online algorithm NP-hardness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The Replenishment Schedule to Minimize Peak Storage Problem: The Gap Between the Continuous and Discrete Versions of the Problem

引用

OPERATIONS RESEARCH 2019年第5期67卷 1345-1361页

作者： Hochbaum, Dorit S. Rao, Xu Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94709 USA

The replenishment storage problem (RSP) is to minimize the storage capacity requirement for a deterministic demand, multi-item inventory system, where each item has a given reorder size and cycle length. We consider the discrete RSP, where reorders can only take place at an integer time unit within the cycle. Discrete RSP was shown to be NP-hard for constant joint cycle length (the least common multiple of the length of all individual cycles). We show here that discrete RSP is weakly NP-hard for constant joint cycle length and prove that it is strongly NP-hard for nonconstant joint cycle length. For constant joint cycle-length discrete RSP, we further present a pseudopolynomial time algorithm that solves the problem optimally and the first known fully polynomial time approximation scheme (FPTAS) for the single-cycle RSP. The scheme is utilizing a new integer programming formulation of the problem that is introduced here. For the strongly NP-hard RSP with nonconstant joint cycle length, we provide a polynomial time approximation scheme (PTAS), which for any fixed e, provides a linear time e approximate solution. The continuous RSP, where reorders can take place at any time within a cycle, seems (with our results) to be easier than the respective discrete problem. We narrow the previously known complexity gap between the continuous and discrete versions of RSP for the multi-cycle RSP (with either constant or nonconstant cycle length) and the single-cycle RSP with constant cycle length and widen the gap for single-cycle RSP with nonconstant cycle length. For the multi-cycle case and constant joint cycle length, the complexity status of continuous RSP is open, whereas it is proved here that the discrete RSP is weakly NP-hard. Under our conjecture that the continuous RSP is easier than the discrete one, this implies that continuous RSP on multi-cycle and constant joint cycle length (currently of unknown complexity status) is at most weakly NP-hard.

关键词： deterministic inventory theory complexity approximation algorithm weakly NP-hard integer programming

来源：评论

学校读者我要写书评

暂无评论

Ambulance Deployment With Relocation Through Robust Optimization

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2019年第1期16卷 138-147页

作者： Zhang, Ran Zeng, Bo Univ S Florida Dept Ind & Management Syst Engn Tampa FL 33620 USA Univ Pittsburgh Dept Ind Engn Pittsburgh PA 15260 USA Univ Pittsburgh Dept Elect & Comp Engn Pittsburgh PA 15260 USA

This paper investigates the deployment issue of an emergency medical service (EMS) system to maintain the preferred service coverages under different considerations. Specifically, two coverage levels are introduced to reflect the requirements under the regular situation and the situation with ambulance unavailable. We propose the two-stage robust optimization (RO) models to design a reliable ambulance system subject to unavailability of the ambulances, with and without the ambulance relocation. For the RO problem with mixed-integer recourse for relocation, we customize the column and constraint generation method with an approximation strategy to handle the computational challenge. Our numerical study: 1) demonstrates that our RO formulations have a strong modeling capacity on designing the EMS system;2) shows that our approximation algorithm performs very well;and 3) provides a quantitative evaluation of, including, relocation operations on the system performance. Note to Practitioners-This paper presents the novel optimization models to help ambulance deployment. Due to ambulance unavailability and relocation operations, traditional optimization formulations might not be sufficient for modeling or might be hard for computation. In this paper, we provide an uncertainty set-based approach to capture ambulance unavailability and to build the robust optimization models (with relocation recourse decisions). Also, efficient algorithms are designed to support practical instances. Numerical results are very supportive to our new models and computational methods.

关键词： Ambulance location and relocation approximation algorithm two-stage robust optimization (RO)

来源：评论

学校读者我要写书评

暂无评论

Efficient Representative Subset Selection over Sliding Windows

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2019年第7期31卷 1327-1340页

作者： Wang, Yanhao Li, Yuchen Tan, Kian-Lee Natl Univ Singapore Sch Comp Singapore 117417 Singapore Singapore Management Univ Sch Informat Syst Singapore 178902 Singapore

Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. Existing literature models RSS as the submodular maximization problem to capture the "diminishing returns" property of the representativeness of selected subsets, but often only has a single constraint (e.g., cardinality), which limits its applications in many real-world problems. To capture the data recency issue and support different types of constraints, we formulate dynamic RSS in data streams as maximizing submodular functions subject to general d-knapsack constraints (SMDK) over sliding windows. We propose a KNAPWINDOW framework (KW) for SMDK. KW utilizes the KNAPSTREAM algorithm (KS) for SMDK in append-only streams as a subroutine. It maintains a sequence of checkpoints and KS instances over the sliding window. Theoretically, KW is 1-epsilon/1+dapproximate for SMDK. Furthermore, we propose a KNAPWINDOWPLUS framework (KW+) to improve upon KW. KW+ builds an index SUBKNAPCHK to manage the checkpoints and KS instances. SUBKNAPCHK deletes a checkpoint whenever it can be approximated by its successors. By keeping much fewer checkpoints, KW+ achieves higher efficiency than KW while still guaranteeing a 1-epsilon'/2+2d-approximate solution for SMDK. Finally, we evaluate the efficiency and solution quality of KW and KW+ in real-world datasets. The experimental results demonstrate that KW achieves more than two orders of magnitude speedups over the batch baseline and preserves high-quality solutions for SMDK over sliding windows. KW+ further runs 5-10 times faster than KW while providing solutions with equivalent or even better utilities.

关键词： Data summarization sliding window data stream submodular maximization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On index policies for stochastic minsum scheduling

引用

OPERATIONS RESEARCH LETTERS 2019年第3期47卷 213-218页

作者： Eberle, Franziska Fischer, Felix Matuschke, Jannik Megow, Nicole Univ Bremen Dept Math & Comp Sci Bremen Germany Queen Mary Univ London Sch Math Sci London England Katholieke Univ Leuven Res Ctr Operat Management Leuven Belgium

Minimizing the sum of completion times when scheduling jobs on m identical parallel machines is a fundamental scheduling problem. Unlike the well-understood deterministic variant, it is a major open problem how to handle stochastic processing times. We show for the prominent class of index policies that no such policy can achieve a distribution-independent approximation factor. This strong lower bound holds even for simple instances with deterministic and two-point distributed jobs. For such instances, we give an O(m)-approximative list scheduling policy. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Stochastic scheduling Parallel machines Total completion time approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：