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

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第3期44卷 1556-1577页

作者： Christman, Ananya Chung, Christine Jaczko, Nicholas Westvold, Scott Yuen, David S. Middlebury Coll Dept Comp Sci Middlebury VT 05753 USA Connecticut Coll Dept Comp Sci New London CT 06320 USA Univ Hawaii Dept Math Honolulu HI 96822 USA

We study the robust assignment problem where the goal is to assign items of various types to containers without exceeding container capacity. We seek an assignment that uses the fewest number of containers and is robust, that is, if any item of type t(i) becomes corrupt causing the containers with type t(i) to become unstable, every other item type t(j) not equal t(i) is still assigned to a stable container. We begin by presenting an optimal polynomial-time algorithm that finds a robust assignment using the minimum number of containers for the case when the containers have infinite capacity. Then we consider the case where all containers have some fixed capacity and give an optimal polynomial-time algorithm for the special case where each type of item has the same size. When the sizes of the item types are nonuniform, we provide a polynomial-time 2-approximation for the problem. We also prove that the approximation ratio of our algorithm is no lower than 1.813. We conclude with an experimental evaluation of our algorithm.

关键词： approximation algorithm Robust Assignment Hosting Distributed system Combinatorial optimization Bin packing

来源：评论

学校读者我要写书评

暂无评论

A note on the minimum power partial cover problem on the plane

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第2期44卷 970-978页

作者： Dai, Han Deng, Bin Li, Weidong Liu, Xiaofei Yunnan Univ Sch Math & Stat Kunming Yunnan Peoples R China Yunnan Univ Sch Informat Sci & Engn Kunming Yunnan Peoples R China

Given a set of n points and a set of m sensors on the plane, each sensor s can adjust its power p(s) and the covering range which is a disk of radius r (s) satisfying p(s) = c . r(s)(alpha). The minimum power partial cover problem, introduced by Freund (Proceedings of international workshop on approximation and online algorithms, pp 137-150.2011. http://***/viewdoc/summary?doi=10.1.1.737.1320), is to determine the power assignment on every sensor such that at least k (k <= n) points are covered and the total power consumption is minimized. By generalizing the method in Li (Journal of Com. Opti.2020. https://***/10.1007/s10878-020-00567-3) whose approximation ratio is 3(alpha) and enlarging the radius of each disk in the relaxed independent set, we present an O (alpha)-approximation algorithm.

关键词： Power partial cover Primal dual approximation algorithm Relaxed independent set

来源：评论

学校读者我要写书评

暂无评论

APPROXIMABILITY OF MONOTONE SUBMODULAR FUNCTION MAXIMIZATION UNDER CARDINALITY AND MATROID CONSTRAINTS IN THE STREAMING MODEL

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第1期36卷 355-382页

作者： Huang, Chien-Chung Kakimura, Naonori Mauras, Simon Yoshida, Yuichi PSL CNRS ENS F-75005 Paris France Keio Univ Yokohama Kanagawa 2238522 Japan Univ Paris CNRS IRIF F-75013 Paris France Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan

Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is large gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat 1 - 1/e the single-pass streaming model. Let n be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio 2-root 2+epsilon requires Omega(n/K-2) space for any epsilon > 0, where K is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio K/2K-1 requires Omega(n/K-2) space for any epsilon > 0, where K is the rank of the given matroid. In addition, we give streaming algorithms that assume access to the objective function via a weak oracle that can only be used to evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios K/2K-1 and 1/2, respectively, whose space complexity is exponential in K but is independent of n. The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of K for a matroid constraint, which almost settles the approximation ratio for a matroid constraint K/2K-1 that can be obtained by a streaming algorithm whose space complexity is independent of n.

关键词： submodular function maximization streaming model approximation algorithm inapproximability

来源：评论

学校读者我要写书评

暂无评论

Adaptive influence maximization under fixed observation time-step

引用

THEORETICAL COMPUTER SCIENCE 2022年 928卷 104-114页

作者： Zhang, Yapu Chen, Shengminjie Xu, Wenqing Zhang, Zhenning Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China

The influence maximization problem aims to find some seeds which can cause the maximum influence spread results in a social network. Most researches focus on the non-adaptive strategies, in which all seeds are selected at once. For the non-adaptive strategies, the seeds may influence other seeds in the influence spread process and make the waste of budget. This paper considers the adaptive strategies and studies the adaptive influence maximization and adaptive stochastic influence maximization in the general feedback model. These problems select seeds adaptively, and it completes each selection after the fixed observation time-step. In this paper, we utilize the adaptive greedy to solve these problems and propose a theoretical analysis by introducing a comparative factor. In addition, we present the feasible approximation algorithm using the reverse sampling technique. Finally, we carry out experiments on three networks to show the efficiency of adaptive strategies. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Adaptive influence maximization Non-adaptive strategies Social network approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Private non-monotone submodular maximization

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第5期44卷 3212-3232页

作者： Sun, Xin Li, Gaidi Zhang, Yapu Zhang, Zhenning Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China

We propose a private algorithm for the problem of maximizing a submodular but not necessary monotone set function over a down-closed family of sets. The constraint is very general since it includes some important and typical constraints such as knapsack and matroid constraints. Our algorithm DIFFERENTIALLY PRIVATE MEASURE *** GREEDY is proved to be O(epsilon)-differential private. For the multilinear relaxation of the above problem, it yields (T e(-T)- o(1))-approximation guarantee with additive error O (2 Delta/epsilon n4), where T is an element of [0, 1] is the stopping time of the algorithm, A is the defined sensitivity of the objective function, which is associated to a sensitive dataset, and n is the size of the given ground set. For a specific matroid constraint, we could obtain a discrete solution with near 1/e-approximation guarantee and same additive error by lossless rounding technique. Besides, our algorithm can be also applied in monotone case. The approximation guarantee is (1 - e(-T)- 0(1)) when the submodular set function is monotone. Furthermore, we give a conclusion in terms of the density of the relaxation constraint, which is always at least as good as the tight bound (1 - 1/e).

关键词： Differential privacy Submodular maximization Down-closed family of sets Measured continuous greedy approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Cleaning Uncertain Data With Crowdsourcing-A General Model With Diverse Accuracy Rates

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2022年第8期34卷 3629-3642页

作者： Zhang, Chen Zhang, Haodi Xie, Weiteng Liu, Nan Li, Qifan Jiang, Di Lin, Peiguang Wu, Kaishun Chen, Lei Shandong Univ Finance & Econ Sch Comp Sci & Technol Jinan 250014 Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Kowloon Hong Kong Peoples R China Shenzhen Univ Coll Comp Sci & Software Engn Shenzhen 518060 Peoples R China WeBank AI Shenzhen 518052 Peoples R China Guangzhou HKUST Fok Ying Tung Res Inst Guangzhou Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China

Since inaccuracies commonly exist in many applications, data uncertainty has become an important problem in database systems. To deal with data uncertainty, probabilistic databases can be used to store uncertain data, and querying facilities are provided to yield answers with confidence. However, the results from a query or mining process may not be reliable when the uncertainty propagates in the systems. In this paper, we leverage the power of crowdsourcing by designing a set of Human Intelligence Tasks, or HITs in short, to ask a crowd to improve the quality of uncertain data. In particular, we consider crowds consists of workers with diverse accuracy rates when answering the HITs. We design solutions to maximize the data quality with minimal number of HITs. There are two obstacles for this non-trivial optimization, which lead to very high computational cost for selecting the optimal set of HITs. First, members of a crowd may return incorrect answers with different probabilities. Second, the HITs decomposed from uncertain data are often correlated. We have addressed these challenges in this paper by designing an effective approximation algorithm and an efficient heuristic solution, especially for crowds with diverse individual accuracy rates. To further improve the efficiency, we derive tight lower and upper bounds for effective filtering and estimation. Extensive experiments on both a simulated crowd and a real crowdsourcing platform are conducted to evaluate our solutions.

关键词： Crowdsourcing Cleaning Uncertainty Data integrity approximation algorithms Urban areas Databases Crowdsourcing cleaning uncertain data approximation algorithm heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

MAXIMIZING CONVERGENCE TIME IN NETWORK AVERAGING DYNAMICS SUBJECT TO EDGE REMOVAL

引用

SIAM JOURNAL ON OPTIMIZATION 2022年第4期32卷 2718-2744页

作者： Etesami, S. Rasoul Univ Illinois Dept Ind & Syst Engn Coordinated Sci Lab Urbana IL 61801 USA

We consider the consensus interdiction problem (CIP), in which the goal is to max-imize the convergence time of consensus averaging dynamics subject to removing a limited number of network edges. We first show that CIP can be cast as an effective resistance interdiction problem (ERIP), in which the goal is to remove a limited number of network edges to maximize the effective resistance between a source node and a sink node. We show that ERIP is strongly NP-hard, even for bipartite graphs of diameter three with fixed source/sink edges, and establish the same hardness result for the CIP. We then show that both ERIP and CIP cannot be approximated up to a (nearly) polynomial factor assuming the exponential time hypothesis. Subsequently, we devise a polynomial -time mn-approximation algorithm for the ERIP that only depends on the number of nodes n and the number of edges m but is independent of the size of edge resistances. Finally, using a quadratic program formulation for the CIP, we devise an iterative approximation algorithm to find a first-order stationary solution for the CIP and evaluate its good performance through numerical experiments.

关键词： network averaging dynamics consensus interdiction effective resistance interdic-tion computational complexity approximation algorithm quadratic programming

来源：评论

学校读者我要写书评

暂无评论

On small-depth tree augmentations

引用

OPERATIONS RESEARCH LETTERS 2022年第6期50卷 667-673页

作者： Parekh, Ojas Ravi, R. Zlatin, Michael Sandia Natl Labs Ctr Comp Res Albuquerque NM USA Carnegie Mellon Univ Tepper Sch Business Pittsburgh 15213 PA USA

We study the Weighted Tree Augmentation Problem for general link costs. We show that the integrality gap of the odd-LP relaxation for the (weighted) Tree Augmentation Problem for a k-level tree instance is at most 2 - 2k-11. For 2-and 3-level trees, these ratios are 32 and 74 respectively. Our proofs are constructive and yield polynomial-time approximation algorithms with matching guarantees.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/4.0/).

关键词： approximation algorithm Network design Integrality gap

来源：评论

学校读者我要写书评

暂无评论

Some graph optimization problems with weights satisfying linear constraints

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第1期43卷 200-225页

作者： Nip, Kameng Wang, Zhenbo Shi, Tianning Xiamen Univ Sch Math Sci Xiamen Peoples R China Tsinghua Univ Dept Math Sci Beijing Peoples R China

In this paper, we study several graph optimization problems in which the weights of vertices or edges are variables determined by several linear constraints, including maximum matching problem under linear constraints (max-MLC), minimum perfect matching problem under linear constraints (min-PMLC), shortest path problem under linear constraints (SPLC) and vertex cover problem under linear constraints (VCLC). The objective of these problems is to decide the weights that are feasible to the linear constraints, and find the optimal solutions of corresponding graph optimization problems among all feasible choices of weights. We find that these problems are NP-hard and are hard to be approximated in general. These findings suggest us to explore various special cases of them. In particular, we show that when the number of constraints is a fixed constant, all these problems are polynomially solvable. Moreover, if the total number of distinct weights is a fixed constant, then max-MLC, min-PMLC and SPLC are polynomially solvable, and VCLC has a 2-approximation algorithm. In addition, we propose approximation algorithms for various cases of max-MLC.

关键词： Graph optimization Linear programming Polynomial-time algorithm approximation algorithm Computational complexity

来源：评论

学校读者我要写书评

暂无评论

On-Chip Optical Routing With Provably Good algorithms for Path Clustering and Assignment

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2022年第11期41卷 4653-4666页

作者： Lu, Yu-Sheng Yu, Sheng-Jung Chang, Yao-Wen Natl Taiwan Univ Grad Inst Elect Engn Taipei 106 Taiwan Natl Taiwan Univ Dept Elect Engn Taipei 106 Taiwan

As the VLSI technology continues to scale down, combined with increasing demands for large bandwidth and low-power consumption, the optical interconnections with wavelength-division multiplexing (WDM) become an attractive alternative for on-chip signal transmission. Previous WDM-aware optical routing works consist of three main drawbacks: they are based mainly on heuristics or restricted integer linear programming to handle optical routing, the addressed types of insertion loss, and WDM overheads are incomplete, and the crosstalk noise during concurrent signal transmission is neglected. As a result, no performance guarantees can be achieved on their WDM clustering results, the reliability of the optical network is impaired, and/or their computations are too time consuming. To remedy these disadvantages, we present a new WDM-aware optical routing flow to minimize the insertion loss, the WDM overheads, and the crosstalk noise with a significant speedup. In the proposed flow, the WDM-aware path clustering algorithm guarantees to find an optimal solution for 1-, 2-, and 3-path clustering and has the constant performance bound for most cases of 4-path clustering;the crosstalk-aware path assignment guarantees to minimize the number of crosstalk signal pairs within the given displacement bound. Experimental results based on the ISPD 2007 and 2019 contest benchmarks and a real optical design show that our optical router significantly outperforms published works in wirelength, insertion loss, wavelength power, crosstalk noise, and runtimes.

关键词： Routing Optical crosstalk Optical losses Wavelength division multiplexing Crosstalk Optical interconnections Optical noise approximation algorithm network-on-chip (NoC) physical design routing wavelength-division multiplexing (WDM)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：