Approximation Algorithms for Hitting Subgraphs [PDF]
, 2021 Let $H$ be a fixed undirected graph on $k$ vertices. The $H$-hitting set problem asks for deleting a minimum number of vertices from a given graph $G$ in such a way that the resulting graph has no copies of $H$ as a subgraph. This problem is a special case of the hypergraph vertex cover problem on $k$-uniform hypergraphs, and thus admits an efficient ...
Noah Brüstle +4 more
openaire +2 more sources
A Performance Study of Some Approximation Algorithms for Computing a Small Dominating Set in a Graph [PDF]
, 2020 Article implements and tests the performances of several approximation algorithms for computing the minimum dominating set of a graph.
Potru, Rohan +5 more
core +1 more source
Approximation Algorithms for Sorting λ-Permutations by λ-Operations
Algorithms, 2021 Understanding how different two organisms are is one question addressed by the comparative genomics field. A well-accepted way to estimate the evolutionary distance between genomes of two organisms is finding the rearrangement distance, which is the ...
Guilherme Henrique Santos Miranda +3 more
doaj +1 more source
Combinatorial Dominance Guarantees for Heuristic Algorithms [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 An $f(n)$ $\textit{dominance bound}$ on a heuristic for some problem is a guarantee that the heuristic always returns a solution not worse than at least $f(n)$ solutions.
Daniel Berend +2 more
doaj +1 more source
Approximation Algorithms for Directed Weighted Spanners [PDF]
, 2023 In the pairwise weighted spanner problem, the input consists of a weighted directed graph on n vertices, where each edge is assigned both a cost and a length. Furthermore, we are given k terminal vertex pairs and a distance constraint for each pair.
Lin, Young-San +2 more
core +1 more source
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints [PDF]
, 2020 We give improved multi-pass streaming algorithms for the problem of maximizing a monotone or arbitrary non-negative submodular function subject to a general p-matchoid constraint in the model in which elements of the ground set arrive one at a time in a ...
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) +6 more
core +1 more source
Greedy Algorithms for Optimal Distribution Approximation
Entropy, 2016 The approximation of a discrete probability distribution t by an M-type distribution p is considered. The approximation error is measured by the informational divergence D ( t ∥ p ) , which is an appropriate measure, e.g., in the ...
Bernhard C. Geiger, Georg Böcherer
doaj +1 more source
Streaming Algorithms with Large Approximation Factors [PDF]
, 2022 We initiate a broad study of classical problems in the streaming model with insertions and deletions in the setting where we allow the approximation factor α to be much larger than 1.
Zhang, Yuheng +3 more
core +1 more source
Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements [PDF]
, 2014 We consider degree bounded network design problems with element and vertex connectivity requirements. In the degree bounded Survivable Network Design (SNDP) problem, the input is an undirected graph G = (V, E) with weights w(e) on the edges and degree ...
Ali Vakilian +3 more
core +1 more source
Scalability of Betweenness Approximation Algorithms: An Experimental Review
IEEE Access, 2019 Betweenness centrality, which measures the contribution of an individual node to the network's connectivity by counting the number of shortest paths a node appears in, is widely used for the analysis of the complex networks.
Sebastian Wandelt +2 more
doaj +1 more source