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

Improved approximation algorithms for some capacitated k edge connectivity problems

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Nutov, Zeev The Open University of Israel

We consider the following two variants of the Capacitated k-Edge Connected Subgraph (Cap-k-ECS) problem. Near Min-Cuts Cover: Given a graph G = (V, E) with edge costs and E0 ⊆ E, find a min-cost edge set J ⊆ E \ E0 that covers all cuts with at most k − 1 edges of the graph G0 = (V, E0). We obtain approximation ratio k − λ0 + 1 + ϵ, improving the ratio 2 min{k − λ0, 8} of [2] for k − λ0 ≤ 14, where λ0 is the edge connectivity of G0. (k, q)-Flexible Graph Connectivity ((k, q)-FGC): Given a graph G = (V, E) with edge costs and a set U ⊆ E of"unsafe" edges and integers k, q, find a min-cost subgraph H of G such that every cut of H has at least k safe edges or at least k + q edges. We show that (k, 1)-FGC admits approximation ratio 3.5 + ϵ if k is odd (improving the ratio 4 of [3]), and that (k, 2)-FGC admits approximation ratio 6 if k is even and 7 + ϵ if k is odd (improving the ratio 20 of [2]). © 2023, CC BY.

关键词： approximation algorithms

Robust approximation algorithms for Non-monotone k-Submodular Maximization under a Knapsack Constraint

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Ha, Dung T.K. Pham, Canh V. Tran, Tan D. Hoang, Huan X. ORLab Phenikaa University Hanoi Viet Nam Faculty of Information Technology Halong University Quang Ninh Viet Nam VNU University of Engineering and Technology Hanoi Viet Nam

The problem of non-monotone k-submodular maximization under a knapsack constraint (kSMK) over the ground set size n has been raised in many applications in machine learning, such as data summarization, information propagation, etc. However, existing algorithms for the problem are facing questioning of how to overcome the non-monotone case and how to fast return a good solution in case of the big size of data. This paper introduces two deterministic approximation algorithms for the problem that competitively improve the query complexity of existing algorithms. Our first algorithm, LAA, returns an approximation ratio of 1/19 within O(nk) query complexity. The second one, RLA, improves the approximation ratio to 1/5−ϵ in O(nk) queries, where ϵ is an input parameter. Our algorithms are the first ones that provide constant approximation ratios within only O(nk) query complexity for the non-monotone objective. They, therefore, need fewer the number of queries than state-of-the-the-art ones by a factor of Ω(log n). Besides the theoretical analysis, we have evaluated our proposed ones with several experiments in some instances: Influence Maximization and Sensor Placement for the problem. The results confirm that our algorithms ensure theoretical quality as the cutting-edge techniques and significantly reduce the number of queries. © 2023, CC BY.

关键词： approximation algorithms

Efficient approximation algorithms for Scheduling Coflows with Total Weighted Completion Time in Identical Parallel Networks

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Chen, Chi-Yeh Department of Computer Science and Information Engineering National Cheng Kung University Taiwan

This paper addresses the scheduling problem of coflows in identical parallel networks, which is a well-known NP-hard problem. Coflow is a relatively new network abstraction used to characterize communication patterns in data centers. We consider both flow-level scheduling and coflow-level scheduling problems. In the flow-level scheduling problem, flows within a coflow can be transmitted through different network cores. However, in the coflow-level scheduling problem, flows within a coflow must be transmitted through the same network core. The key difference between these two problems lies in their scheduling granularity. Previous approaches relied on linear programming to solve the scheduling order. In this paper, we enhance the efficiency of solving by utilizing the primal-dual method. For the flow-level scheduling problem, we propose a (6 − m2 )-approximation algorithm with arbitrary release times and a (5 − m2 )-approximation algorithm without release time, where m represents the number of network cores. Additionally, for the coflow-level scheduling problem, we introduce a (4m + 1)-approximation algorithm with arbitrary release times and a (4m)-approximation algorithm without release time. To validate the effectiveness of our proposed algorithms, we conduct simulations using both synthetic and real traffic traces. The results demonstrate the superior performance of our algorithms compared to previous approach, emphasizing their practical utility. Copyright © 2023, The Authors. All rights reserved.

关键词： approximation algorithms

Faster exact and approximation algorithms for packing and covering matroids via push-relabel

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Quanrud, Kent Purdue University United States

Matroids are a fundamental object of study in combinatorial optimization. Three closely related and important problems involving matroids are maximizing the size of the union of k independent sets (that is, k-fold matroid union), computing k disjoint bases (a.k.a. matroid base packing), and covering the elements by k bases (a.k.a. matroid base covering). These problems generalize naturally to integral and real-valued capacities on the elements. This work develops faster exact and/or approximation problems for these and some other closely related problems such as optimal reinforcement and matroid membership. We obtain improved running times both for general matroids in the independence oracle model and for the graphic matroid. The main thrust of our improvements comes from developing a faster and unifying push-relabel algorithm for the integer-capacitated versions of these problems, building on previous work by Frank and Miklós [FM12]. We then build on this algorithm in two directions. First we develop a faster augmenting path subroutine for k-fold matroid union that, when appended to an approximation version of the push-relabel algorithm, gives a faster exact algorithm for some parameters of k. In particular we obtain a subquadratic-query running time in the uncapacitated setting for the three basic problems listed above. We also obtain faster approximation algorithms for these problems with real-valued capacities by reducing to small integral capacities via randomized rounding. To this end, we develop a new randomized rounding technique for base covering problems in matroids that may also be of independent interest. Copyright © 2023, The Authors. All rights reserved.

关键词： approximation algorithms

Simpler constant factor approximation algorithms for weighted flow time - now for any p-norm

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Armbruster, Alexander Rohwedder, Lars Wiese, Andreas TU of Munich Germany Maastricht University Netherlands

A prominent problem in scheduling theory is the weighted flow time problem on one machine. We are given a machine and a set of jobs, each of them characterized by a processing time, a release time, and a weight. The goal is to find a (possibly preemptive) schedule for the jobs in order to minimize the sum of the weighted flow times, where the flow time of a job is the time between its release time and its completion time. It had been a longstanding important open question to find a polynomial time O(1)-approximation algorithm for the problem. In a break-through result, Batra, Garg, and Kumar (FOCS 2018) presented such an algorithm with pseudopolynomial running time. Its running time was improved to polynomial time by Feige, Kulkarni, and Li (SODA 2019). The approximation ratios of these algorithms are relatively large, but they were improved to 2 + ǫ by Rohwedder and Wiese (STOC 2022) and subsequently to 1 + ǫ by Armbruster, Rohwedder, and Wiese (STOC 2023). All these algorithms are quite complicated and involve for example a reduction to (geometric) covering problems, dynamic programs to solve those, and LP-rounding methods to reduce the running time to a polynomial in the input size. In this paper, we present a much simpler (6 + ǫ)approximation algorithm for the problem that does not use any of these reductions, but which works on the input jobs directly. It even generalizes directly to an O(1)-approximation algorithm for minimizing the p-norm of the jobs’ flow times, for any 0 1 only a pseudopolynomial time O(1)-approximation algorithm was known for this variant, and no algorithm for p © 2023, CC0.

关键词： approximation algorithms

Bicriteria approximation algorithms for the Submodular Cover Problem

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Chen, Wenjing Crawford, Victoria G. Department of Computer Science & Engineering Texas A&M University United States

In this paper, we consider the optimization problem Submodular Cover (SCP), which is to find a minimum cardinality subset of a finite universe U such that the value of a submodular function f is above an input threshold τ. In particular, we consider several variants of SCP including the general case, the case where f is additionally assumed to be monotone, and finally the case where f is a regularized monotone submodular function. Our most significant contributions are that: (i) We propose a scalable algorithm for monotone SCP that achieves nearly the same approximation guarantees as the standard greedy algorithm in significantly faster time;(ii) We are the first to develop an algorithm for general SCP that achieves a solution arbitrarily close to being feasible;and finally (iii) we are the first to develop algorithms for regularized SCP. Our algorithms are then demonstrated to be effective in an extensive experimental section on data summarization and graph cut, two applications of SCP. © 2023, CC BY.

关键词： approximation algorithms

Parameterized and approximation algorithms for the Maximum Bimodal Subgraph Problem

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Didimo, Walter Fomin, Fedor V. Golovach, Petr A. Inamdar, Tanmay Kobourov, Stephen Sieper, Marie Diana Dept. of Engineering University of Perugia Italy Department of Computer Science University of Bergen Norway Department of Computer Science University of Arizona United States Department of Computer Science University of Würzburg Germany

A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart of many types of graph layouts, such as upward drawings, level-planar drawings, and L-drawings. If the graph is not bimodal, the Maximum Bimodal Subgraph (MBS) problem asks for an embedding-preserving bimodal subgraph with the maximum number of edges. We initiate the study of the MBS problem from the parameterized complexity perspective with two main results: (i) we describe an FPT algorithm parameterized by the branchwidth (and hence by the treewidth) of the graph;(ii) we establish that MBS parameterized by the number of non-bimodal vertices admits a polynomial kernel. As the byproduct of these results, we obtain a subexponential FPT algorithm and an efficient polynomial-time approximation scheme for MBS. © 2023, CC BY.

关键词： approximation algorithms

New approximation algorithms for Touring Regions

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Qi, Benjamin Qi, Richard Chen, Xinyang Massachusetts Institute of Technology CambridgeMA United States

We analyze the touring regions problem: find a (1 + ∊)-approximate Euclidean shortest path in d-dimensional space that starts at a given starting point, ends at a given ending point, and visits given regions R1, R2, R3,..., Rn in that order. Our main result is an (Equation presented) -time algorithm for touring disjoint disks. We also give an (Equation presented) -time algorithm for touring disjoint two-dimensional convex fat bodies. Both of these results naturally generalize to larger dimensions;we obtain (Equation presented) and (Equation presented)-time algorithms for touring disjoint d-dimensional balls and convex fat bodies, respectively. Copyright © 2023, The Authors. All rights reserved.

关键词： approximation algorithms

Efficient approximation algorithms for Scheduling Coflows with Precedence Constraints in Identical Parallel Networks to Minimize Weighted Completion Time

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Chen, Chi-Yeh Department of Computer Science and Information Engineering National Cheng Kung University Taiwan

This paper focuses on the problem of coflow scheduling with precedence constraints in identical parallel networks, which is a well-known NP-hard problem. Coflow is a relatively new network abstraction used to characterize communication patterns in data centers. Both flow-level scheduling and coflow-level scheduling problems are examined, with the key distinction being the scheduling granularity. The proposed algorithm effectively determines the scheduling order of coflows by employing the primal-dual method. When considering workload sizes and weights that are dependent on the network topology in the input instances, our proposed algorithm for the flow-level scheduling problem achieves an approximation ratio of O(χ) where χ is the coflow number of the longest path in the directed acyclic graph (DAG). Additionally, when taking into account workload sizes that are topology-dependent, the algorithm achieves an approximation ratio of O(Rχ), where R represents the ratio of maximum weight to minimum weight. For the coflow-level scheduling problem, the proposed algorithm achieves an approximation ratio of O(mχ), where m is the number of network cores, when considering workload sizes and weights that are topology-dependent. Moreover, when considering workload sizes that are topology-dependent, the algorithm achieves an approximation ratio of O(Rmχ). In the coflows of multi-stage job scheduling problem, the proposed algorithm achieves an approximation ratio of O(χ). Although our theoretical results are based on a limited set of input instances, experimental findings show that the results for general input instances outperform the theoretical results, thereby demonstrating the effectiveness and practicality of the proposed algorithm. Copyright © 2023, The Authors. All rights reserved.

关键词： approximation algorithms