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

Polylogarithmic approximation algorithms for Weighted-F-deletion Problems

ACM TRANSACTIONS ON algorithmS 2020年第4期16卷 1–38页

作者： Agrawal, Akanksha Lokshtanov, Daniel Misra, Pranabendu Saurabh, Saket Zehavi, Meirav Ben Gurion Univ Negev Dept Comp Sci Alon Bldg IL-84105 Beer Sheva Israel Univ Calif Santa Barbara Dept Comp Sci 2104 Harold Frank Hall Santa Barbara CA 93106 USA Max Planck Inst Informat Dept Algorithms & Complex Campus E1 4Saarland Informat Campus D-66123 Saarbrucken Germany Univ Bergen Dept Informat N-5020 Bergen Norway HBNI Inst Math Sci Chennai 600113 Tamil Nadu India

For a family of graphs F, the WEIGHTED F VERTEX DELETION problem, is defined as follows: given an n-vertex undirected graph G and a weight function w : V(G) -> R, find a minimum weight subset S subset of V(G) such thatG - S belongs to F. We devise a recursive scheme to obtain O(log(O(1)) n)-approximation algorithms for such problems, building upon the classical technique of finding balanced separators. We obtain the first O(log(O(1)) n)-approximation algorithms for the following problems. Let F be a finite set of graphs containing a planar graph, and F = G(F) be the maximal family of graphs such that every graph H is an element of G(F) excludes all graphs in F as minors. The vertex deletion problem corresponding to F = G(F) is the WEIGHTED PLANAR F-MINOR-FREE DELETION (WP F-MFD) problem. We give a randomized and a deterministic approximation algorithms for WP F-MFD with ratios O(log(1.5) n) and O(log(2) n), respectively. Prior to our work, a randomized constant factor approximation algorithm for the unweighted version was known [FOCS 2012]. After our work, a deterministic constant factor approximation algorithm for the unweighted version was also obtained [SODA 2019]. We give an O(log(2) n)-factor approximation algorithm for WEIGHTED CHORDAL VERTEX DELETION, the vertex deletion problem to the family of chordal graphs. On the way to this algorithm, we also obtain a constant factor approximation algorithm for MULTICUT on chordal graphs. We give an O(log(3) n)-factor approximation algorithm for WEIGHTED DISTANCE HEREDITARY VERTEX DELETION. We believe that our recursive scheme can be applied to obtain O(log(O(1)) n)-approximation algorithms for many other problems as well.

关键词： approximation algorithm balanced separators chordal graphs Planar F-minor-free graphs distance hereditary graphs F-Vertex Deletion

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for two-stage flowshops scheduling problem

引用

THEORETICAL COMPUTER SCIENCE 2020年 806卷 509-515页

作者： Wu, Guangwei Chen, Jianer Wang, Jianxin Cent South Univ Sch Comp 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 considers the problem of scheduling n two-stage jobs on m two-stage flowshops so as to minimize the makespan. By studying the relationship between the problem and the classical MAKESPAN problem, we prove that if there is an alpha-approximation algorithm for the MAKESPAN problem, then for the general case of the problem, we can construct a 2 alpha-approximation algorithm, and for two restricted cases which are of practical importance, we can construct an (alpha + 1/2)-approximation algorithm. As a result, by employing the polynomial-time approximation scheme for the MAKESPAN problem, we get a (2 + epsilon-approximation algorithm for the general case and a (1.5 + epsilon)-approximation algorithm for the two restricted cases, which significantly improve the previous approximation ratios 2.6 and 11/6 respectively. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Scheduling Flowshops approximation algorithm MAKESPAN

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for Path Vertex Covers in Regular Graphs

引用

algorithmICA 2020年第10期82卷 3041-3064页

作者： Zhang, An Chen, Yong Chen, Zhi-Zhong Lin, Guohui Hangzhou Dianzi Univ Dept Math Hangzhou 350018 Peoples R China Tokyo Denki Univ Div Informat Syst Design Saitama 3500394 Japan Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

Given a simple graph G=(V,E) and a constant integer k >= 2, the k-path vertex cover problem (PkVC) asks for a minimum subset F subset of V of vertices such that the induced subgraph G[V-F]does not contain any path of order k. When k=2, this turns out to be the classic vertex cover (VC) problem, which admits a 1log|V|-approximation. The general PkVC admits a trivial k-approximation;when k=3and k=4, the best known approximation results are a 2-approximation and a 3-approximation, respectively. On d-regular graphs, the approximation ratios can be reduced to min2-5d+3+epsilon,2-(2-o(1))loglogdlogd for VC (i.e. , P2VC), 2-1d+4d-23d|V| for P3VC, Ld/2 RIGHT FLOOR(2d-2)(Ld/2 RIGHT FLOOR+1)(d-2) for P4VC, and 2d-k+2d-k+2 for PkVC when 1 <= k-2algorithm for graph defective coloring, we first present a Ld/2 RIGHT FLOOR(2d-k+2)(Ld/2 RIGHT FLOOR+1)(d-k+2)-approximation for PkVC on d-regular graphs when 1 <= k-2approximation results for PkVC on d-regular graphs for k >= 3, except for P4VC it ties with the best prior work and in particular they tie at 2 on cubic graphs and 4-regular graphs. We then propose a (1.875+epsilon)-approximation and a 1.852-approximation for P4VC on cubic graphs and 4-regular graphs, respectively. We also present a better approximation algorithm for P4VC on d-regular bipartite graphs.

关键词： Path vertex cover Regular graph Defective coloring Maximum independent set approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments

引用

JOURNAL OF SCHEDULING 2020年第5期23卷 595-608页

作者： Dong, Jianming Chang, Joshua Su, Bing Hu, Jueliang Lin, Guohui Zhejiang Sci Tech Univ Dept Math Hangzhou Zhejiang Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Xian Technol Univ Sch Econ & Management Xian Shaanxi Peoples R China

We study a scheduling environment that finds many real-world manufacturing applications, in which there is a close connection between a hybrid multiprocessor open shop and multiple parallel identical flow shops. In this environment, there is an extended two-stage open shop, where in one stage we have a set of parallel identical machines, while in the other we have a two-machine flow shop. Our objective is to minimize the makespan, that is, the latest completion time of all jobs. We pursue approximation algorithms with provable performance, and we achieve a 2-approximation when the number of parallel identical machines is constant or is part of the input;we also design a 5/3-approximation for the special case where there is only one machine in the multiprocessor stage, which remains weakly NP-hard. Our empirical experiments show that both approximation algorithms perform much better in simulated instances;their average ratios over the proposed lower bound are around 1.5 and 1.2, respectively.

关键词： Scheduling Extended two-stage open shop Two-machine flow shop Multiprocessor approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

FPT approximation for Capacitated Sum of Radii 15

FPT Approximation for Capacitated Sum of Radii

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Jaiswal, Ragesh Kumar, Amit Yadav, Jatin IIT Delhi CSE Delhi India

ISBN: (纸本)9783959773096

We consider the capacitated clustering problem in general metric spaces where the goal is to identify k clusters and minimize the sum of the radii of the clusters (we call this the CAPACITATED k-sumRADii problem). We are interested in fixed-parameter tractable (FPT) approximation algorithms where the running time is of the form f (k) " poly(n), where f (k) can be an exponential function of k and n is the number of points in the input. In the uniform capacity case, Bandyapadhyay et al. recently gave a 4-approximation algorithm for this problem. Our first result improves this to an FPT 3-approximation and extends to a constant factor approximation for any Lp norm of the cluster radii. In the general capacities version, Bandyapadhyay et al. gave an FPT 15-approximation algorithm. We extend their framework to give an FPT (4-V13)-approximation algorithm for this problem. Our framework relies on a novel idea of identifying approximations to optimal clusters by carefully pruning points from an initial candidate set of points. This is in contrast to prior results that rely on guessing suitable points and building balls of appropriate radii around them. On the hardness front, we show that assuming the Exponential Time Hypothesis, there is a constant c> 1 such that any c-approximation algorithm for the non-uniform capacity version of this (kproblem requires running time 2(Omega) (k/polylog(k)).

关键词： approximation algorithm parameterized algorithm clustering

来源：评论

学校读者我要写书评

暂无评论

New approximation algorithms for machine scheduling with rejection on single and parallel machine

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第4期40卷 929-952页

作者： Liu, Peihai Lu, Xiwen East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

In this paper we consider three machine scheduling problems with the special feature that jobs may be rejected at a certain penalty. There are n jobs which are characterized by a release date, a processing time and a penalty. Each job is either accepted and then processed by one machine, or rejected and then a rejection penalty is paid. The objective is to minimize the maximum completion time of all accepted job plus the total penalties of all rejected jobs. When jobs have identical release dates, we present a (3/2 - 1/2m)-approximation algorithm for the parallel machine problem. When jobs have general release dates, we propose a 4/3-approximation algorithm for the single machine problem and a (1 + max{0.618, 1 - 1/m})-approximation algorithm for the parallel machine problem, respectively.

关键词： Scheduling Rejection Release date approximation algorithm Worst-case ratio

来源：评论

学校读者我要写书评

暂无评论

A Local Search algorithm for the Radius-Constrained k-Median Problem

引用

THEORY OF COMPUTING SYSTEMS 2025年第1期69卷 1-18页

作者： Chi, Gaojie Guo, Longkun Jia, Chaoqi Guangdong Univ Technol Sch Integrated Circuits Guangzhou Peoples R China Fuzhou Univ Sch Math & Stat Fuzhou 350116 Peoples R China RMIT Univ Sch Accounting Informat Syst & Supply Chain Melbourne Vic 3000 Australia

Given a radius R is an element of Z+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R\in \mathbb {Z}<^>+$$\end{document} and a set X of n points distributed within a metric space, we consider the radius-constrained k-median problem, which combines both the k-center and k-median clustering problems. In this problem, the objective is the same as that of the k-median problem, with the additional constraint that every point x in X must be assigned to a center within the given radius R. This paper proposes an approximation algorithm that achieves a bicriteria approximation ratio of (3+epsilon,7)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(3+\varepsilon , 7)$$\end{document} by incorporating local search with a key ball structure. The algorithm constructs a keyball center set to ensure coverage of the points and iteratively refines the solution through subset swaps while satisfying feasibility conditions. Thus, this process maintains coverage while reducing costs. Compared to the state-of-the-art approximation ratio of (8, 4) based on a linear programming formulation for this problem, our approach improves the k-median ratio from 8 to 3+epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$3+\varepsilon $$\end{document}, at the cost of increasing the radius ratio from 4 to 7.

关键词： Local search k-median k-center approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimizing total completion time and makespan for a multi-scenario bi-criteria parallel machine scheduling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2025年第2期321卷 397-406页

作者： Zhang, Xiechen Angel, Eric Chu, Feng Regnault, Damien Univ Paris Saclay Univ Evry IBISC Lab 23 Blvd F-91037 Essonne France

Multi-criteria scheduling problems under uncertainty remain a relatively unexplored topic in theoretical computer science despite substantial practical interests. This work studies a bi-objective identical parallel machine scheduling problem under uncertainty, in which the first objective is to minimize the total completion time, and the second is to minimize the makespan. Especially a job's processing time is assumed to be represented by a polynomial function with respect to scenario u is an element of U, where U subset of R+ is an interval containing an infinite number of scenarios. In this work, we are looking for a compact and complete description of the set of possibly optimal solutions, along with their objective function values, over the set of scenarios or an approximation with a performance guarantee. First, to better understand the characteristics of the studied problem, we consider two single-objective problems: parallel machine scheduling problem under uncertainty with the total completion time and makespan criterion, respectively. For the problem with the total completion time criterion, we demonstrate that the set of possibly optimal schedules can be found in polynomial time. In contrast, for the problem with the makespan criterion, we provide a (1+epsilon)-approximation algorithm. For the bi-objective problem, we provide a 2-approximation algorithm for any number of parallel machines and a (1+epsilon)-approximation algorithm where a fixed number of parallel machines is considered.

关键词： Scheduling Identical parallel machines Multi-criteria Uncertainty approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the Maximum Weight Internal Spanning Tree Problem

引用

algorithmICA 2019年第11-12期81卷 4167-4199页

作者： Chen, Zhi-Zhong Lin, Guohui Wang, Lusheng Chen, Yong Wang, Dan Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada City Univ Hong Kong Dept Comp Sci 83 Tat Chee Ave Kowloon Hong Kong Peoples R China City Univ Hong Kong Shenzhen Res Inst Shenzhen Hitech Ind Pk Shenzhen Peoples R China Hangzhou Dianzi Univ Inst Operat Res & Cybernet Hangzhou 310018 Zhejiang Peoples R China

Given a vertex-weighted connected graph G=(V,E), the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree T of G such that the total weight of internal vertices in T is maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio of 13 / 17. The currently best approximation algorithm for MwIST only has a performance ratio of 1/3-E, for any E>0. In this paper, we present a simple algorithm based on a novel relationship between MwIST and maximum weight matching, and show that it achieves a significantly better approximation ratio of 1/2. When restricted to claw-free graphs, a special case previously studied, we design a 7/12-approximation algorithm.

关键词： Maximum weight internal spanning tree Maximum weight matching approximation algorithm Performance analysis

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for minimum weight connected 3-path vertex cover

引用

APPLIED MATHEMATICS AND COMPUTATION 2019年 347卷 723-733页

作者： Ran, Yingli Zhang, Zhao Huang, Xiaohui Li, Xiaosong Du, Ding-Zhu Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Xinjiang Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

A k-path vertex cover (VCPk) is a vertex set C of graph G such that every path of G on k vertices has at least one vertex in C. Because of its background in keeping data integrality of a network, minimum VCPk problem (MinVCP(k)) has attracted a lot of researches in recent years. This paper studies the minimum weight connected VCPk problem (MinWCVCP(k)), in which every vertex has a weight and the VCPk found by the algorithm induces a connected subgraph and has the minimum weight. It is known that MinWCVCP(k) is set-cover-hard. We present two polynomial-time approximation algorithms for MinWCVCP(3). The first one is a greedy algorithm achieving approximation ratio 31n n. The difficulty lies in its analysis dealing with a non-submodular potential function. The second algorithm is a 2-stage one, finding a VCP3 in the first stage and then adding more vertices for connection. We show that its approximation ratio is at most ln delta(max) + 4 + ln 2, where delta(max) is the maximum degree of the graph. Considering the inapproximability of this problem, this ratio is asymptotically tight. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Connected k-path vertex cover Weight approximation algorithm Non-submodular potential function

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：