# Questions tagged [approximation-algorithms]

425 questions
Filter by
Sorted by
Tagged with
84 views

### What is the competitive ratio of a $d$-way associative LRU cache?

In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$. It is well known that for ...
117 views

In MAX-SAT, given a formula, we want to maximize the number of satisfied clauses: given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the largest $k\... 2answers 137 views ### Minimum relevant variables in linear system - additive approximation In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.: $$A x = b$$ and the goal is to find a solution$x$with as few nonzero variables as ... 0answers 162 views ### Best polynomial-time approximation factor for NP-optimization problems Let us say that a function$f(n)$is the best approximation factor for an NP-optimization problem, if both of the following hold: There exist a polynomial-time algorithm$A,$and an integer$n_0$, ... 0answers 136 views ### Grid-Minor Theorem of Robertson and Seymour and its Algorithmic Applications Graph-Minor Theorem of Robertson and Seymour  states that if graph G has large treewidth, then it contains a large grid as minor. Most approximation results on general classes of graphs with ... 0answers 51 views ### PTAS for projective clustering : survey$(k,j)$-projective clustering is the natural generalisation for k-clustering, in which one needs to find$kj$-flats in$\mathbb{R}^d$that minimizes the cost function as defined below: Given a$j$-... 0answers 37 views ### Best approach for allocation problem I am a bit rusty on optimization algorithms and need an advice. This is my problem: I have n images (with width and ... 0answers 62 views ### Why do k min-hashes, instead of one hash where we find the k minimum elements? Traditionally if one wants to sketch streams for Jaccard similarity hashing, one finds the minimum element in each of$k$permutation for comparison purposes, and then takes number_of_collisions /$k$... 1answer 213 views ### Does Max Planar 3-SAT admit a PTAS? Suppose we are given a formula$\phi$of 3-SAT, with variables$x_1,\dots, x_n$and clauses$C_1,\dots, C_m$. Consider the graph$G_\phi$where there is one node for each clause$C_i$, for each ... 0answers 158 views ### Classification of randomized approximation algorithms Is there a known classification of randomized approximation algorithms, in the same vein as the distinction between Monte Carlo and Las Vegas algorithms for decision problems? (Or equivalently ... 1answer 65 views ### Polynomial approximation algorithm for set cover with assumption We want to cover$n$elements with some sets from$S_1, …, S_m$(classical set cover). We furthermore suppose that any element belongs to at least$k$sets and want to find a set cover with cardinal ... 0answers 109 views ### Counting the maximum number of paths of length$n$that differ in at least$k$edges What is known about the complexity of solving (or approximately solving) the following problem? INPUT: Graph$G=(V,E)$and constants$L$and$K$. OUTPUT: The maximum size of any set$S$of simple ... 1answer 145 views ### About a pre-processing step for primal–dual weighted set cover problem I was reading the paper titled "Primal-dual RNC approximation algorithms.." by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1. They present a dual fitting based algorithm ... 2answers 340 views ### Finding a set which dominates the Minimum Dominating Set Given an unweighted, undirected graph, a dominating set$S$is a set of nodes such that every node is in$S$or adjacent to a node in$S$. The dominating set problem is NP-hard, but I am considering ... 0answers 37 views ### Approximate answer to Max-SMT (bitvector) query I have a problem that could be completely solved as Max-SMT instances in the theory of quantifier-free bit-vectors, but it apparently is too complex to be tractable with current Max-SMT technology. ... 2answers 338 views ### Max cut problem between two connected subgraphs Let$G$be a connected graph. Consider the problem of finding a partition$G = A \cup B$into connected subgraphs, so that the cut between$A$and$B$is maximized. Is there anything which is known ... 2answers 190 views ### What is the best approximation and exact algorithm for vertex cover on cubic graphs? "Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm. 0answers 75 views ### k-center 2.0: A stronger k-center condition Given an unweighted, undirected graph, we can use the classical 2-appx for$k$-center to select a set$S$of centers such that every vertex is within a distance of 2 of some center in$S$. Note that ... 1answer 53 views ### Complexity of distributively verifying that the diameter is small Consider a graph$G=(V,E)$and an integer parameter$k$. I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than ... 1answer 119 views ### Smoothed analysis to compare algorithms Has there been any research using smoothed analysis to compare approximation algorithms that have the same approximation ratio? Any research that compares algorithms using smoothed analysis would be ... 1answer 100 views ### How can algorithms with nested combinatorial searches be quasi-linear? I've come across algorithms similar to the one below, where a demanding step is performed, which should have at least polynomial complexity, yet the whole algorithm is deemed quasi-linear without ... 5answers 550 views ### W-hard problems with FPT time approximation algorithms I'm looking for problems that are hard to solve in FPT time but has an approximation algorithm. That is, problems that are: R1. W-hard. R2. Admit a (preferably constant) approximation algorithm ... 0answers 73 views ### Is there any online problem that the best known competitive ratio is better than the hardness of approximation (or the best known approximation)? In online-setting, we usually allow exponential time to think and come up with a strategy. On the other hand, in offline-setting, we might care about solving a particular problem optimally, or as good ... 1answer 56 views ### Does the following 2-rounds distributed algorithm approximates a maximal matching well? Let$G$be an undirected graph. I'm looking for a two-rounds distributed algorithm that matches as many vertex pairs as possible. Consider the following protocol for vertex$v$. Use a fair coin to ... 0answers 247 views ### Can we find a generic tight example for the greedy algorithm of the unweighted generalized assignment problem? In the unweighted generalized assignment problem (UGAP) we have$n$items and$k$knapsacks. For each item$i$and knapsack$j$, there is a weight$w_{ij}$. Also, every knapsack has a capacity$W$. ... 1answer 152 views ### Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph? I would like to know any results in terms of approximation algorithm about Maximum weight Independent Set problem in coloring graph. Input: Given a graph G with non-negative vertex weights and valid ... 1answer 162 views ### Minimizing SubModular Function: Cardinality Given a submodular function f: 2^V to reals (not necessarily monotone), and an integer k, find a set S such that |S| <= k and such that f(S) is minimized. When the size constraint is |S| >=k, the ... 1answer 91 views ### About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective Is there any algorithm which shows that under the assumption of Lipschitz smoothness of the Hessian of a non-convex function one can get to its critical point faster? 0answers 59 views ### What is the fastest gradient based algorithm to get to criticality of a “nice” non-convex function? I am allowing for the following properties for a once differentiable non-convex$f : \mathbb{R}^d \rightarrow \mathbb{R}$, (a) Let there be a$\sigma >0$s.t the norm of the gradient of the ... 0answers 269 views ### Hardness of Approximation for minimum path cover in an undirected graph? Given an undirected graph$G = (V,E)$, a path cover is a set of disjoint paths such that every vertex$v\in V$belongs to exactly one path. The minimum path cover problem consists of finding a path ... 0answers 33 views ### Getting to local/global minima with (stochastic) gradient descent on non-convex objectives Is there any class of non-convex objective functions for which (stochastic) gradient descent can provably get to a local or a global minima? (..maybe in the approximate sense like a point such that ... 0answers 44 views ### Approximating a monotone submodular function using a concrete coverage function Is it possible to approximate a monotone submodular function using a concrete coverage function, i.e. Given a ground set$U$and a monotone submodular function,$f:2^U\to \mathbb{R}$, the goal is to ... 1answer 210 views ### Monotone supermodular function minimization under partition matroid constraints Is there a known approximation algorithm for the problem of minimizing a monotone (non increasing) supermodular function under partition matroid constraints ? 0answers 109 views ### Learning hidden variable distribution Consider a set of$k$continuous variables. Each variable$x_k$is associated with a hidden distribution from which its value is sampled independently of other variables. I am given a set of ... 0answers 124 views ### Stacks serving interval storage requests An interval storage request is represented by a tuple$(s,t,v)$satisfying$s<t$, meaning that the value$v$needs to be stored from time$s$to time$t$. A stack serves the request$(s,t,v)$in ... 0answers 96 views ### Unbalanced connected partition Let$G = (V, E)$be a connected graph with (possibly negative) vertex weights$w(v)\in\mathbb{Z}$. We want to partition the vertices into two parts such that the induced graphs$G'$and$G''$are ... 1answer 600 views ### Common terminology used for lower/upper bounds Suppose you have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound?... 0answers 151 views ### An optimal subspace projection problem Suppose we have a$k$-dimensional subspace$V$in$\mathbb{R}^n$given by a basis$\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set$I\subset [n]$with$|I|=m$where$k\le m\le n$, such that $$\... 2answers 196 views ### Geometric max cover Consider n points and a distance function d that satisfies the triangle inequality. We are also given a number r. Each point p defines a set B_p (or a ball) that covers all other points ... 1answer 397 views ### Find an approximate argmax using only approximate max queries Consider the following problem. There are n unknown values v_1, \cdots, v_n \in \mathbb{R}. The task is to find the index of the largest one using only queries of the following form. A query ... 0answers 60 views ### \alpha-path on Euclidean graphs Consider the following problem: Suppose we are given a G=(V, E) Euclidean Graph in the plane and a real \alpha > 0. For simplicity assume, there exists only one path whose summation of weights ... 0answers 103 views ### Hausdorff Distance and Convex Hull Given two sets of points A and B, both in R^d, is there a relation between the convex hulls of A and B, i.e. conv(A) and conv(B), w.r.t. the Hausdorff distance between A and B? In other words, does ... 0answers 155 views ### Lower bound for Yao's algorithm on general addition chains? An addition chain of size n for given integers n_1,n_2\dots ,n_p is a sequence of integers k_1,k_2\dots ,k_n such that k_1=1, for all i (2\le i\le m) we have k_i=k_j+k_m for some 1\le ... 0answers 113 views ### On approximating problems in \#P We know that for every counting problem \#A in \#P, there is a probabilistic algorithm \mathcal C that on input x, computes with high probability a value v such that$$(1 − ε)\#A(x) ≤ v ≤ (1 ... 0answers 62 views ### On the impossibility of representing/approximating subadditive function using additive functions I am trying to understand whether a monotone and subadditive function$f(S), S \subseteq 2^{[n]}$and$ f : 2^{[n]} \rightarrow R_{\geq0}$can be represented using an additive function$\hat{f}(S) = \...
Consider a universe $N$ containing $n$ elements, and a collection of sets $\mathcal{C}$, over $N$. The $k$-multiset multicover (MSMC) problem is to cover all elements of the universe $N$ at least $k$ ...