Questions about approximation algorithms.

learn more… | top users | synonyms

1
vote
0answers
24 views

The distribution on the solution space induced by randomized rounding

Consider the Goemans-Williamson algorithm for the MAX-CUT problem. It is known, that if $maxcut(G) \geq 1-\epsilon$, then the algorithm returns a cut $S$ of fractional size at least ...
0
votes
0answers
56 views

k closest points that belong to a set

This is a question from theory community, but I came across this issue in a practical problem. So just have this in mind. I have a set of real vectors: $$ S = \lbrace v_1, \dots, v_n \rbrace $$ ...
-2
votes
0answers
139 views

How to reduce the computational complexity max algorithm in this specific case

We work over $\mathbb{R}_+^L$. Let $V$ be the set of column vectors whose coordinates take values $0$ or $1$. Thus, $V$ contains $2^L$ vectors. Let $\mathbf{w}(t)$ (in $\mathbb{R}_+^L$) a vector that ...
-1
votes
0answers
32 views

Reducing computational complexity of sorting algorithm in this specific case [duplicate]

We work over $\mathbb{R}^L$. Let $V$ be the set of column vectors whose coordinates take values $0$ or $1$. Thus, $V$ contains $2^L$ vectors. Let $\mathbf{w}(t)$ (in $\mathbb{R}^L$) a vector that ...
6
votes
0answers
60 views

Approximating a max-cut's intersection with other cuts

For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any ...
8
votes
0answers
91 views

Advances towards proving the Held-Karp conjecture for TSP

I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture. The Held-Karp relaxation is conjectured to have an integrality gap of ...
3
votes
1answer
65 views

Approximation algorithms for min vector subset-sum over GF(2)

In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum. Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing ...
3
votes
0answers
47 views

Maximizing a submodular function with restricted values

Maximizing a general monotone submodular function $f$ under the constraint that $|S|\leq k$, can be approximated to $(1-1/e)$. I am wondering if a better approximation algorithm exists if the ...
14
votes
0answers
376 views

Practically Good Algorithms of a Very Low Computational Complexity Class

I am looking for one (or more) examples of a parametric class of algorithms $P_t$ for approximately solving a class $\cal A$ of algorithmic questions with the following properties: 1) Solving the ...
11
votes
0answers
195 views

What is this variant of set cover problem known as?

Input is a universe $U$ and a family of subsets of $U$, say, ${\cal F} \subseteq 2^U$. We assume that the subsets in ${\cal F}$ can cover $U$, i.e., $\bigcup_{E\in {\cal F}}E=U$. An incremental ...
4
votes
2answers
111 views

Variation on partial Set Cover with penalties

I'm looking at the following problem, which I'm hoping is perhaps a known variant of the Set Cover problem: Input: We're given a universe $U$ and two disjoint subsets $A$ and $B$ such that $A \cup ...
5
votes
0answers
192 views

Tuning Parameters of Locality Sensitive Hashing

We have given a set of $n$ binary vectors each of dimension $d$, i.e. a binary matrix of $d*n$. Our goal is to group vectors which are almost similar, $\forall v_i, v_j\in\{0,1\}^d$, we say $v_i$ ...
0
votes
0answers
46 views

Minimum vector sets span spaces cover problem

Instance: a set of vectors $V=\{\mathbf{v}_1,\mathbf{v}_2,...,\mathbf{v}_n\}$ and $m$ vector sets $V_1,V_2,...,V_m$, each of which contains multiple vectors ($V_i$ may not be a subset of $V$). In our ...
10
votes
0answers
181 views

Can we approximate the number of words accepted by an NFA?

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete. The second ...
2
votes
1answer
80 views

Approximating the value of k in $k$-mean clustering problem

Consider a set of $n$ points in $R^d$ which are covered by some finitely many (say $k$) unit balls. Can we approximate the value of $k$ by querying only sublinear many points. More precisely, by ...
4
votes
1answer
115 views

Inapproximability of $(\alpha, \beta)$ bi-criteria approximation

An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the ...
0
votes
0answers
132 views

Clustering in sublinear time/query

Given a set of $n$ points in $R^d$, the goal is to cover them with (finitely many) unit balls such that following conditions satisfy: 1) Minimizing the number of balls that are required to cover all ...
-1
votes
1answer
45 views

Combinatorial algorithm for load balancing

I have a problem that can be solved with linear programming, but I'm hoping there's a combinatorial algorithm for this (even approximation is fine). This is basically a load balancing problem using ...
0
votes
0answers
36 views

Estimating Graph/ Network Accuracy

If I'm creating a (social) network using some automatic system, which I know is not 100% accurate but for which I can estimate the rate of error, what, if anything, can I say about the accuracy of the ...
1
vote
0answers
43 views

inapproximability of logarithic factor of indepence set [closed]

The hardness result derived using PCP theorem for Independent set suggests that there exists some absolute constant $\epsilon_0$ such that for $0< \epsilon < \epsilon_0$, it is hard to ...
3
votes
0answers
39 views

Approximation of covering number in metric space

Consider the following setting: Let $(X,d)$ be a metric space and let $S$ be a finite subset of $X$. An $\epsilon$-cover of $S$ is any subset $C\subset S$ such that $$ \max_{x\in S} d(x,C)\leq ...
6
votes
1answer
194 views

Why is complementary slackness important?

Complementary slackness (CS) is commonly taught when talking about duality. It establishes a nice relation between the primal and the dual constraint/variables from a mathematical viewpoint. The two ...
2
votes
1answer
1k views

A quantum algorithm for GCD

Does anyone know of a direct quantum algorithm for computing GCD, - There could be quantum gates for addition subtraction constructed explicitly, using CNOT, etc. - the construction can be done in ...
0
votes
0answers
46 views

How can I show that zero-one programming is not in APX?

How can I show that zero-one programming is not in APX? Vertex Cover Problem is in the APX class. So can I try a PTAS-reduction from the zero-one programming problem to Vertex Cover and show that ...
8
votes
0answers
188 views

Additive error in counting the number of 1's in a sliding window?

The setting is as follows: We're given a stream of bits. At time $t$ you get to see bit $b_t$, and required to output $\widehat{s_t} \approx \Sigma_{i=0}^{N}b_{t-i}$ (i.e. approximately how many 1's ...
1
vote
2answers
100 views

Maximum item in data stream

I have N elements and need to find the maximum of these elements. At each time tick, exactly one of the N elements is updated and I need to determine the new max element (more specifically, the index ...
0
votes
0answers
61 views

Estimate the maximum by randomized approximation algorithms

Given a set $A$ of $2^n$ elements such that each $a\in A$ is a rational in $[0,1]$. The question is to estimate $\max(A)$, i.e., the maximal element of $A$. Is there a polynomial algorithm to ...
9
votes
1answer
154 views

Bisecting a set of points into two optimal subsets

I want to divide a set of points into two equally-sized subsets such that the within-cluster sum of squares is minimized. We can assume that the points are in two-dimensional Euclidian space. I'm ...
8
votes
2answers
168 views

Approximating #P-hard problems

Consider the classical #P-complete problem #3SAT, i.e., to count the number of valuations to make a 3CNF with $n$ variables satisfiable. I am interested in the additive approximability. Clearly, there ...
2
votes
3answers
149 views

The number of integral points in a polytope

Suppose we define a polytope with $$ \mathbf{Ax} \leq \mathbf{b} $$ What is the best way to find/approximate the number of the integral points in the polytope? Update: how hard is the complexity ...
0
votes
0answers
126 views

Calculating exact/approximate solution to a formula

Suppose we have a set of variable $\mathbf{y} = \left(y_1, ..., y_n \right)$. Also consider the set of functions $g_i(y_i), 1 \leq i \leq n$. Note that $g_i()$ is dependent only on $y_i$. Consider ...
2
votes
1answer
117 views

Hardness of approximating chromatic number of triangle-free graphs

The chromatic number of graph, $\chi( G)$ is hard to approximate for general graphs. Are there results of hardness of approximating $\chi(G)$ for triangle-free graphs?
5
votes
0answers
124 views

Approximate c-chromatic number, each color class is P4-free (cograph)

The classic chromatic number of graph, $\chi(G)$, describes the minimum number of colors needed so that each color class is an independent set. There are many other graph coloring definitions. One of ...
8
votes
1answer
179 views

Tight examples for approximating the feedback vertex set problem

There are several 2-approximation algorithms for the UNWEIGHTED feedback vertex set problem (FVS), which are summarized in [4]. Note that the reduction from vertex cover to FVS is ...
1
vote
0answers
31 views

Approximation algorithm to a minimization problem with optimization function going to zero

I have a simple function to minimize, but it is not discrete: $f(x) = 2x - \alpha x - c(x)$, where $x$ is a natural number, $\alpha$ is a rational number, $0 \leq \alpha \leq 1$, and $0 \leq c(x) \leq ...
6
votes
1answer
87 views

Minimize makespan on identical machines when jobs are vectors

Given are $n$ $d$-dimensional vectors and $m$ machines where $d$ need not be fixed. The objective is to minimize the makespan i.e., assign the vectors to machines such that the maximum of the ...
14
votes
1answer
336 views

Does PSPACE-completeness imply approximation hardness?

It is mentioned in a comment in another cstheorySE post that PSPACE-completeness imply APX-hardness. Can anyone please explain/share a reference for it? Is this "tight"? (i.e., are there ...
7
votes
2answers
244 views

Planted Clique in G(n,p), varying p

In the planted clique problem, one must recover a $k$-clique planted in an Erdos-Renyi random graph $G(n,p)$. This has mostly been looked at for $p=\frac{1}{2}$, in which case it is known to be ...
2
votes
1answer
67 views

State of the art on approximating quadratic assignment problem

I was wondering what is the state of the art on approximating the quadratic assignment problem (QAP). In particular, I am interested in the following instance. Suppose the $A = (a_{ij}) \in \{0,1\}^{n ...
4
votes
1answer
101 views

Polynomial-time distinguishability threshold of planted clique

I have a basic question regarding the best known polynomial-time "distinguishing advantage" for the planted clique problem. By this, I'm referring to the problem of distinguishing the distribution ...
4
votes
1answer
126 views

Gradient descent-like optimization on a convex landscape with noisy sampling

We have a strictly convex function $f(x,y)$ with a global minimum at $p_{min}$. The goal is to approximate the minimum. E.g. $$f: [0,\pi]^2 \to \mathbb{R}$$ $$f(\theta,\phi) = t_1 \sin \theta + t_2 ...
3
votes
2answers
256 views

Greedy MAX SAT approximation ratio

Consider a naive MAX SAT approximation algorithm: pick a literal $l$ which appears in maximum number of clauses set the corresponding variable of $l$, such that all clauses containing $l$ are ...
2
votes
2answers
151 views

Set packing with maximum coverage objective

We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$. Set-Packing asks how many disjoint sets we can pack, and is defined ...
1
vote
1answer
93 views

Covering by disjoint sets

We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$. I'm interested in the approximability of two problems, or in ...
4
votes
1answer
61 views

Bellman principle and approximability

Does anybody know if a combinatorial optimzation problem that enjoys the Bellman's optimality principle can in automatic way be approximated?
6
votes
2answers
331 views

Proof for ACYCLIC PARTITION being NP-complete

I'm new to this site, so please pardon me for any mistakes and please feel free to edit the question to help get better answers. I'm interested in reading any proof of ACYCLIC PARTITION (Garey and ...
7
votes
1answer
226 views

How bad can the greedy coloring (list color) for the c-chromatic number of graph be?

c-chromatic number is defined in the paper Partitions of graphs into cographs. It asks for the minimum number of colors used to color vertices such that each color class is a cograph. Cograph is a ...
13
votes
1answer
272 views

Is DAG subset sum approximable?

We are given a directed acyclic graph $G=(V,E)$ with a number associated with each vertex ($g:V\to \mathbb{N}$), and a target number $T\in \mathbb{N}$. The DAG subset sum problem (might exist under a ...
0
votes
3answers
168 views

Comparing graphs

I am looking for a kick in the right direction. What i am trying to do is to compute "similarity" between two graphs, where I define "similarity" as the number of shared paths. example: ...
2
votes
0answers
184 views

Why doesn't the standard analysis of set cover $H_n$ greedy extend to partial cover?

Several authors, starting with Slavik, have noted that the classical analysis of the set cover $H_n$ greedy algorithm does not readily extend to the set partial cover problem, where the goal is to ...