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

On the Approximability of the Stable Matching Problem with Ties of Size Two

algorithmICA 2020年第9期82卷 2668-2686页

作者： Chiang, Robert Pashkovich, Kanstantsin Univ Waterloo Dept Combinator & Optimizat 200 Univ Ave West Waterloo ON N2L 3G1 Canada Univ Ottawa Sch Comp Sci & Elect Engn 800 King Edward Ave Ottawa ON K1N 6N5 Canada

The stable matching problem is one of the central problems of algorithmic game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum cardinality is an NP-hard problem, even when the ties are of size two. Moreover, in this setting it is UGC-hard to provide an approximation with a constant factor smaller than 4/3. In this paper, we give a tight analysis of an approximation algorithm given by Huang and Kavitha for the maximum cardinality stable matching problem with ties of size two, demonstrating an improved 4/3-approximation factor.

关键词： Stable matchings Ties Maximum cardinality approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An Efficient Randomized algorithm for Rumor Blocking in Online Social Networks

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2020年第2期7卷 845-854页

作者： Tong, Guangmo Wu, Weili Guo, Ling Li, Deying Liu, Cong Liu, Bin Du, Ding-Zhu Univ Texas Dallas Jonsson Sch Engn & Comp Sci Dept Comp Sci Erik 800 W Campbell RdMS EC31 Richardson TX 75080 USA Renmin Univ Beijing 100872 Peoples R China Ocean Univ China Sch Math Sci Qingdao 266071 Peoples R China

Social networks allow rapid spread of ideas and innovations while negative information can also propagate widely. When a user receives two opposing opinions, they tend to believe the one arrives first. Therefore, once misinformation or rumor is detected, one containment method is to introduce a positive cascade competing against the rumor. Given a budget k, the rumor blocking problem asks for k seed users to trigger the spread of a positive cascade such that the number of the users who are not influenced by rumor can be maximized. The prior works have shown that the rumor blocking problem can be approximated within a factor of (1-1/e) by a classic greedy algorithm combined with Monte Carlo simulation. Unfortunately, the Monte Carlo simulation based methods are time consuming and the existing algorithms either trade performance guarantees for practical efficiency or vice versa. In this paper, we present a randomized approximation algorithm which is provably superior to the state-of-the art methods with respect to running time. The superiority of the proposed algorithm is demonstrated by experiments done on both the real-world and synthetic social networks.

关键词： approximation algorithms Social network services Integrated circuit modeling Monte Carlo methods Linear programming algorithm design and analysis Greedy algorithms Social networks rumor blocking approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimizing NFV Chain Deployment in Software-Defined Cellular Core

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2020年第2期38卷 248-262页

作者： Zheng, Jiaqi Tian, Chen Dai, Haipeng Ma, Qiufang Zhang, Wei Chen, Guihai Zhang, Gong Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China Microsoft Azure Networking Redmond WA 98052 USA Huawei Technol Co Ltd Labs 2012 Theory Lab Hong Kong Peoples R China

Today's cellular core relies on a few expensive and dedicated hardware racks to connect the radio access network and the egress point to the Internet, which are geographically placed at fixed locations and use the specific routing policies. This inelastic architecture fundamentally leads to increased capital and operating expenses, poor application performance and slow evolution. The emerging paradigm of Network Function Virtualization (NFV) and Software Defined Networking (SDN) bring new opportunities for cellular networks, which makes it possible to flexibly deploy service chains on commodity servers and fine-grained control the routing policies in a centralized way. We present a two-stage optimization framework Plutus. The network-level optimization aims to minimize the service chain deployment cost, while the server-level optimization requires to determine which Virtualized Network Function (VNF) should be deployed onto which CPU core to balance the CPU processing capability. We formulate these two problems as two optimization programs and prove their hardness. Based on parallel multi-block ADMM, we propose a $(\delta, 2)$ -bicriteria approximation algorithm and a learning-based algorithm to address two cases whether the flow information and the resource consumption can be known as a priori, respectively. Large-scale simulations and DPDK-based OpenNetVM platform show that Plutus can reduce the capital cost by 84% and increase the throughput by 36% on average.

关键词： Software Defined Networking (SDN) Network Function Virtualization (NFV) approximation algorithm ADMM

来源：评论

学校读者我要写书评

暂无评论

Eccentricity terrain of δ-hyperbolic graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2020年 112卷 50-65页

作者： Dragan, Feodor F. Guarnera, Heather M. Kent State Univ Dept Comp Sci Algorithm Res Lab Kent OH 44240 USA

A graph G = (V, E) is delta-hyperbolic if for any four vertices u, v, w, x, the two larger of the three distance sums d(u, v) + d(w, x), d(u, w) + d(v, x), d(u, x) + d(v, w) differ by at most 2 delta >= 0. This paper describes the eccentricity terrain of a delta-hyperbolic graph. The eccentricity function e(G) (v) = max{d(v, u) : u is an element of V} partitions vertices of G into eccentricity layers C-k(G) = {v is an element of V : e(G)(v) = rad(G) k}, k is an element of N, where rad(G) = min{e(G)(v) : v is an element of V} is the radius of G. The paper studies the eccentricity layers of vertices along shortest paths, identifying such terrain features as hills, plains, valleys, terraces, and plateaus. It introduces the notion of beta-pseudoconvexity, which implies Gromov's epsilon-quasiconvexity, and illustrates the abundance of pseudoconvex sets in delta-hyperbolic graphs. It shows that all sets C-<= k(G) = {v is an element of V : e(G) (v) <= rad(G) k}, k is an element of N, are (2 delta - 1)-pseudoconvex. Several bounds on the eccentricity of a vertex are obtained which yield a few approaches to efficiently approximating all eccentricities. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Gromov hyperbolicity Eccentricity terrain Radius Diameter Convexity approximation algorithm Complex network analysis

来源：评论

学校读者我要写书评

暂无评论

Minimizing maximum delivery completion time for order scheduling with rejection

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第4期40卷 1044-1064页

作者： Chen, Ren-Xia Li, Shi-Sheng Zhongyuan Univ Technol Dept Appl Math Zhengzhou 450007 Peoples R China Zhongyuan Univ Technol Dept Informat & Computat Sci Zhengzhou 450007 Peoples R China

We study an order scheduling problem with rejection, in which each order consists of multiple product types and each product type should be manufactured on a dedicated machine. The aim is to find a solution to minimize a linear sum of the maximum delivery completion time of the accepted orders and the total penalty of the rejected orders. Even if the delivery times of all orders are zero, the problem is shown to be binary NP-hard in the two-machine case and it is shown to be unary NP-hard when the number of machines is arbitrary. Three approximation algorithms are proposed and their worst-case performance ratios are analyzed. For the scenario where the number of machines is fixed, a pseudo-polynomial dynamic programming algorithm and a fully polynomial time approximation scheme are devised for it.

关键词： Order scheduling Maximum delivery completion time Rejection approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On Parallel and Hitless vSDN Reconfiguration

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2020年第6期28卷 2657-2670页

作者： Zhao, Sicheng Wu, Xing Zhu, Zuqing Univ Sci & Technol China Sch Informat Sci & Technol Hefei 230027 Peoples R China

The symbiosis of network virtualization and software-defined networking (SDN) enables an infrastructure provider (InP) to build various virtual software defined networks (vSDNs) over a shared substrate network (SNT). To handle a dynamic network environment, the InP may need to reconfigure the mapping schemes of vSDNs for a variety of reasons. Although previous studies have addressed how to calculate the new virtual network embedding (VNE) schemes for vSDN reconfiguration under different objectives, the transition to migrate vSDNs from their original VNE schemes to new ones is still under-explored. Hence, this article studies how to realize parallel and hitless vSDN reconfiguration, by leveraging the "make-before-break" scenario. We come up with a generic solution to optimize the transition to remap vSDNs to new VNE schemes, such that the remappings can be done in the parallel, hitless and resource-efficient manner, as long as the new VNE schemes are feasible. More specifically, our proposal is the multi-stage parallel vSDN reconfiguration based on maximal connected reconfigurable subgraph (MCRSG). To ensure the efficiency of our proposal, we formulate the optimization for selecting MCRSGs to reconfigure in each stage, and prove the NP-hardness of the problem. Then, we design an approximation algorithm based on Lagrangian relaxation to solve it time-efficiently. Extensive simulations verify that the proposed algorithm can obtain near-optimal solutions quickly. In addition to the algorithmic study, we also realize our multi-stage parallel vSDN reconfiguration in a practical NVH system, and demonstrate its performance in a real network testbed. Our experimental study identifies in what condition losing of packets during remapping would be inevitable, studies the tradeoff between reconfiguration latency and packet loss rate, and reveal an empirical method to adjust key parameters of our NVH system, for adapting to various network environments.

关键词： Indium phosphide III-V semiconductor materials Virtualization Substrates approximation algorithms Proposals IEEE transactions Network virtualization software-defined networking (SDN) parallel and hitless vSDN reconfiguration Lagrangian relaxation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

High-Dimensional Approximate r-Nets

引用

algorithmICA 2020年第6期82卷 1675-1702页

作者： Avarikioti, Z. Emiris, I. Z. Kavouras, L. Psarros, I Natl Tech Univ Athens Sch Elect & Comp Engn 9 Iroon Polytechniou St Athens 15780 Greece Natl & Kapodistrian Univ Athens Dept Informat & Telecommun Athens 15784 Greece ATHENA Res Ctr Maroussi Greece

The construction of r-nets offers a powerful tool in computational and metric geometry. We focus on high-dimensional spaces and present a new randomized algorithm which efficiently computes approximate r-nets with respect to Euclidean distance. For any fixed epsilon>0the approximation factor is 1+epsilon and the complexity is polynomial in the dimension and subquadratic in the number of points;the algorithm succeeds with high probability. Specifically, we improve upon the best previously known (LSH-based) construction of Eppstein et al. (Approximate greedy clustering and distance selection for graph metrics, 2015. CoRR ) in terms of complexity, by reducing the dependence on epsilon provided that epsilon is sufficiently small. Moreover, our method does not require LSH but follows Valiant's (J ACM 62(2):13, 2015. 10.1145/2728167) approach in designing a sequence of reductions of our problem to other problems in different spaces, under Euclidean distance or inner product, for which r-nets are computed efficiently and the error can be controlled. Our result immediately implies efficient solutions to a number of geometric problems in high dimension, such as finding the (1+epsilon)-approximate k-th nearest neighbor distance in time subquadratic in the size of the input.

关键词： Metric geometry General dimension approximation algorithm r-nets Locality sensitive hashing

来源：评论

学校读者我要写书评

暂无评论

Machine scheduling with soft precedence constraints

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第2期282卷 491-505页

作者： Zhang, An Qi, Xiangtong Li, Guanhua Hangzhou Dianzi Univ Dept Math Hangzhou 310018 Peoples R China Hong Kong Univ Sci & Technol Dept Ind Engn & Decis Analyt Hong Kong Peoples R China Hangzhou Dianzi Univ Zhuoyue Honors Coll Hangzhou 310018 Peoples R China

This paper introduces a new concept, soft precedence constraint (SPC), in machine scheduling problems. Similar to the conventional precedence constraint, SPC specifies some partial order over the jobs;however, an SPC can be violated, but with a certain penalty or cost. The scheduling problem is to balance the tradeoff between the SPC violation penalty and other criteria relative to job completion times. We focus on studying a special case where SPC is defined by a bipartite network. This case is motivated by the berth allocation problem at a transshipment port, where the SPC models any missed container connections from feeder vessels to ocean-going vessels. We discuss the complexity of the problems for different scenarios and develop approximation algorithms. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Scheduling Precedence constraint Soft precedence constraint approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Range assignment of base-stations maximizing coverage area without interference

引用

THEORETICAL COMPUTER SCIENCE 2020年 804卷 81-97页

作者： Acharyya, Ankush De, Minati Nandy, Subhas C. Roy, Bodhayan Indian Stat Inst ACM Unit Kolkata India Indian Inst Technol Delhi Dept Math New Delhi India Indian Inst Technol Kharagpur Dept Math Kharagpur W Bengal India

We study the problem of assigning non-overlapping geometric objects centered at a given set of points such that the sum of area covered by them is maximized. The problem remains open since 2002, as mentioned in a lecture slide of David Eppstein. In this paper, we have performed an exhaustive study on the problem. We show that, if the points are placed in R-2 then the problem is NP-hard even for simplest type of covering objects like disks or squares. In contrast, Eppstein (2017) [10] proposed a polynomial time algorithm for maximizing the sum of radii (or perimeter) of non-overlapping disks when the points are arbitrarily placed in R-2. We show that Eppstein's algorithm for maximizing sum of perimeter of the disks in R-2 gives a 2-approximation solution for the sum of area maximization problem. We also propose a PTAS for the same problem. Our results can be extended in higher dimensions as well as for a class of centrally symmetric convex objects. (C) 2019 Published by Elsevier B.V.

关键词： Quadratic programming Discrete packing Range assignment in wireless communication NP-hardness approximation algorithm PTAS

来源：评论

学校读者我要写书评

暂无评论

Data mule scheduling on a path with handling time and time span constraints

引用

OPTIMIZATION LETTERS 2020年第7期14卷 1701-1710页

作者： Chen, Zhihao Zhang, Zhao Ran, Yingli Shi, Yishuo Du, Ding-Zhu Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China Acad Sinica Inst Informat Sci Taibei 11529 Taiwan Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

In this paper, we study a data mule scheduling problem in which data mules are dispatched from a depot to serve targets located on a path. Every target sensor has a handling time, and every data mule is required to return to the depot before time spanD. The goal is to minimize the number of data mules. For uniform handling time, a linear-time algorithm is presented. For non-uniform handling time, NP-hardness is proved and an approximation algorithm with a guaranteed approximation ratio is presented.

关键词： Data mule scheduling Handling time Time span constraint Computational complexity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：