Questions about approximation algorithms.

learn more… | top users | synonyms

-3
votes
0answers
31 views

Analaytic expression gives different results from numerical integration [closed]

Please see the attached figure (I tried to upload the figure, but never succeed, complaining "Request returned an error: [error] I'm a teapot") I feed numbers into Log[z/(z-1)] and numerically ...
1
vote
0answers
70 views

Set Cover variant- improvement over log(n) approximation?

Suppose we are asked to produce a set cover of minimal weight, where here w(S)=size(S) (and the weight of the cover is the sum of the weights of its sets). It is well known that in general weighted ...
3
votes
1answer
153 views

What is the reverse of greedy algorithm for setcover?

A common approach to approximating SETCOVER is the greedy algorithm (Algorithm 2.2 Vazirani). This algorithm greedily picks the most cost-effective subset at each iteration, removes covered elements, ...
5
votes
0answers
90 views

Is there an approximation algorithm for MAX k DOUBLE SET COVER?

Given a set system $(X,\mathcal S)$, let us say that a subset $\mathcal C\subseteq \mathcal S$ doubly covers a vertex $x$ in $X$ if $x$ is contained in at least two sets of $\mathcal C$. Let us define ...
16
votes
0answers
302 views

Complexity of approximating the range of a matrix

Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define: $$S_M = |\{Mx : x \in \{-1,1\}^n\}|.$$ I believe that it is NP-hard to compute $S_M$ exactly, by applying ...
3
votes
0answers
105 views

Complexity of minimizing monotone arithmetical formulas

Let's say that I have a multi-variate arithmetical expression $A(x_1, \ldots, x_n)$ that uses addition and multiplication operations and is also in a very simple form of sums of products, e.g., ...
0
votes
0answers
44 views

Generalized caching Problem offline version

statement 1: Here we are given a cache of size k and pages with arbitrary sizes and fetching costs. Given a request sequence of pages, the goal is to minimize the total cost of fetching the pages ...
2
votes
1answer
183 views

Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?

I'm wondering which is the approximation class of Minimum 0-1 Integer Programming if only non-negative integers are used. That is: minimize $c^T \cdot x$, with $x\in \{0,1\}^n$ and $c\in ...
1
vote
0answers
70 views

Distributing bags of apples equally

Assume you have $N$ bags of apples that you want to equally distribute to $K$ people. Each bag contains $n_i$ apples and you are not allowed to open and divide the bags; you must distribute the bags ...
3
votes
1answer
188 views

Approximation algorithms for the maximum $2$-independence set problem

I am interested in approximating the maximum $2$-independent set problem in arbitrary graphs. In a graph $G$ a set $I$ of vertices is called $2$-independent if the distance between any two distinct ...
1
vote
0answers
78 views

Linear Programing with Rounding for the Fire Station Problem

Consider the following fire station problem: The input is a positive integer k and a complete undirected graph $G = (V,E)$ with distances on the edges. The distances form a metric: $d(v, v) = 0$, ...
0
votes
0answers
36 views

Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
0
votes
0answers
23 views

Nearest Neighbor in many dimensions with integers for L_max

We have $n$ points in $d$ dimensional space $\mathbb{N}$ and $n \gg d$. $$ x_i = (a_1,a_2,\ldots,a_d), \; \textsf{when} \; \forall_i a_i \in \mathbb{N}. $$ Distance $d_{max}(a,b) = \sum^d_{i=1} ...
3
votes
1answer
108 views

The complexity of decomposing a bi-stochastic matrix

A bistochastic matrix $A$ is a matrix with positive entries in which each row/column sums to $1$. By the Birkhoff von-Neumann theorem $A$ is a convex combination of permutation matrices. Further, by ...
0
votes
0answers
30 views

On approx-preserving P- and A-reducibilities

Let $X$ and $Y$ be two NPO problems. Let $(f,g)$ be a reduction between $X$ and $Y$, in particular, assume that $(f,g)$ is both P-reduction and A-reduction, i.e., there exist two poly-time ...
0
votes
0answers
68 views

Maximize number of bins and minimize cost of elements chosen from a set

I am considering the following problem: there is a set of elements $S$ where each element is assigned to a bin $B$. The bins are disjoint and their union is $S$. There is also a cost function ...
0
votes
0answers
26 views

labeled multicut editing problem

I am interested in the following problem: Input: An undirected edge-labeled graph $G=(V,E,w)$ with $w:E\mapsto \Sigma$, for some finite set of labels $\Sigma$, a set of source-sink pairs ...
1
vote
1answer
48 views

Approximations for the Stable Fixtures Problem

I have a set of N items, each with a subset of those items they can be paired with; each pair has a weight. I'd like to choose pairs to maximize the total weight, subject to each item being in at ...
3
votes
0answers
55 views

Trying to understand a paper on ksvd algorithm (dictionary learning) by Elad, et al

Trying to understand a paper titled KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation by M.Elad, et al; my take of section IV.C. detailed description of KSVD, is ...
10
votes
2answers
156 views

The complexity of finding a Borsuk-Ulam point

The Borsuk-Ulam theorem says that for every continuous odd function $g$ from an n-sphere into Euclidean n-space, there is a point $x_0$ such that $g(x_0)=0$. Simmons and Su (2002) describe a method ...
3
votes
1answer
208 views

Constrained version of vertex cover in a bipartite graph

Let $G(V_1, V_2, E)$ be a bipartite graph such that degree of all the vertices in $V_1$ is bounded by some constant (say) $d$. Now, for given two positive integer $l$ and $k$, we wish to decide if ...
1
vote
0answers
19 views

Which matrix of Q values is being used here?

This question refers to this paper: Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task In section 2.1, equations (5) and (6), I am wondering which Q values are ...
4
votes
1answer
67 views

Approximate matching in table of integer vectors

Disclaimer: This is my first question on cstheory.stackexchange.com so please be forgiving. I have a list of M (M is big, more than 1 million elements) vectors of integers. Each vector can contain ...
2
votes
0answers
47 views

Is there any exsiting research on this kind of “sorting with constraint” problem?

I have been interested in this kind of "sorting with constraint" problem: Given $n$ items $\{S_1 ,S_2 ,...S_n\}$ with corresponding weight $w_i ,i=1,2,...,n$, we want to sort these $n$ items (i.e. ...
1
vote
0answers
73 views

“conservative approximate Set Cover”?

We are given a lattice graph $L$, embedded on the plane, and a certain "shape" (a connected, acyclic subgraph $S$ of $L$). The task is to approximately cover $L$ with translated, rotated and flipped ...
4
votes
2answers
208 views

What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?

What are some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems, especially any linear programs which had helped in getting good ...
0
votes
0answers
37 views

How dependent is complexity of trigonometric functions on the size of inputs, not just precision?

In https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Elementary_functions, computational complexity of computing trigonometric functions of type $\sin x$ to $n$-digit ...
2
votes
0answers
80 views

An algorithm to compute sine and cosine within $n$-digit precision

I know CORDIC, but is there a better algorithm to compute $\sin x$ and $\cos x$ within specified $n$-digit accuracy?
5
votes
0answers
141 views

Statistical Algorithms vs Convex Relaxations - Planted Clique

I am trying to understand exactly what the lower bounds for the query complexity of statistical algorithms imply for convex relaxations for the planted clique problem ? A recent paper by Feldman, ...
1
vote
0answers
95 views

Difficult On Average Cases for 3MaxSAT and 3SAT Approximation Algorithm

1.Its known that a polynomial time approximation algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP. 2.Its also experimentally known that 3SAT has the most difficult known cases when the ...
2
votes
1answer
92 views

Coreset and VC dimension

I am trying to understand the notion of $\epsilon$-coreset and its relation with sampling bounds of a range space having a finite VC-dimension. Although both of them give an $\epsilon$-approximation ...
11
votes
0answers
241 views

How good is greedy in average?

Given a family ${\cal F}\subset 2^E$ of (feasible solutions), the maximization problem on ${\cal F}$ is, for every weighting $x:E\to \{0,1,\ldots\}$ of ground elements, to compute the maximum weight ...
14
votes
2answers
1k views

What is known about this TSP variant?

This question was previously posted to Computer Science Stack Exchange here. Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've ...
4
votes
1answer
225 views

Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization?

First of all, I want to make clear that my question is about algorithms. I'd like to know if there are any algorithms with provable guarantees in the context of manifold learning (or manifold ...
6
votes
1answer
210 views

Approximating the clique size of the graph

Let $G=(V,E)$ be a graph. For a given $\rho \leq |V|$ and $\epsilon$ with $(0<\epsilon<1)$, is there any sublinear query algorithm known/possible to decide if the graph has a clique of size ...
1
vote
0answers
48 views

3D Bin Packing with one bin with infinite/unknown size

Hi I'm looking for a variation of the Orthogonal 3D-BinPacking algorithm with only one bin of unknown size. I have a set $S$ of $n$ cuboids items $i_j$ with $j=1...n$. The dimensions of the items are ...
0
votes
1answer
126 views

What is the intuition behind “hardness of approximation”? [closed]

I am reading a paper about graph matching problem. Which is, to some extent, an optimization version of the graph isomorphism problem. To my surprise, some closely related NP-hard problems are quite ...
3
votes
0answers
117 views

Exactly solvable but non-trivial integrality gap

Are there interesting polynomial time solvable problems that we know of for which the natural convex relaxation has a non-trivial integrality gap? Note: Maximum matching doesn't qualify because I ...
1
vote
1answer
234 views

What are multiple rounds of SOS/Lasserre hierarchy?

Is that the same as saying the one will try to generate a higher-degree "pseudo expectation functional" by solving a SOS-program ? Or is there a difference between the two things? Or to take a ...
1
vote
1answer
249 views

The Goemans-Williamson algorithm in the $SOS$ framework

If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, ...
1
vote
1answer
189 views

Evaluating the expected value of negatively correlated random variables

A polynomial random process satisfying the following properties converts a fractional point $(x_1, x_2, \ldots, x_n) \in \mathcal{P}$, $(x_i \in [0,1])$ to a random integer point $(X_1, X_2, \ldots, ...
5
votes
0answers
155 views

Is MAX-SAT SETH (like) hard?

If we make a random assignment to the variables in $k$-sat ($m$ clauses), we are going to satisfy $(1-2^{-k})m$ clauses in expectation. In general satisfying fewer clauses is considered easy. There ...
7
votes
1answer
275 views

Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics). I am particularly ...
3
votes
1answer
118 views

Set cover in which some pairs of sets are forbidden

I'm trying to find an approximation algorithm for a variant of the weighted set cover problem. However, this variation doesn't seem to let me apply the traditional set cover arguments for an ...
3
votes
0answers
63 views

Multiple knapsack fpt?

It was an open question whether multiple knapsack is fpt wrt standard parameter. Since at SODA 2009 Jansen has presented an EPTAS for multiple knapsack and an EPTAS implies the existense of an fpt ...
3
votes
1answer
411 views

Algorithms for computing the minimal vertex separator of a graph

Background: Let $u,v$ be two vertices of an undirected graph $G=(V,E)$. A vertex set $S\subseteq V$ is a $u,v$-separator if $u$ and $v$ belong to different connected components of $G−S$. If no proper ...
0
votes
1answer
247 views

NP-complete problems with optimal approximation in poly-time

I'm looking for examples of hard optimization problems, for which we have an optimal approximation (not that this is not the same as $PTAS$, as we require a completely tight approximation, and not ...
2
votes
0answers
70 views

$\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ problems

All the problems which are either $\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ cannot admit a $\mathsf{PTAS}$, unless $P=NP$. I would like to know whether $\mathsf{MaxSNP}$ ...
0
votes
0answers
131 views

Steiner Tree and minimum spanning tree

If I must connect: $$2^k$$ terminals in a Steiner Tree choosen randomly and connect them with the cheapest component; "loss - contracting algorithm" is a good way? Or is an "Iterative Randomized ...
0
votes
0answers
71 views

Approximation Algorithm for TSP-like problem

Suppose we are given a graph with distances for each of the edges and merit for each of the nodes. What are the best (approximation) algorithms for computing the the most meritorious simple path with ...