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

Complexity and approximation algorithms for Fixed Charge Transportation Problems

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Chen, Yong Li, Shi Liang, Zihao Department of Mathematics Hangzhou Dianzi University Zhejiang Province Hangzhou China School of Computer Science Nanjing University Jiangsu Province Nanjing China

The Fixed Charge Transportation (FCT) problem models transportation scenarios where we need to send a commodity from n sources to m sinks, and the cost of sending a commodity from a source to a sink consists of a linear component and a fixed component. Despite extensive research on exponential time exact algorithms and heuristic algorithms for FCT and its variants, their approximability and computational complexity are not well understood. In this work, we initiate a systematic study of the approximability and complexity of these problems. When there are no linear costs, we call the problem the Pure Fixed Charge Transportation (PFCT) problem. We also distinguish between cases with general, sink-independent, and uniform fixed costs;we use the suffixes "-S" and "-U" to denote the latter two cases, respectively. This gives us six variants of the FCT problem. We give a complete characterization of the existence of O(1)-approximation algorithms for these variants. In particular, we give 2-approximation algorithms for FCT-U and PFCT-S, and a (6/5 + ϵ)-approximation for PFCT-U. On the negative side, we prove that FCT and PFCT are NP-hard to approximate within a factor of O(log2−ϵ(max{n, m})) for any constant ϵ > 0, FCT-S is NP-hard to approximate within a factor of c log(max{n, m}) for some constant c > 0, and PFCT-U is APX-hard. Additionally, we design an Efficient Parameterized approximation Scheme (EPAS) for PFCT when parameterized by the number n of sources, and an O(1/ϵ)-bicriteria approximation for the FCT problem, when we are allowed to violate the demand constraints for sinks by a factor of 1 ± ϵ. Copyright © 2025, The Authors. All rights reserved.

关键词： approximation algorithms

Improved approximation algorithms for multiprocessor indivisible coflow scheduling

学校读者我要写书评

暂无评论

Journal of Combinatorial Optimization 2025年第5期49卷

作者： Gong, Mingyang Chen, Guangting Lin, Guohui Su, Bing Department of Computing Science University of Alberta EdmontonABT6G 2E8 Canada Zhejiang University of Water Resources and Electric Power Hangzhou310018 China School of Economics and Management Xi’an Technological University Xi’an710021 China

Coflow scheduling is a challenging optimization problem that underlies many data transmission and parallel computing applications. In this paper, we study the indivisible coflow scheduling problem on parallel identical machines with the objective to minimize the makespan, i.e., the completion time of the last flow. In our problem setting, the number of the input/output ports in each machine is a fixed constant, each port has a unit capacity, and all the flows inside a coflow should be scheduled on the same machine. We present a (2+ϵ)-approximation algorithm for the problem, for any ϵ>0, in which the number of machines can be either a fixed constant or part of the input. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2025.

关键词： approximation algorithms

Comparison of approximation algorithms for the travelling salesperson problem on semimetric graphs

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Krukowski, Mateusz Turobos, Filip Institute of Mathematics Lódz University of Technology Wólczanska 215 Lódz90-924 Poland

The aim of the paper is to compare different approximation algorithms for the travelling salesperson problem. We pick the most popular and widespread methods known in the literature and contrast them with a novel approach (the polygonal Christofides algorithm) described in our previous work. The paper contains a brief summary of theory behind the algorithms and culminates in a series of numerical simulations (or "experiments"), whose purpose is to determine "the best" approximation algorithm for the travelling salesperson problem on complete, weighted graphs. Copyright © 2021, The Authors. All rights reserved.

关键词： approximation algorithms

VERIFIED approximation algorithms

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Essmann, Robin Nipkow, Tobias Robillard, Simon Sulejmani, Ujkan Technische Universität München Germany LIRMM Université de Montpellier CNRS Montpellier France

We present the first formal verification of approximation algorithms for NP-complete optimization problems: vertex cover, independent set, set cover, center selection, load balancing, and bin packing. We uncover incompletenesses in existing proofs and improve the approximation ratio in one case. All proofs are uniformly invariant based. © 2021, CC BY.

关键词： approximation algorithms

Automating the Search for Small Hard Examples to approximation algorithms

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Sharma, Eklavya University of Illinois Urbana-Champaign United States

Given an approximation algorithm A, we want to find the input with the worst approximation ratio, i.e., the input for which A’s output’s objective value is the worst possible compared to the optimal solution’s objective value. Such hard examples shed light on the approximation algorithm’s weaknesses, and could help us design better approximation algorithms. When the inputs are discrete (e.g., unweighted graphs), one can find hard examples for small input sizes using brute-force enumeration. However, it’s not obvious how to do this when the input space is continuous, as in makespan minimization or bin packing. We develop a technique for finding small hard examples for a large class of approximation algorithms. Our algorithm works by constructing a decision tree representation of the approximation algorithm and then running a linear program for each leaf node of the decision tree. We implement our technique in Python, and demonstrate it on the longest-processing-time (LPT) heuristic for makespan minimization. Copyright © 2025, The Authors. All rights reserved.

关键词： approximation algorithms

New approximation algorithms for forest closeness centrality - For individual vertices and vertex groups

学校读者我要写书评

暂无评论

arXiv 2021年

作者： van der Grinten, Alexander Angriman, Eugenio Predari, Maria Meyerhenke, Henning Dept. of Computer Science Humboldt-Universität zu Berlin Unter den Linden 6 BerlinD-10099 Germany

The emergence of massive graph data sets requires fast mining algorithms. Centrality measures to identify important vertices belong to the most popular analysis methods in graph mining. A measure that is gaining attention is forest closeness centrality;it is closely related to electrical measures using current flow but can also handle disconnected graphs. Recently, [Jin et al., ICDM’19] proposed an algorithm to approximate this measure probabilistically. Their algorithm processes small inputs quickly, but does not scale well beyond hundreds of thousands of vertices. In this paper, we first propose a different approximation algorithm;it is up to two orders of magnitude faster and more accurate in practice. Our method exploits the strong connection between uniform spanning trees and forest distances by adapting and extending recent approximation algorithms for related single-vertex problems. This results in a nearly-linear time algorithm with an absolute probabilistic error guarantee. In addition, we are the first to consider the problem of finding an optimal group of vertices w. r. t. forest closeness. We prove that this latter problem is NP-hard;to approximate it, we adapt a greedy algorithm by [Li et al., WWW’19], which is based on (partial) matrix inversion. Moreover, our experiments show that on disconnected graphs, group forest closeness outperforms existing centrality measures in the context of semi-supervised vertex classification. © 2021, CC BY.

关键词： approximation algorithms

Complexity analysis and approximation algorithms for the single-machine scheduling problem with workload-dependent maintenance activities

学校读者我要写书评

暂无评论

JOURNAL OF SCHEDULING 2025年

作者： Liu, Peihai Gu, Manzhan Lu, Xiwen East China Univ Sci & Technol Sch Math Shanghai 200237 Peoples R China Shanghai Univ Finance & Econ Sch Math Shanghai 200433 Peoples R China

This paper considers the single-machine scheduling problem with workload-dependent maintenance activities of variable length. The time needed to perform a maintenance activity is a function of the total processing time of the jobs that are processed between the starting time of this activity and the end of the last previous activity. In the case where the function is concave, we study the computational complexity of the three problems with the goal of minimizing the makespan, the total completion time, and the total weighted completion time, respectively. In addition, we propose a 2-approximation algorithm for the first problem and a 2.5-approximation algorithm for the second problem.

关键词： Single-machine scheduling Computational complexity Maintenance activities approximation algorithms

α-approximate reductions: A novel source of heuristics for better approximation algorithms

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Manne, Fredrik Philip, Geevarghese Saurabh, Saket Tale, Prafullkumar University of Bergen Bergen Norway Chennai Mathematical Institute India The Institute of Mathematical Sciences HBNI Chennai India CISPA Helmholtz Center for Information Security Saarbrücken Germany

Lokshtanov et al. [STOC 2017] introduced lossy kernelization as a mathematical framework for quantifying the effectiveness of preprocessing algorithms in preserving approximation ratios. αapproximate reduction rules are a central notion of this framework. We propose that carefully crafted α-approximate reduction rules can yield improved approximation ratios in practice, while being easy to implement as well. This is distinctly different from the (theoretical) purpose for which Lokshtanov et al. designed α-approximate Reduction Rules. As evidence in support of this proposal we present a new 2-approximate reduction rule for the Dominating Set problem. This rule, when combined with an approximation algorithm for Dominating Set, yields significantly better approximation ratios on a variety of benchmark instances as compared to the latter algorithm alone. The central thesis of this work is that α-approximate reduction rules can be used as a tool for designing approximation algorithms which perform better in practice. To the best of our knowledge, ours is the first exploration of the use of α-approximate reduction rules as a design technique for practical approximation algorithms. We believe that this technique could be useful in coming up with improved approximation algorithms for other optimization problems as well. © 2021, CC BY.

关键词： approximation algorithms

Application of the level-2 quantum lasserre hierarchy in quantum approximation algorithms

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Parekh, Ojas Thompson, Kevin Sandia National Laboratories AlbuquerqueNM United States

The Lasserre Hierarchy, [19, 20], is a set of semidefinite programs which yield increasingly tight bounds on optimal solutions to many NP-hard optimization problems. The hierarchy is parameterized by levels, with a higher level corresponding to a more accurate relaxation. High level programs have proven to be invaluable components of approximation algorithms for many NP-hard optimization problems [4, 8, 27]. There is a natural analogous quantum hierarchy [6, 9, 25], which is also parameterized by level and provides a relaxation of many (QMA-hard) quantum problems of interest [6, 7, 10]. In contrast to the classical case, however, there is only one approximation algorithm which makes use of higher levels of the hierarchy [6]. Here we provide the first ever use of the level-2 hierarchy in an approximation algorithm for a particular QMA-complete problem, so-called Quantum Max Cut [3, 10]. We obtain modest improvements on state-of-the-art approximation factors for this problem, as well as demonstrate that the level-2 hierarchy satisfies many physically-motivated constraints that the level-1 does not satisfy. Indeed, this observation is at the heart of our analysis and indicates that higher levels of the quantum Lasserre Hierarchy may be very useful tools in the design of approximation algorithms for QMA-complete problems. Copyright © 2021, The Authors. All rights reserved.

关键词： approximation algorithms