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

Two-machine flow shop scheduling with an operator non-availability period to minimize makespan

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第4期39卷 1060-1078页

作者： Li, Dawei Lu, Xiwen East China Univ Sci & Technol Sch Sci 130 Meilong Rd Shanghai 200237 Peoples R China

In this paper, we consider the two-machine flow shop scheduling with an operator non-availability period in the first stage to minimize makespan, where the operator non-availability period is an open time interval in which a job can neither start nor complete. We first prove that the problem is NP-hard, even if the length of the operator non-availability period is no more than the processing time of any job on the first machine. Then we show that Johnson's rule is a 2-approximation algorithm and the bound is tight. Moreover, a better tight 3/2-approximation algorithm is provided.

关键词： Flow shop scheduling Operator non-availability approximation algorithm Worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

Reducing Isotropy and Volume to KLS: An O*(n³ψ²) Volume algorithm 2021

Reducing Isotropy and Volume to KLS: An <i>O</i>*(<i>n</i><S...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Jia, He Laddha, Aditi Lee, Yin Tat Vempala, Santosh Georgia Inst Technol Atlanta GA 30332 USA Univ Washington Seattle WA 98195 USA Microsoft Res Seattle WA USA

ISBN: (纸本)9781450380539

We show that the volume of a convex body in R-n in the general membership oracle model can be computed to within relative error epsilon using (O) over tilde (n(3)psi(2)/epsilon(2)) oracle queries, where psi is the KLS constant. With the current bound of psi = O(n(o(1))), this gives an (O) over tilde (n(3+o(1))/epsilon(2)) algorithm, the first improvement on the Lovasz-Vempala (O) over tilde (n(4)/epsilon(2)) algorithm from 2003. The main new ingredient is an (O) over tilde (n(3)psi(2)) algorithm for isotropic transformation, following which we can apply the (O) over tilde (n(3)/epsilon(2)) volume algorithm of Cousins and Vempala for well-rounded convex bodies. A positive resolution of the KLS conjecture would imply an (O) over tilde (n(3)/epsilon(2)) volume algorithm. We also give an efficient implementation of the new algorithm for convex polytopes defined by m inequalities in R-n: polytope volume can be estimated in time (O) over tilde (mn(c)/epsilon(2)) where c < 3.2 depends on the current matrix multiplication exponent and improves on the previous best bound.

关键词： Markov chain Monte Carlo approximation algorithm Volume Computation

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm of the RNA Pseudoknotted Structure Prediction Baesed on MFE

Approximation Algorithm of the RNA Pseudoknotted Structure P...

引用

IEEE International Conference on Information and Automation

作者： Zhendong Liu Yuejun Li Peng Zhang Zhaohui Yang Sch. of Comput. Sci. &amp Technol. Shandong Jianzhu Univ. Jinan China|c|

ISBN: (纸本)9781479913329;9781479940998

Determination of Ribonucleic Acid structure is challenging, in order to optimize the RNA pseudoknotted structure, the paper investigates the computational problem and complexity of predicting RNA structure. A new computational method and model with minimum free energy are adopted to predict RNA structure. The main contribution of the paper is to achieves an efficient approximation algorithm for finding RNA pseudoknotted structure and nested structures. We have compared with other algorithms in time complexity and space complexity, the approximation algorithm takes O(n~3) time and O(n~2) space, where n is the length of the RNA sequences. The experimental tests for a large database of RNA show that the algorithm is more exact and effective than the algorithms, the algorithm can predict arbitrary pseudoknots, and improve the a predicting accuracy.

关键词： RNA Pseudoknotted structure Minimum free energy Stacking pairs approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating the τ-relaxed soft capacitated facility location problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第3期40卷 848-860页

作者： Han, Lu Xu, Dachuan Xu, Yicheng Zhang, Dongmei Chinese Acad Sci Acad Math & Syst Sci Beijing 100190 Peoples R China Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

In this paper, we consider the tau-relaxed soft capacitated facility location problem (tau-relaxed SCFLP), which extends several well-known facility location problems like the squared metric soft capacitated facility location problem (SMSCFLP), soft capacitated facility location problem (SCFLP), squared metric facility location problem and uncapacitated facility location problem. In the tau-relaxed SCFLP, we are given a facility set F, a client set and a parameter tau >= 1. Every facility i is an element of F has a capacity u(i) and an opening cost f(i), and can be opened multiple times. If facility i is opened l times, this facility can be connected by at most lu(i) clients and incurs an opening cost of l f(i). Every facility-client pair has a connection cost. Under the assumption that the connection costs are non-negative, symmetric and satisfy the tau-relaxed triangle inequality, we wish to open some facilities (once or multiple times) and connect every client to an opened facility without violating the capacity constraint so as to minimize the total opening costs as well as connection costs. As our main contribution, we propose a primal-dual based (3 tau + 1)-approximation algorithm for the tau-relaxed SCFLP. Furthermore, our algorithm not only extends the applicability of the primal-dual technique but also improves the previous approximation guarantee for the SMSCFLP from 11.18 + epsilon to 10.

关键词： Facility location problem Relaxed triangle inequality Soft capacitated approximation algorithm Primal-dual

来源：评论

学校读者我要写书评

暂无评论

Continuous Activity Maximization in Online Social Networks

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2020年第4期7卷 2775-2786页

作者： Guo, Jianxiong Chen, Tiantian Wu, Weili Univ Texas Dallas Erik Jonsson Sch Engn & Comp Sci Dept Comp Sci Dallas TX 75080 USA

Activity maximization is a task of seeking a small subset of users in a given social network that makes the expected total activity benefit maximized. This is a generalization of many real applications. In this paper, we extend activity maximization problem to that under the general marketing strategy x, which is a d-dimensional vector from a lattice space and has probability h(u)(x) to activate a node u as a seed. Based on that, we propose the continuous activity maximization (CAM) problem, where the domain is continuous and the seed set we select conforms to a certain probability distribution. It is a new topic to study the problem about information diffusion under the lattice constraint, thus, we address the problem systematically here. First, we analyze the hardness of CAM and how to compute the objective function of CAM accurately and effectively. We prove this objective function is monotone, but not DR-submodular and not DR-supermodular. Then, we develop a monotone and DR-submodular lower bound and upper bound of CAM, and apply sampling techniques to design three unbiased estimators for CAM, its lower bound and upper bound. Next, adapted from IMM algorithm and sandwich approximation framework, we obtain a data-dependent approximation ratio. This process can be considered as a general method to solve those maximization problem on lattice but not DR-submodular. Last, we conduct experiments on three real-world datasets to evaluate the correctness and effectiveness of our proposed algorithms.

关键词： Lattices approximation algorithms Social networking (online) Linear programming Upper bound Computational modeling Monte Carlo methods Activity Maximization approximation algorithm DR-submodular Lattice Sampling Techniques Sandwich approximation Framework Social Networks

来源：评论

学校读者我要写书评

暂无评论

Influence maximization problem: properties and algorithms

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第4期40卷 907-928页

作者： Yang, Wenguo Zhang, Yapu Du, Ding-Zhu Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA

The influence maximization problem has become one of the fundamental combinatorial optimization problems over the past decade due to its extensive applications in social networks. Although a 1-1/e approximation ratio is easily obtained using a greedy algorithm for the submodular case, how to solve the non-submodular case and enhance the solution quality deserve further study. In this paper, based on the marginal increments, we devise a non-negative decomposition property for monotone function and a non-increasing decomposition property for monotone submodular function (NDP). According to the exchange improvement (EI), a necessary condition for an optimal solution is also proposed. With the help of NDP and EI condition, an exchange improvement algorithm is proposed to improve further the quality of the solution to the non-submodular influence maximization problem. For the influence maximization, we devise effective methods to compute the influence spread and marginal gain in a successive iteration update manner. These methods make it possible to calculate the influence spread directly and accurately. Next, we design a data-dependent approximation algorithm for a non-submodular topology change problem from a marginal increment perspective.

关键词： Submodular function Marginal increment approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Chromatic cost coloring of weighted bipartite graphs

引用

APPLIED MATHEMATICS AND COMPUTATION 2020年第0期375卷 125073-000页

作者： Pikies, Tytus Kubale, Marek Gdansk Univ Technol ETI Fac Dept Algorithms & Syst Modelling Gabriela Narutowicza 11-12 PL-80233 Gdansk Poland

Given a graph G and a sequence of color costs C, the Cost Coloring optimization problem consists in finding a coloring of G with the smallest total cost with respect to C. We present an analysis of this problem with respect to weighted bipartite graphs. We specify for which finite sequences of color costs the problem is NP-hard and we present an exact polynomial algorithm for the other finite sequences. These results are then extended to a substantial class of infinite sequences. We show that these results on both types of sequences partially transfer to unweighted bipartite graphs. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Chromatic cost coloring Optimum cost chromatic partition Weighted graph Bipartite graph approximation algorithm Chromatic cost 3-pseudocoloring

来源：评论

学校读者我要写书评

暂无评论

Temporal vertex cover with a sliding time window

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2020年 107卷 108-123页

作者： Akrida, Eleni C. Mertzios, George B. Spirakis, Paul G. Zarnaraev, Viktor Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Durham Dept Comp Sci Durham England

Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs focused on temporal paths and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal problems. In this paper we introduce and study two natural temporal extensions of the classical problem VERTEX COVER. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. We provide strong hardness results, complemented by approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Temporal networks Temporal vertex cover Exponential Time Hypothesis (ETH) approximation algorithm approximation hardness

来源：评论

学校读者我要写书评

暂无评论

On scheduling multiple two-stage flowshops

引用

THEORETICAL COMPUTER SCIENCE 2020年 818卷 74-82页

作者： Wu, Guangwei Chen, Jianer Wang, Jianxin Cent South Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China Cent South Univ Forestry & Technol Coll Comp & Informat Engn Changsha 410004 Hunan Peoples R China Guangzhou Univ Sch Comp Sci & Educ Software Guangzhou 510006 Guangdong Peoples R China Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

This paper studies the problem of scheduling n two-stage jobs on m multiple two-stage flowshops, with the objective of minimizing the makespan. The problem is NP-hard even when m is a fixed constant, and becomes strongly NP-hard when m is part of the input. A 2.6-approximation algorithm along with its analysis is presented for an arbitrary m >= 2. This is the first approximation algorithm for multiple flowshops when the number m of flowshops is part of the input. The fact that m is part of the input and the time complexity 0 logn) of the algorithm demonstrate that the problem, which plays an important role in the current research in cloud computing and data centers, can be solved efficiently with a reasonable level of satisfaction. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Scheduling Multiple two-stage flowshops approximation algorithm Cloud computing

来源：评论

学校读者我要写书评

暂无评论

Placement of Unmanned Aerial Vehicles for Directional Coverage in 3D Space

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2020年第2期28卷 888-901页

作者： Wang, Weijun Dai, Haipeng Dong, Chao Cheng, Xiao Wang, Xiaoyu Yang, Panlong Chen, Guihai Dou, Wanchun Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China Univ Goettingen Fac Math & Comp Sci D-37073 Gottingen Germany Nanjing Univ Aeronaut & Astronaut Coll Elect & Informat Engn Nanjing 210007 Peoples R China Univ Sci & Technol China Sch Comp Sci & Technol Hefei 230026 Peoples R China

This paper considers the fundamental problem of Placement of unmanned Aerial vehicles achieviNg 3D Directional coverAge (PANDA), that is, given a set of objects with determined positions and orientations in a 3D space, deploy a fixed number of UAVs by adjusting their positions and orientations such that the overall directional coverage utility for all objects is maximized. First, we establish the 3D directional coverage model for both cameras and objects. Then, we propose a Dominating Coverage Set (DCS) extraction method to reduce the infinite solution space of PANDA to a limited one without performance loss. Finally, we model the reformulated problem as maximizing a monotone submodular function subject to a matroid constraint and present a greedy algorithm with $1-1/e$ approximation ratio to address this problem. We conduct simulations and field experiments to evaluate the proposed algorithm, and the results show that our algorithm outperforms comparison ones by at least 75.4%.

关键词： Placement UAV approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：