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

approximation algorithms FOR SIZE-CONSTRAINED NON-MONOTONE SUBMODULAR MAXIMIZATION IN DETERMINISTIC LINEAR TIME

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Chen, Yixin Kuhnle, Alan Department of Computer Science & Engineering Texas A&M University College StationTX United States

In this work, we study the problem of finding the maximum value of a non-negative submodular function subject to a limit on the number of items selected, a ubiquitous problem that appears in many applications, such as data summarization and nonlinear regression. We provide the first deterministic, linear-time approximation algorithms for this problem that do not assume the objective is monotone. We present three deterministic, linear-time algorithms: a single-pass streaming algorithm with a ratio of 23.313 + ϵ, which is the first linear-time streaming algorithm;a simpler deterministic linear-time algorithm with a ratio of 11.657;and a (4 + O(ϵ))-approximation algorithm. Finally, we present a deterministic algorithm that obtains ratio of e + ϵ in Oϵ(n log(n)) time, close to the best known expected ratio of e − 0.121 in polynomial time. Copyright © 2021, The Authors. All rights reserved.

关键词： approximation algorithms

FPT and FPT-approximation algorithms for unsplittable flow on trees 29

学校读者我要写书评

暂无评论

FPT and FPT-approximation algorithms for unsplittable flow o...

29th Annual European Symposium on algorithms, ESA 2021

作者： Martínez-Muñoz, Tomás Wiese, Andreas Mathematical Engineering Department University of Chile Santiago Chile Department of Industrial Engineering University of Chile Santiago Chile

ISBN: (纸本)9783959772044

We study the unsplittable flow on trees (UFT) problem in which we are given a tree with capacities on its edges and a set of tasks, where each task is described by a path and a demand. Our goal is to select a subset of the given tasks of maximum size such that the demands of the selected tasks respect the edge capacities. The problem models throughput maximization in tree networks. The best known approximation ratio for (unweighted) UFT is O(log n). We study the problem under the angle of FPT and FPT-approximation algorithms. We prove that UFT is FPT if the parameters are the cardinality k of the desired solution and the number of different task demands in the input, UFT is FPT under (1 + δ)-resource augmentation of the edge capacities for parameters k and 1/δ, and UFT admits an FPT-5-approximation algorithm for parameter k. One key to our results is to compute structured hitting sets of the input edges which partition the given tree into O(k) clean components. This allows us to guess important properties of the optimal solution. Also, in some settings we can compute core sets of subsets of tasks out of which at least one task i is contained in the optimal solution. These sets have bounded size, and hence we can guess this task i easily. A consequence of our results is that the integral multicommodity flow problem on trees is FPT if the parameter is the desired amount of sent flow. Also, even under (1 + δ)-resource augmentation UFT is APX-hard, and hence our FPT-approximation algorithm for this setting breaks this boundary. © Tomás Martínez-Muñoz and Andreas Wiese;licensed under Creative Commons License CC-BY 4.0

关键词： approximation algorithms

Better approximation algorithms for Maximum Weight Internal Spanning Trees in Cubic Graphs and Claw-Free Graphs 15th

学校读者我要写书评

暂无评论

Better Approximation Algorithms for Maximum Weight Internal ...

15th International Conference on algorithms and Computation, WALCOM 2021

作者： Biniaz, Ahmad School of Computer Science University of Windsor Windsor Canada

ISBN: (纸本)9783030682101

Given a connected vertex-weighted graph G, the maximum weight internal spanning tree (MaxwIST) problem asks for a spanning tree of G that maximizes the total weight of internal nodes. This problem is NP-hard and APX-hard, with the currently best known approximation factor 1/2 (Chen et al., Algorithmica 2019). For the case of claw-free graphs, Chen et al. present an involved approximation algorithm with approximation factor 7/12. They asked whether it is possible to improve these ratios, in particular for claw-free graphs and cubic graphs. For cubic graphs we present an algorithm that computes a spanning tree whose total weight of internal vertices is at least 34-3n times the total weight of all vertices, where n is the number of vertices of G. This ratio is almost tight for large values of n. For claw-free graphs of degree at least three, we present an algorithm that computes a spanning tree whose total internal weight is at least 35-1n times the total vertex weight. The degree constraint is necessary as this ratio may not be achievable if we allow vertices of degree less than three. With the above ratios, we immediately obtain better approximation algorithms with factors 34-ϵ and 35-ϵ for the MaxwIST problem in cubic graphs and claw-free graphs having no degree-2 vertices, for any ϵ> 0. The new algorithms are short (compared to that of Chen et al.) and fairly simple as they employ a variant of the depth-first search algorithm. Moreover, they take linear time while previous algorithms for similar problem instances are super-linear. © 2021, Springer Nature Switzerland AG.

关键词： approximation algorithms

approximation algorithms for LCS and LIS with truly improved running times

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Rubinstein, Aviad Seddighin, Saeed Song, Zhao Sun, Xiaorui Stanford University Toyota Technological Institute Chicago United States Adobe Research University of Illinois

Longest common subsequence (LCS) is a classic and central problem in combinatorial optimization. While LCS admits a quadratic time solution, recent evidence suggests that solving the problem may be impossible in truly subquadratic time. A special case of LCS wherein each character appears at most once in every string is equivalent to the longest increasing subsequence problem (LIS) which can be solved in quasilinear time. In this work, we present novel algorithms for approximating LCS in truly subquadratic time and LIS in truly sublinear time. Our approximation factors depend on the ratio of the optimal solution size over the input size. We denote this ratio by λ and obtain the following results for LCS and LIS without any prior knowledge of λ. • A truly subquadratic time algorithm for LCS with approximation factor Ω(λ3). • A truly sublinear time algorithm for LIS with approximation factor Ω(λ3). Triangle inequality was recently used by Boroujeni, Ehsani, Ghodsi, HajiAghayi and Seddighin [BEG+18] and Charkraborty, Das, Goldenberg, Koucky and Saks [CDG+18] to present new approximation algorithms for edit distance. Our techniques for LCS extend the notion of triangle inequality to non-metric settings. © 2021, CC BY-NC-SA.

关键词： approximation algorithms

approximation algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree

学校读者我要写书评

暂无评论

arXiv 2025年

作者： D’Angelo, Gianlorenzo Delfaraz, Esmaeil Viale F. Crispi 7 L’Aquila67100 - Italy University of L’Aquila Via Vetoio snc L’Aquila67100 - Italy

In the Connected Budgeted maximum Coverage problem (CBC), we are given a collection of subsets S, defined over a ground set X, and an undirected graph G = (V, E), where each node is associated with a set of S. Each set in S has a different cost and each element of X gives a different prize. The goal is to find a subcollection S′ ⊆ S such that S′ induces a connected subgraph in G, the total cost of the sets in S′ does not exceed a budget B, and the total prize of the elements covered by S′ is maximized. The Directed rooted Connected Budgeted maximum Coverage problem (DCBC) is a generalization of CBC where the underlying graph G is directed and in the subgraph induced by S′ in G must be an out-tree rooted at a given node. The current best algorithms achieve approximation ratios that are linear in the size of G or depend on B. In this paper, we provide two algorithms for CBC and DCBC that guarantee approximation ratios of O (logǫ22|X|) and O (√|V |ǫlog22 |X|) , resp., with a budget violation of a factor 1 + ǫ, where ǫ ∈ (0, 1]. Our algorithms imply improved approximation factors of other related problems. For the particular case of DCBC where the prize function is additive, we improve from O (ǫ12 |V |2/3 log |V |) to O (ǫ12 |V |1/2 log2 |V |). For the minimum connected set cover, a minimization version of CBC, and its directed variant, we obtain approximation factors of O(log3 |X|) and O(p|V | log3 |X|), resp. For the Node-Weighted Group Steiner Tree and and its directed variant, we obtain approximation factors of O(log3 k) and O(p|V | log3 k), resp., where k is the number of groups. © 2025, CC BY.

关键词： approximation algorithms

approximation algorithms for 1-Wasserstein distance between persistence diagrams

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Chen, Samantha Wang, Yusu University of California San Diego United States

Recent years have witnessed a tremendous growth using topological summaries, especially the persistence diagrams (encoding the so-called persistent homology) for analyzing complex shapes. Intuitively, persistent homology maps a potentially complex input object (be it a graph, an image, or a point set and so on) to a unified type of feature summary, called the persistence diagrams. One can then carry out downstream data analysis tasks using such persistence diagram representations. A key problem is to compute the distance between two persistence diagrams efficiently. In particular, a persistence diagram is essentially a multiset of points in the plane, and one popular distance is the so-called 1-Wasserstein distance between persistence diagrams. In this paper, we present two algorithms to approximate the 1-Wasserstein distance for persistence diagrams in near-linear time. These algorithms primarily follow the same ideas as two existing algorithms to approximate optimal transport between two finite point-sets in Euclidean spaces via randomly shifted quadtrees. We show how these algorithms can be effectively adapted for the case of persistence diagrams. Our algorithms are much more efficient than previous exact and approximate algorithms, both in theory and in practice, and we demonstrate its efficiency via extensive experiments. They are conceptually simple and easy to implement, and the code is publicly available in github. 2012 ACM Subject Classification Theory of computation approximation algorithms analysis. © 2021, CC BY.

关键词： approximation algorithms

approximation algorithms for the random-field Ising model

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Helmuth, Tyler Lee, Holden Perkins, Will Ravichandran, Mohan Wu, Qiang Durham University Mathematical Sciences Department Duke University Department of Mathematics University of Illinois at Chicago Department of Mathematics Statistics and Computer Science Bogazici University Department of Mathematics University of Illinois at Urbana-Champaign Department of Mathematics

Approximating the partition function of the ferromagnetic Ising model with general external fields is known to be #BIS-hard in the worst case, even for bounded-degree graphs, and it is widely believed that no polynomial-time approximation scheme exists. This motivates an average-case question: are there classes of instances for which polynomial-time approximation schemes exist? We investigate this question for the random field Ising model on graphs with maximum degree ∆. We establish the existence of fully polynomial-time approximation schemes and samplers with high probability over the random fields if the external fields are IID Gaussians with variance larger than a constant depending only on the inverse temperature and ∆. The main challenge comes from the positive density of vertices at which the external field is small. These regions, which may have connected components of size Θ(log n), are a barrier to algorithms based on establishing a zero-free region, and cause worst-case analyses of Glauber dynamics to fail. The analysis of our algorithm is based on percolation on a self-avoiding walk tree. Copyright © 2021, The Authors. All rights reserved.

关键词： approximation algorithms

Improved approximation algorithms for 2-dimensional knapsack: Packing into multiple L-shapes, spirals, and more 37

学校读者我要写书评

暂无评论

Improved approximation algorithms for 2-dimensional knapsack...

37th International Symposium on Computational Geometry, SoCG 2021

作者： Gálvez, Waldo Grandoni, Fabrizio Khan, Arindam Ramírez-Romero, Diego Wiese, Andreas Department of Computer Science TU München Germany IDSIA USI-SUPSI Lugano Switzerland Department of Computer Science and Automation Indian Institute of Science Bangalore India Department of Mathematical Engineering Universidad de Chile Santiago Chile Department of Industrial Engineering Center for Mathematical Modeling Universidad de Chile Santiago Chile

ISBN: (纸本)9783959771849

In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsack and a collection of n rectangular items with integer sizes and profits. Our goal is to find the most profitable subset of items that can be packed non-overlappingly into the knapsack. The currently best known polynomial-time approximation factor for 2DK is 17/9 + Ε © Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero, and Andreas Wiese;licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).

关键词： approximation algorithms

approximation algorithms for demand strip packing

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Gálvez, Waldo Grandoni, Fabrizio Ameli, Afrouz Jabal Khodamoradi, Kamyar Technical University of Munich Germany IDSIA USI-SUPSI Switzerland University of Würzburg Germany

In the Demand Strip Packing problem (DSP), we are given a time interval and a collection of tasks, each characterized by a processing time and a demand for a given resource (such as electricity, computational power, etc.). A feasible solution consists of a schedule of the tasks within the mentioned time interval. Our goal is to minimize the peak resource consumption, i.e. the maximum total demand of tasks executed at any point in time. It is known that DSP is NP-hard to approximate below a factor 3/2, and standard techniques for related problems imply a (polynomial-time) 2-approximation. Our main result is a (5/3 + Ε)approximation algorithm for any constant Ε > 0. We also achieve best-possible approximation factors for some relevant special cases. Copyright © 2021, The Authors. All rights reserved.

关键词： approximation algorithms