Approximation algorithm for the multicovering problem [PDF]
Let $\mathcal{H}=(V,\mathcal{E})$ be a hypergraph with maximum edge size $\ell$ and maximum degree $Δ$. For given numbers $b_v\in \mathbb{N}_{\geq 2}$, $v\in V$, a set multicover in $\mathcal{H}$ is a set of edges $C \subseteq \mathcal{E}$ such that every vertex $v$ in $V$ belongs to at least $b_v$ edges in $C$. Set Multicover is the problem of finding
Abbass Gorgi +3 more
openaire +3 more sources
Approximation algorithms [PDF]
Increasing global competition, rapidly changing markets, and greater consumer awareness have altered the way in which corporations do business. To become more efficient, many industries have sought to model some operational aspects by gigantic optimization problems. It is not atypical to encounter models that capture 10
Schulz, Andreas S. +2 more
openaire +2 more sources
An Approximation Algorithm for Approximation Rank [PDF]
One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication matrix.
Troy Lee, Adi Shraibman
openaire +4 more sources
Algorithms and error bounds for multivariate piecewise constant approximation [PDF]
We review the surprisingly rich theory of approximation of functions of many vari- ables by piecewise constants. This covers for example the Sobolev-Poincar´e inequalities, parts of the theory of nonlinear approximation, Haar wavelets and tree ...
Davydov, Oleg
core +3 more sources
Streaming Algorithms with Large Approximation Factors [PDF]
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
Approximation Algorithms for Directed Weighted Spanners [PDF]
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
Approximation Algorithms for Hitting Subgraphs [PDF]
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 +3 more sources
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints [PDF]
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
Approximation methods for hybrid diffusion systems with state-dependent switching processes : numerical algorithms and existence and uniqueness of solutions [PDF]
By focusing on hybrid diffusions in which continuous dynamics and discrete events coexist, this work is concerned with approximation of solutions for hybrid stochastic differential equations with a state-dependent switching process.
Yuan, Chenggui +3 more
core +4 more sources
Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth [PDF]
In this paper we present two novel generic schemes for approximation algorithms for optimization to partial k-trees. Our first scheme yields deterministic polynomialtime algorithms achieving typically an approximation factor of k/ log n, where k
Chlebikova, Janka +14 more
core +1 more source

