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

On the Approximability of Related Machine Scheduling Under Arbitrary Precedence

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2021年第3期18卷 3706-3718页

作者： Aggarwal, Vaneet Lan, Tian Subramaniam, Suresh Xu, Maotong Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA George Washington Univ Dept Elect & Comp Engn Washington DC 20052 USA Facebook News Feed Menlo Pk CA 94025 USA

Distributed computing systems often need to consider the scheduling problem involving a collection of highly dependent data-processing tasks that must work in concert to achieve mission-critical objectives. This paper considers the unrelated machine scheduling problem for minimizing weighted sum completion time under arbitrary precedence constraints and on heterogeneous machines with different processing speeds. The problem is known to be strongly NP-hard even in the single machine setting. By making use of Queyranne's constraint set and constructing a novel Linear Programming relaxation for the scheduling problem under arbitrary precedence constraints, our results in this paper advance the state of the art. We develop a 2(1 + (m-1)/D)-approximation algorithm (and 2(1 + (m-1)/D) + 1-approximation) for the scheduling problem with zero release time (and arbitrary release time), where m is the number of servers and D is the task-skewness product. The algorithm can be efficiently computed in polynomial time using the Ellipsoid method and achieves nearly optimal performance in practice as D > O(m) when the number of tasks per job to schedule is sufficiently larger than the number of machines available. Our implementation and evaluation using a heterogeneous testbed and real-world benchmarks confirms significant improvement in weighted sum completion time for dependent computing tasks.

关键词： Related machine scheduling precedence constraints directed acyclic graph approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Tree Augmentation Problem

引用

algorithmICA 2021年第2期83卷 553-575页

作者： Nutov, Zeev Open Univ Israel Dept Math & Comp Sci Raanana Israel

In the TREE AUGMENTATIONproblem we are given a treeT=(V,F)\ and a setE subset of VxVof edges with positive integer costs{ce:e is an element of E}. The goal is to augmentTby a minimum cost edge setJ subset of Esuch that T?Jis 2-edge-connected. We obtain the following results. -Recently, Adjiashvili [SODA 17] introduced a novel LP for the problem and used it to break the 2-approximation barrier for instances when the maximum cost of an edge in is bounded by a constant;his algorithm computes a1.96418+epsilon approximate solution in timen(M/epsilon 2)O(1)\. Using a simpler LP, we achieve ratio127+epsilon in time2O(M/epsilon 2)poly(n). This gives ratio better than 2 for logarithmic costs, and not only for constant costs. One of the oldest open questions for the problem is whether for unit costs (whenM=1) the standard LP-relaxation, so calledCut-LP, has integrality gap less than 2. We resolve this open question by proving that for unit costs the integrality gap of theCut-LPis at most28/15=2-2/15. In addition, we will prove that another natural LP-relaxation, that is much simpler than the ones in previous work, has integrality gap at most 7/4.

关键词： Tree augmentation approximation algorithm Extreme points Integrality gap

来源：评论

学校读者我要写书评

暂无评论

Approximating Max k-Uncut via LP-rounding plus greed, with applications to Densest k-Subgraph

引用

THEORETICAL COMPUTER SCIENCE 2021年 849卷 173-183页

作者： Zhang, Peng Liu, Zhendong Shandong Univ Sch Software Jinan 250101 Shandong Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China

The Max k-Uncut problem arose from the study of homophily of large-scale networks. Given an n-vertex undirected graph G = (V, E) with nonnegative weights defined on edges and a positive integer k, the Max k-Uncut problem asks to find a partition {V-1, V-2, ... , V-k} of V such that the total weight of edges that are not cut is maximized. This problem is the complement of the classic Min k-Cut problem, and was proved to have surprisingly rich connection to the Densest k-Subgraph problem. In this paper, we give an approximation algorithm for Max k-Uncut using a non-uniform approach combining LP-rounding and the greedy strategy. The algorithm partitions the vertices of G into at least (1 - 1/e)k parts in expectation, and achieves a good expected approximation ratio 1/2(1 + (n-k/n)(2)). (C) 2020 Elsevier B.V. All rights reserved.

关键词： Max k-Uncut k-Subgraph approximation algorithm LP-rounding Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Wafer Defect Inspection Optimization With Partial Coverage-A Numerical Approach

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2021年第4期18卷 1916-1927页

作者： Qin, Ming Shi, Zhongshun Chen, Weiwei Gao, Siyang Shi, Leyuan Peking Univ Dept Ind Engn & Management Beijing 100871 Peoples R China Univ Tennessee Dept Ind & Syst Engn Knoxville TN 37996 USA Rutgers State Univ Dept Supply Chain Management Piscataway NJ 08854 USA City Univ Hong Kong Dept Syst Engn & Engn Management Hong Kong Peoples R China Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA

Electron beam inspection (EBI) with high resolution is a promising technique to improve the defect inspection on the surface of patterned wafer. However, high resolution usually means long inspection time, which results in the low throughput and limitation of EBI applied in practice. This study aims to optimize the inspection time of EBI by reducing the total number of inspection regions without loss of the accuracy. We first refine this defect inspection optimization problem as a partial congruent square cover problem. Then, we propose two novel mixed-integer linear programming models for this problem. To deal with the large-scale problems, an approximation algorithm is developed to obtain the high-quality solutions. This approximation algorithm efficiently utilizes the linear programming (LP) rounding technique and greedy strategy based on the proposed model. Compared with the existing algorithms in the literature, numerical results show the superiority of the proposed model and algorithm. Note to Practitioners-Defect inspection is a key process in wafer fabrication for identifying and inspecting the patterning defects generated during the complicated fabrication processes. Electron beam inspection (EBI) takes place of optical inspection gradually as the design rules keep shrinking and the circuits are more susceptible to nanoscale killer defects. Low throughput is the main drawback of EBI and the improvements on throughput have far-reaching significance on the high volume manufacturing of semiconductor products. This study aims to reduce the number of inspection regions to improve the total inspection time in the EBI process. Considering that the inspection time for each inspection region is constant, less inspection regions means less total inspection time. However, the positions of inspection regions are arbitrary across the continuous planar space, putting pressure on modeling and solving the problem. A preprocessing algorithm is designed to discover a limited

关键词： Inspection approximation algorithms Optimization Numerical models Throughput Tools Electron beams approximation algorithm electron beam inspection (EBI) mixed-integer linear programming (MILP) partial covering optimization wafer defect inspection

来源：评论

学校读者我要写书评

暂无评论

Multiproduct Newsvendor Problem with Customer-Driven Demand Substitution: A Stochastic Integer Program Perspective

引用

INFORMS JOURNAL ON COMPUTING 2021年第3期33卷 1229-1244页

作者： Zhang, Jie Xie, Weijun Sarin, Subhash C. Virginia Tech Dept Ind & Syst Engn Blacksburg VA 24061 USA

This paper studies a multiproduct newsvendor problem with customer-driven demand substitution, where each product, once run out of stock, can be proportionally substituted by the others. This problem has been widely studied in the literature;however, because of nonconvexity and intractability, only limited analytical properties have been reported and no efficient approaches have been proposed. This paper first completely characterizes the optimal order policy when the demand is known and reformulates this nonconvex problem as a binary quadratic program. When the demand is random, we formulate the problem as a two-stage stochastic integer program, derive several necessary optimality conditions, prove the submodularity of the profit function, and also develop polynomial-time approximation algorithms and show their performance guarantees. We further propose a tight upper bound via nonanticipativity dual, which is proven to be very close to the optimal value and can yield a good-quality feasible solution under a mild condition. Our numerical investigation demonstrates effectiveness of the proposed algorithms. Moreover, several useful findings and managerial insights are revealed from a series of sensitivity analyses.

关键词： newsvendor problem demand substitution stochastic program submodularity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

APPROXIMATE 1-NORM MINIMIZATION AND MINIMUM-RANK STRUCTURED SPARSITY FOR VARIOUS GENERALIZED INVERSES VIA LOCAL SEARCH\ast

引用

SIAM JOURNAL ON OPTIMIZATION 2021年第3期31卷 1722-1747页

作者： Xu, Luze Fampa, Marcia Lee, Jon Ponte, Gabriel Univ Michigan Dept Ind & Operat Engn Ann Arbor MI 48109 USA Univ Fed Rio de Janeiro BR-21941901 Rio De Janeiro RJ Brazil

Fundamental in matrix algebra and its applications, a generalized inverse of a real matrix A is a matrix H that satisfies the Moore-Penrose (M--P) property AHA = A. If H also satisfies the additional useful M--P property, HAH = H, it is called a reflexive generalized inverse. Reflexivity is equivalent to minimum rank, so we are particularly interested in reflexive generalized inverses. We consider aspects of symmetry related to the calculation of a sparse reflexive generalized inverse of A. As is common, and following Fampa and Lee [Oper. Res. Lett., 46 (2018), pp. 605--610] for calculating sparse generalized inverses, we use (vector) 1-norm minimization for inducing sparsity and for keeping the magnitude of entries under control. When A is symmetric, we may naturally desire a symmetric H, while generally such a restriction on H may not lead to a 1-norm minimizing reflexive generalized inverse. We investigate a block construction method to produce a symmetric reflexive generalized inverse that is structured and has guaranteed sparsity. We provide a theoretically efficient and practical local-search algorithm to block construct an approximate 1-norm minimizing symmetric reflexive generalized inverse. Another aspect of symmetry that we consider relates to another M--P property: H is ah-symmetric if AH is symmetric. The ah-symmetry property is the key one for solving least-squares problems using H. Here we do not assume that A is symmetric, and we do not impose symmetry on H. We investigate a column block construction method to produce an ah-symmetric reflexive generalized inverse that is structured and has guaranteed sparsity. We provide a theoretically efficient and practical local-search algorithm to column block construct an approximate 1-norm minimizing ah-symmetric reflexive generalized inverse.

关键词： generalized inverse sparse optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Degree-anonymization using edge rotations

引用

THEORETICAL COMPUTER SCIENCE 2021年 873卷 1-15页

作者： Bazgan, Cristina Cazals, Pierre Chlebikova, Janka Univ PSL Univ Paris Dauphine CNRS LAMSADE F-75016 Paris France Univ Portsmouth Sch Comp Portsmouth Hants England

The MIN ANONYMOUS-EDGE-ROTATION problem asks for an input graph G and a positive integer k to find a minimum number of edge rotations that transform G into a graph such that for each vertex there are at least k 1 other vertices of the same degree (a k-degree-anonymous graph). In this paper, we prove that the MIN ANONYMOUS-EDGE-ROTATION problem is NP-hard even for k = n/q, where n is the order of a graph and q any positive integer, q >= 3. We argue that under some constrains on the number of edges in a graph and k, MIN ANONYMOUS-EDGE-ROTATION is polynomial-time 2-approximable. Furthermore, we show that the problem is solvable in polynomial time for any graph when k = n and for trees when k = theta(n). Additionally, we establish sufficient conditions for an input graph and k such that a solution for MIN ANONYMOUS-EDGE-ROTATION exists. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Degree-anonymization NP-hardness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第4期41卷 888-904页

作者： Lv, Wei Wu, Chenchen Tianjin Renai Coll Comp Sci & Technol Dept Tianjin 306136 Peoples R China Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China

Facility location problem is a well established research area within Operations Research. Capacitated facility location problem is one of the most important variants, in which each facility has an upper bound on the demand, i.e., capacity. Moreover, the integrality gap of the natural linear program relaxation for the problem is infinite. Fortunately, the gap is finite when all opening costs for the facilities are the same. We consider a capacity facility location problem with penalties in which it is allowed some customers are not served by facilities and all opening costs are uniform. Based on LP-rounding framework, we propose a 5.732-approximation algorithm.

关键词： Capacitated facility location problem approximation algorithm Linear program

来源：评论

学校读者我要写书评

暂无评论

Multi-robot exploration on grids with a bounded time

引用

SCIENTIA IRANICA 2021年第3期28卷 1515-1528页

作者： Davoodi, M. Delfaraz, E. Ghobadi, S. Masoori, M. Inst Adv Studies Basic Sci Dept Comp Sci & Informat Technol Gavazang Zanjan Iran

In this paper, the problem of exploring a grid environment in the offline setting is studied. The goal is to propose an algorithm to find the minimum number of robots for exploring a rectangular grid environment, with n rows and m columns, denoted by R(n, m) at a predefined time T. In case of no obstacles in the environment, an optimal solution is proposed for the problem. In another case when the environment may contain some obstacles, it is pointed out that the problem is NP-complete and it cannot be approximated within better than a factor 2. Finally, a 4-approximation algorithm is presented in order to explore R(n, m) in the presence of obstacles. (C) 2021 Sharif University of Technology. All rights reserved.

关键词： approximation algorithm Path planning Exploration Grid environments Lower bound

来源：评论

学校读者我要写书评

暂无评论

Energy-Efficient Topology Construction via Power Allocation for Decentralized Learning via Smart Devices With Edge Computing

IEEE TRANSACTIONS ON GREEN COMMUNICATIONS AND NETWORKING

引用

IEEE TRANSACTIONS ON GREEN COMMUNICATIONS AND NETWORKING 2021年第4期5卷 1806-1819页

作者： Kuo, Jian-Jhih Ching, Cheng-Wei Huang, Hung-Sheng Liu, Yu-Chun Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 621 Taiwan Natl Chung Cheng Univ Adv Inst Mfg High Tech Innovat Chiayi 621 Taiwan Natl Chung Cheng Univ Dept Elect Engn Chiayi 621 Taiwan

Data privacy preservation has drawn much attention in emerging machine learning applications. Decentralized learning among smart devices over wireless networks is thus developed to guarantee data security and eliminate the involvement of parameter servers to avoid transmission bottlenecks. However, the previous research focuses on data compression and exchange rules of model parameters among smart devices. Still, it neglects the interplay between link cardinality, transmission power consumption, and collision in transmission. To jointly optimize these issues, in this paper, we first set collision and interference aside and formulate a new optimization problem, named GreenDL, and then extend GreenDL to be collision-aware, namely, GreenDL-CA, by restricting the maximum degree of each smart devices. We prove their hardness and propose two approximation algorithms dubbed as CoTRAIN and CoTRAIN-CA for GreenDL and GreenDL-CA, respectively. Experiment and simulation results manifest that both CoTRAIN and CoTRAIN-CA reduce more than 20% power compared with the other heuristics without sacrificing the convergence rate in the decentralized learning practices.

关键词： Smart devices Training data Performance evaluation Servers Energy conservation Data models Power demand Decentralized learning topology construction energy conservation wireless communication NP-hardness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：