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

FPT approximation and subexponential algorithms for covering few or many edges

学校读者我要写书评

暂无评论

INFORMATION PROCESSING LETTERS 2024年 185卷

作者： Fomin, Fedor V. Golovach, Petr A. Inamdar, Tanmay Koana, Tomohiro Univ Bergen Dept Informat N-5004 Bergen Norway Indian Inst Technol Jodhpur 342030 India Tech Univ Berlin Algorithm & Computat Complex Berlin Germany

We study the alpha-Fixed Cardinality Graph Partitioning (alpha-FCGP) problem, the generic local graph partitioning problem introduced by Bonnet et al. [Algorithmica 2015]. In this problem, we are given a graph G, two numbers k,p and 0 <= alpha <= 1, the question is whether there is a set S subset of V of size k with a specified coverage function cov(alpha)(S) at least p (or at most p for the minimization version). The coverage function cov(alpha)(center dot) counts edges with exactly one endpoint in S with weight alpha and edges with both endpoints in S with weight 1-alpha. alpha-FCGP generalizes a number of fundamental graph problems such as Densest k-Subgraph, Max k-Vertex Cover, and Max (k, n-k)-CUT. A natural question in the study of alpha-FCGP is whether the algorithmic results known for its special cases, like Max k-VERTEX COVER, could be extended to more general settings. One of the simple but powerful methods for obtaining parameterized approximation [Manurangsi, SOSA 2019] and subexponential algorithms [Fomin et al. IPL 2011] for Max k-Vertex Cover is based on the greedy vertex degree orderings. The main insight of our work is that the idea of greedy vertex degree ordering could be used to design fixed-parameter approximation schemes (FPT-AS) for alpha>0 and subexponential-time algorithms for the problem on apex-minor free graphs for maximization with alpha > 1/3 and minimization with alpha < 1/3.(4)

关键词： Parameterized complexity approximation algorithms Partial vertex cover

approximation algorithms for the Team Orienteering Problem

学校读者我要写书评

暂无评论

Approximation Algorithms for the Team Orienteering Problem

IEEE Annual Joint Conference: INFOCOM, IEEE Computer and Communications Societies

作者： Wenzheng Xu Zichuan Xu Jian Peng Weifa Liang Tang Liu Xiaohua Jia Sajal K. Das College of Computer Science Sichuan University Chengdu P. R. China School of Software Dalian University of Technology Dalian P. R. China Research School of Computer Science The Australian National University Canberra ACT Australia College of Computer Science Sichuan Normal University Chengdu P. R. China Department of Computer Science City University of Hong Kong Hong Kong P. R. China Department of Computer Science Missouri University of Science and Technology Rolla MO USA

ISBN: (数字)9781728164120

ISBN: (纸本)9781728164137

In this paper we study a team orienteering problem, which is to find service paths for multiple vehicles in a network such that the profit sum of serving the nodes in the paths is maximized, subject to the cost budget of each vehicle. This problem has many potential applications in IoT and smart cities, such as dispatching energy-constrained mobile chargers to charge as many energy-critical sensors as possible to prolong the network lifetime. In this paper, we first formulate the team orienteering problem, where different vehicles are different types, each node can be served by multiple vehicles, and the profit of serving the node is a submodular function of the number of vehicles serving it. We then propose a novel (1 - (1/e) 1/2+ε )approximation algorithm for the problem, where c is a given constant with 0 ≤ ε ≤ 1 and ε is the base of the natural logarithm. In particular, the approximation ratio is no less than 0.32 when ε = 0.5. In addition, for a special team orienteering problem with the same type of vehicles and the profits of serving a node once and multiple times being the same, we devise an improved approximation algorithm. Finally, we evaluate the proposed algorithms with simulation experiments, and the results of which are very promising. Precisely, the profit sums delivered by the proposed algorithms are approximately 12.5% to 17.5% higher than those by existing algorithms.

关键词： approximation algorithms Capacitive sensors Smart cities Dispatching Monitoring

approximation algorithms for connectivity augmentation problems

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Nutov, Zeev Open University of Israel Israel

In Connectivity Augmentation problems we are given a graph H = (V, EH) and an edge set E on V , and seek a min-size edge set J ⊆ E such that H ∪J has larger edge/node connectivity than H. In the Edge-Connectivity Augmentation problem we need to increase the edge-connectivity by 1. In the Block-Tree Augmentation problem H is connected and H ∪ S should be 2-connected. In Leaf-to-Leaf Connectivity Augmentation problems every edge in E connects minimal deficient sets. For this version we give a simple combinatorial approximation algorithm with ratio 5/3, improving the 1.91 approximation of [3] (see also [16]), that applies for the general case. We also show by a simple proof that if the Steiner Tree problem admits approximation ratio α then the general version admits approximation ratio 1 + ln(4 − x) + Ε, where x is the solution to the equation 1 + ln(4 − x) = α + (α − 1)x. For the currently best value of α = ln 4 + Ε [4] this gives ratio 1.942. This is slightly worse than the ratio 1.91 of [3], but has the advantage of using Steiner Tree approximation as a "black box", giving ratio Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

approximation algorithms for car-sharing problems

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Luo, Kelin Spieksma, Frits C.R. Department of Mathematics and Computer Science Eindhoven University of Technology Eindhoven Netherlands

We consider several variants of a car-sharing problem. Given are a number of requests each consisting of a pick-up location and a drop-off location, a number of cars, and nonnegative, symmetric travel times that satisfy the triangle inequality. Each request needs to be served by a car, which means that a car must first visit the pick-up location of the request, and then visit the drop-off location of the request. Each car can serve two requests. One problem is to serve all requests with the minimum total travel time (called CSsum), and the other problem is to serve all requests with the minimum total latency (called CSlat). We also study the special case where the pick-up and drop-off location of a request coincide. We propose two basic algorithms, called the match and assign algorithm and the transportation algorithm. We show that the best of the resulting two solutions is a 2-approximation for CSsum (and a 7/5-approximation for its special case), and a 5/3-approximation for CSlat (and a 3/2-approximation for its special case);these ratios are better than the ratios of the individual algorithms. Finally, we indicate how our algorithms can be applied to more general settings where each car can serve more than two requests, or where cars have distinct speeds. Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

approximation algorithms and LP relaxations for scheduling problems related to min-sum set cover

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Happach, Felix Schulz, Andreas S. Department of Mathematics and School of Management Technische Universität München Germany

We consider single-machine scheduling problems that are natural generalizations or variations of the min-sum set cover problem and the min-sum vertex cover problem. For each of these problems, we give new approximation algorithms. Some of these algorithms rely on time-indexed LP relaxations. We show how a variant of alpha-point scheduling leads to the best-known approximation ratios, including a guarantee of 4 for an interesting special case of the so-called generalized min-sum set cover problem. We also make explicit the connection between the greedy algorithm for min-sum set cover and the concept of Sidney decomposition for precedence constrained single-machine scheduling, and show how this leads to a 4-approximation algorithm for single-machine scheduling with so-called bipartite OR-precedence constraints.90B35, 90C05, 68W25 Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

approximation algorithms for the MAXSPACE advertisement problem

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Da Silva, Mauro R.C. Pedrosa, Lehilton L.C. Schouery, Rafael C.S. Institute of Computing University of Campinas Brazil

In MAXSPACE, given a set of ads A, one wants to schedule a subset A′ ⊆ A into K slots B1, ⋯ , BKof size L. Each ad Ai∈ A has a size siand a frequency wi. A schedule is feasible if the total size of ads in any slot is at most L, and each ad Ai∈ A′ appears in exactly wislots and at most once per slot. The goal is to find a feasible schedule that maximizes the sum of the space occupied by all slots. We consider a generalization called MAXSPACE-R for which an ad Aialso has a release date ri and may only appear in a slot Bjif j ≥ ri. For this variant, we give a 1/9-approximation algorithm. Furthermore, we consider MAXSPACE-RDV for which an ad Ai also has a deadline di(and may only appear in a slot Bjwith ri≤ j ≤ di), and a value vithat is the gain of each assigned copy of Ai(which can be unrelated to si). We present a polynomial-time approximation scheme for this problem when K is bounded by a constant. This is the best factor one can expect since MAXSPACE is strongly NP-hard, even if K = 2. Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

From Theory to Practice: Engineering approximation algorithms for Dynamic Orientation

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Großmann, Ernestine van der Hoog, Ivor Reinstädtler, Henrik Rotenberg, Eva Schulz, Christian Vlieghe, Juliette Heidelberg University Germany Technical University of Denmark Denmark

Dynamic graph algorithms have seen significant theoretical advancements, but practical evaluations often lag behind. This work bridges the gap between theory and practice by engineering and empirically evaluating recently developed approximation algorithms for dynamically maintaining graph orientations. We comprehensively describe the underlying data structures, including efficient bucketing techniques and round-robin updates. Our implementation has a natural parameter λ, which allows for a trade-off between algorithmic efficiency and the quality of the solution. In the extensive experimental evaluation, we demonstrate that our implementation offers a considerable speedup. Using different quality metrics, we show that our implementations are very competitive and can outperform previous methods. Overall, our approach solves more instances than other methods while being up to 112 times faster on instances that are solvable by all methods compared. Copyright © 2025, The Authors. All rights reserved.

关键词： approximation algorithms

Exact and approximation algorithms for many-to-many point matching in the plane

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bandyapadhyay, Sayan Maheshwari, Anil Smid, Michiel Department of Informatics University of Bergen Norway School of Computer Science Carleton University

Given two sets S and T of points in the plane, of total size n, a many-to-many matching between S and T is a set of pairs (p, q) such that p ∈ S, q ∈ T and for each r ∈ S ∪ T, r appears in at least one such pair. The cost of a pair (p, q) is the (Euclidean) distance between p and q. In the minimum-cost many-to-many matching problem, the goal is to compute a many-to-many matching such that the sum of the costs of the pairs is minimized. This problem is a restricted version of minimum-weight edge cover in a bipartite graph, and hence can be solved in O(n3) time. In a more restricted setting where all the points are on a line, the problem can be solved in O(n log n) time [Colannino, Damian, Hurtado, Langerman, Meijer, Ramaswami, Souvaine, Toussaint;Graphs Comb., 2007]. However, no progress has been made in the general planar case in improving the cubic time bound. In this paper, we obtain an O(n2 · poly(log n)) time exact algorithm and an O(n3/2 · poly(log n)) time (1 + ϵ)-approximation in the planar case. Our results affirmatively address an open problem posed in [Colannino et al., Graphs Comb., 2007]. © 2021, CC BY.

关键词： approximation algorithms

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