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

International Asian School-Seminar Optimization Problems of Complex Systems

作者： Alexandre Khutoretskii Sergei Bredikhin Novosibirsk State University Institute of Computational Mathematics and Mathematical Geophysics SB RAS

ISBN: (纸本)9781728129877

We present a greedy 0.5-approximation algorithm for allocation indivisible jobs in a multiprocessor system. The algorithm uses an ordering of processors according to the non-decreasing of size, and two orderings of items: in nonincreasing utility order and in nonincreasing order of the utility/size ratio. These orderings create two lexicographic orderings on the set I × J (here I is the set of jobs and J is the set of processors). Based on these lexicographic orderings, the algorithm creates an admissible allocation by looking through the pairs (i, j) ∈ I × J in the corresponding order and allocating the job i to processor j if this job is not allocated yet and can be allocated to processor j. The algorithm chooses the best of the two obtained solutions. This algorithm is 0.5-approximate and has running time O(mn) (without sorting), where m and n are the sizes of the sets I and J correspondingly.

关键词： Multiple knapsack problem Lexicographic ordering approximation algorithm approximation ratio approximation algorithms greedy algorithm jobs iodine PROCESSOR Multiprocessor allocation

来源：评论

学校读者我要写书评

暂无评论

Scheduling with Rejection to Minimize the Total Weighted Completion Time

Scheduling with Rejection to Minimize the Total Weighted Com...

引用

第八届运筹学及其应用国际研讨会

作者： Shu-Xia Zhang Zhi-Gang Cao Yu-Zhong Zhang Department of Watercraft Command Zhenjiang Watercraft College Key Laboratory of Management Decision & Information Systems AMSS CAS College of Operations Research and Management Science Qufu Normal University

＜正＞In this paper,we address the scheduling problem with rejection in which we can choose a subset of jobs to *** not to process any job incurs a corresponding *** consider the following problem for the first time:scheduling with rejection to minimize the total weighted completion time with the constraint of total penalties on identical parallel machines,where the number of identical parallel machines is *** show that it is NP-hard and design a pseudo-polynomial time algorithm as well as an FPTAS through dynamic programming.

关键词： Scheduling Rejection Identical parallel machines approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Augmenting edge-connectivity between vertex subsets 09

Augmenting edge-connectivity between vertex subsets

引用

Proceedings of the Fifteenth Australasian Symposium on Computing: The Australasian Theory - Volume 94

作者： Toshimasa Ishii Kazuhisa Makino Otaru University of Commerce Otaru Japan University of Tokyo Tokyo Japan

ISBN: (纸本)9781920682750

Given a graph G = (V, E) and a requirement function r: W1 x W2 → R+ for two families W1, W2 ⊆ 2V - {θ}, we consider the problem (called area-to-area edge-connectivity augmentation problem) of augmenting G by a smallest number of new edges so that the resulting graph G satisfies δG (X) ≥ r(W1, W2) for all X ⊆ V, W1 ∈ W1, and W2 ∈ W2 with W1 ⊆ X ⊆ V - W2, where δG(X) denotes the degree of a vertex set X in G. This problem can be regarded as a natural generalization of the global, local, and node-to-area edge-connectivity augmentation *** this paper, we show that there exists a constant c such that the problem is inapproximable within a ratio of clog α(W1, W2), unless P=NP, even restricted to the directed global node-to-area edge-connectivity augmentation or undirected local node-to-area edge-connectivity augmentation, where α(W1, W2) denotes the number of pairs W1 ∈ W1 and W2 ∈ W2 with r(W1, W2) > 0. We also provide an O(log α (W1, W2))-approximation algorithm for the area-to-area edge-connectivity augmentation problem. This together with the negative result implies that the problem is Θ(log α (W1, W2))-approximable, unless P=NP, which solves open problems for node-to-area edge-connectivity augmentation (Ishii et al. 2008, Ishii and Hagiwara 2006, Miwa and Ito 2004).Furthermore, we characterize the node-to-area and area-to-area edge-connectivity augmentation problems as the augmentation problems with modulotone and extended modulotone functions.

关键词： approximation algorithm graph algorithm modulotone function edge-connectivity

来源：评论

学校读者我要写书评

暂无评论

On-line algorithms for Variable-size and Variable-cost Bin Packing Problems

On-line Algorithms for Variable-size and Variable-cost Bin P...

引用

The Seventh International Conference on Information and Management Sciences

作者： ~(a,b)Rongxia Zhang ~a Shusheng Zhang a School of Mechatronics,Northwestern Polytechnical University,Xi'an 710072,China b China Academy of Space Technology,Beijing 100094,China

Two on-line algorithms for variable-size and variable-cost bin packing problems are *** first algo- rithm,based on the well known HARMONIC algorithm,han- dles the general case with competitive ratio ρ<*** sec- ond... 详细信息

关键词： Packing approximation algorithm Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

The multiple knapsack problem with compatible bipartite graphs

The multiple knapsack problem with compatible bipartite grap...

引用

12th International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA 2015)

作者： Jianping Li Weidong Li Hao Wang Yunnan University Kunming China

The multiple knapsack problem is to pack some items into given knapsacks, such that the sum of the knapsack profits is maximized. This paper is concerned with a variant of the multiple knapsack problem, called the multiple knapsack problem with compatible bipartite graph (MKPCBG), where two items can be packed into the same knapsack only if their corresponding vertices are adjacent in the given compatible bipartite graph. Under two different objectives, we prove that the MKPCBG problem is strongly NP-hard, design some 1/2-approximation algorithms, and design two optimal algorithms for the special case where all knapsacks have the same capacity.

关键词： Multiple knapsack problem approximation algorithm bipartite graph non-approximability optimal algorithm knapsack problems Bipartite graph Optimization algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Conflict-Free Many-to-One Data Aggregation Scheduling in Multi-Channel Multi-Hop Wireless Sensor Networks

Conflict-Free Many-to-One Data Aggregation Scheduling in Mul...

引用

IEEE International Conference on Communications Workshops

作者： Deying Li Qinghua Zhu Hongwei Du Weili Wu Hong Chen Wenping Chen School of Information Renmin University of China Department of Computer Science Technology Harbin Institute of Technology Shenzhen Graduate School Department of Computer Science University of Texas at Dallas

ISBN: (纸本)9781612842325

In this paper, we studied the minimum latency conflict-free many-to-one data aggregation scheduling problem in multi-channel multi-hop wireless sensor networks: Given locations of all sensors and a base station, some sensors which are called as sources, find a schedule such that data from all sources can be transmitted to the base station without any conflict and the latency is minimized. In this model, each sensor has three parameters which are transmission range r, interference range ar and carrier sensing range (beta)r where a, and beta are constant. There are lambda >=1 available channels for communications. We designed an approximation algorithm with ratio ([a/lambda] + 11 [b/lambda]) This work improves our previous work when lambda velence 1. Extensive simulations valuate the performance of the algorithm.

关键词： Conflict-free data aggregation Latency Multi-channel approximation algorithm Sensor networks Wireless sensor networks unified retrieval models Spread spectrum communication approximation algorithms BASE STATION Sensors Communication Research minimum latency Latency

来源：评论

学校读者我要写书评

暂无评论

A Penalized Best-Response algorithm for Nonlinear Single-Path Routing Problems

引用

NETWORKS 2017年第1期69卷 52-66页

作者： Brun, Olivier Prabhu, Balakrishna Vallet, Josselin Univ Toulouse CNRS LAAS Toulouse France Univ Toulouse LAAS F-31400 Toulouse France Viveris Technol 1 Ave Europe F-31400 Toulouse France

This article is devoted to nonlinear single-path routing problems, which are known to be NP-hard even in the simplest cases. For solving these problems, we propose an algorithm inspired from Game Theory in which individual flows are allowed to independently select their path to minimize their own cost function. We design the cost function of the flows so that the resulting Nash equilibrium of the game provides an efficient approximation of the optimal solution. We establish the convergence of the algorithm and show that every optimal solution is a Nash equilibrium of the game. We also prove that if the objective function is a polynomial of degree d >= 1, then the approximation ratio of the algorithm is (2(1/d) - 1)(-d). Experimental results show that the algorithm provides single-path routings with modest relative errors with respect to optimal solutions, while being several orders of magnitude faster than existing techniques. (C) 2016 Wiley Periodicals, Inc.

关键词： best response single-path routing game theory nonlinear programming approximation algorithm Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

Approximating Fixation Probabilities in the Generalized Moran Process 12

Approximating Fixation Probabilities in the Generalized Mora...

引用

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

作者： Josep Diaz Leslie Ann Goldberg George B. Mertzios David Richerby Maria Serna Paul G. Spirakis Departament de Llenguatges i Sistemes Informatics Universitat Politecnica de Catalunya Department of Computer Science University of Liverpool School of Engineering and Computing Sciences Durham University Department of Computer Engineering and Informatics University of Patras

ISBN: (纸本)9781611972108

We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312-316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability proportional to its assigned "fitness" value. It reproduces, placing a copy of itself on a neighbouring vertex chosen uniformly at random, replacing the individual that was there. The initial population consists of a single mutant of fitness r ＞ 0 placed uniformly at random, with every other vertex occupied by an individual of fitness 1. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction); almost surely, these are the only possibilities. In general, exact computation of these quantities by standard Markov chain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible. We show that, with high probability, the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph. This bound allows us to construct fully polynomial randomized approximation schemes (FPRAS) for the probability of fixation (when r ＞ 1) and of extinction (for all r ＞ 0).

关键词： Evolutionary dynamics Markov-chain Monte Carlo approximation algorithm approximation algorithms Probability Fixation fixation Markov chain monte carlo methods vertex head Random Linear system of equations Polynomial Line graph Markov chain

来源：评论

学校读者我要写书评

暂无评论

An improved algorithm for the machine scheduling problem with job delivery coordination

An improved algorithm for the machine scheduling problem wit...

引用

12th International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA 2015)

作者： Yuzhong Zhang Qiongyi Zheng Jianfeng Ren Long Zhang School of Management Qufu Normal University Rizhao China

A two-stage supply chain scheduling problem is considered, where the first stage is job production and the second stage is job delivery. The focus is on the study of the integration of production scheduling with delivery of finished products to customers. In our considered model each job can be processed on either of two identical machines, and then delivered by a vehicle to a customer location. We present an improved algorithm with the worst-case performance ratio 14/9 + ε, which improves the known upper bounds of 2 and 5/3 in [Chang, Y.C. and Lee, C.Y., E. J. O. R., 158 (2004), pp. 470-487; Zhong, W., Dosa, G. and Tan, Z.Y., E. J. O. R., 182(2007), pp. 1057-1072].

关键词： approximation algorithm Job delivery coordination Scheduling Worst-case performance ratio approximation algorithms machine scheduling jobs Obstetric Delivery production control Upper bound

来源：评论

学校读者我要写书评

暂无评论

Stochastic greedy algorithms for maximizing constrained submodular plus supermodular functions

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2023年第17期35卷

作者： Ji, Sai Xu, Dachuan Li, Min Wang, Yishui Zhang, Dongmei Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing Peoples R China Chinese Acad Sci Acad Math & Syst Sci Beijing Peoples R China Shandong Normal Univ Sch Math & Stat Jinan Peoples R China Univ Sci & Technol Beijing Sch Math & Phys Beijing Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

The problem of maximizing the sum of a constrained submodular and a supermodular function has many applications such as social networks, machine learning, and artificial intelligence. In this article, we study the monotone submodular + supermodular maximization problem under a cardinality constraint and a p-system constraint, respectively. For each problem, we provide a stochastic algorithm and prove the approximation ratio of each algorithm theoretically. Since the algorithm of the latter problem can also solve the former problem, we do some numerical experiments of the two algorithms to compare the time as well as the quality of the two algorithms in solving the former problem.

关键词： approximation algorithm constrained stochastic greedy submodular plus supermodular maximization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：