Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [approximation-algorithms]

Questions about approximation algorithms.

2
votes
0answers
59 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 ...
-1
votes
0answers
60 views

Approximate Multi Covering with Randomized Rounding

In the set multicover problem we are given a set $N$ of $n$ elements and a set $S$ of $m$ subsets of $N$. Additionally, each element has a coverage requirement (the number of times it has to be ...
2
votes
1answer
83 views

Maximum-minimum satisfiability

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\...
3
votes
2answers
101 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 ...
2
votes
0answers
146 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$, ...
6
votes
0answers
99 views

Grid-Minor Theorem of Robertson and Seymour and its Algorithmic Applications

Graph-Minor Theorem of Robertson and Seymour [1] 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 ...
1
vote
0answers
30 views

PTAS for projective clustering : survey

$(k,j)$-projective clustering is the natural generalisation for k-clustering, in which one needs to find $k$ $j$-flats in $\mathbb{R}^d$ that minimizes the cost function as defined below: Given a $j$-...
1
vote
0answers
34 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 ...
1
vote
0answers
47 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$ ...
6
votes
1answer
159 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 ...
5
votes
0answers
141 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 ...
0
votes
1answer
51 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 ...
2
votes
0answers
83 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 ...
2
votes
1answer
111 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 ...
3
votes
2answers
155 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 ...
2
votes
0answers
33 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. ...
4
votes
2answers
131 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 ...
2
votes
1answer
88 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.
1
vote
0answers
49 views

maximization of non-negative monotone supermodular set function with cardinality constraints

the following link Maximizing a monotone supermodular function s.t. cardinality says no kind approximation possible for maximizing non negative supermodular function subject to maximum cardinality ...
1
vote
0answers
53 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 ...
3
votes
1answer
47 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 ...
4
votes
0answers
59 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 ...
0
votes
1answer
96 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 ...
9
votes
4answers
230 views

W[1]-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[1]-hard. R2. Admit a (preferably constant) approximation algorithm ...
2
votes
0answers
66 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 ...
0
votes
0answers
49 views

Metric 1-Center in l-infinity norm (when dimension is part of the input)

Consider the following problem, Input: A number $d>0$, $X \subseteq \mathbb{R}^d$. Output: A center $c\in \mathbb{R}^d$ s.t $\max_{x \in X} \lVert x - c\rVert_p $ is minimized. This is the 1-...
1
vote
1answer
54 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 ...
0
votes
0answers
66 views

Hypergraph Coloring Complexity

Dear can you help I am confused about the complexity of hypergraph coloring and finding the minimum number of colors Finding the minimum number of colors for strongly coloring a k-uniform hypergraph ...
3
votes
0answers
217 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$. ...
0
votes
1answer
95 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 ...
1
vote
1answer
90 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 ...
0
votes
1answer
43 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?
1
vote
0answers
58 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 ...
2
votes
0answers
118 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 ...
1
vote
0answers
32 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 ...
4
votes
0answers
35 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 ...
1
vote
1answer
105 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 ?
5
votes
0answers
105 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 ...
0
votes
0answers
410 views

APX-Hard vs NP-Hard

I am confused whether $\mathsf{APX-hard} \subseteq \mathsf{NP-hard}$. My confusion stems from a result on graph pricing from this paper which says the following : "Unlike the general case of the graph ...
3
votes
0answers
118 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 ...
2
votes
0answers
81 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 ...
1
vote
1answer
299 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?...
5
votes
0answers
104 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 $$\...
0
votes
2answers
130 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 ...
10
votes
1answer
283 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 ...
1
vote
0answers
56 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 ...
1
vote
0answers
63 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 ...
6
votes
0answers
122 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 ...
2
votes
0answers
107 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 ...
2
votes
0answers
46 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) = \...