Questions about approximation algorithms.

learn more… | top users | synonyms

-2
votes
0answers
54 views

incremental knapsack

Is there a way to compute the knapsack problem incrementally? Any approximation algorithm? I am trying to solve the problem in the following scenario. Let D be my data set which is not ordered and ...
1
vote
1answer
88 views

How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?

I have these two problems: Problem 1 (Dual bin packing problem) Instance: A set of $n$ items where each item $i$ has weight $w_i$. A set of $k$ bins where each bin has capacity $W$. Question: Find ...
1
vote
0answers
64 views

Percolation probabilities

I have a finite undirected graph with a probability $p_e$ given for each edge $e$. This gives a random graph by removing each edge e with probability $1-p_e$ independently of the others. I'm ...
3
votes
0answers
116 views

Weighted $l_1$ distance

So there are many well known algorithms for approximate nearest neighbor on the $\ell_1$ distance. My question is, what about the weighted version of the problem (where the weights are specified along ...
0
votes
1answer
73 views

Max-sum graph-partition for maximizing intra-edge weights?

I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results. Input: A graph G with negative or ...
3
votes
1answer
137 views

Partial cover approximation

We have a set of elements $E=\{e_1, e_2, \ldots, e_m\}$, and $n$ subsets of $E$: $S_1, S_2, \ldots, S_n$ The union of those subsets is $E$, and each subset $S_i$ has a non-negative weight $w_i$. The ...
3
votes
0answers
101 views

Fast Approximation Algorithms for Covering Design

The covering design problem is as follows: We are given a universe $\mathcal{U}$ of size $n$. By $C(n,k,l)$ we denote the smallest cardinality of any set system $\mathcal{A} \subset 2^\mathcal{U}$ ...
1
vote
0answers
70 views

About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube

Naively, in my very limited awareness, it feels that the Max-CUT is a very "special" NP-Hard problem because for a graph with edge-set $E$, it can be written as the question of trying to maximize a ...
0
votes
0answers
40 views

Thresholding technique for Bottleneck Optimization Problems like k-centre, k-suppliers etc

There is a well know thresholding techniques (introduced by Hochbaum and Shmoys in [1]) for bottleneck optimization problems which preprocesses the instance which is a graph whose edges satisfy the ...
6
votes
1answer
125 views

Does k-PATH admit a constant approximation?

In the $k$-PATH problem, we receive as input a graph $G$ and an integer $k$. The goal is to decide whether there exists a simple path of length $k$ in $G$. A $\alpha$-approximation for $k$-PATH is an ...
2
votes
0answers
23 views

Stochastic optimization with erroneous oracles

I am interested in a class of optimization problems of which we know that the input variable is first subjected to noise $\xi$ before entering the data-producing process $f$. I write the objective in ...
5
votes
1answer
126 views

Maximizing a monotone supermodular function s.t. cardinality

I've tried to comb the literature and seen a lot of references to results that almost but don't quite seem to address this. Question: Is it known to be true or is there a hardness result ...
0
votes
0answers
87 views

An approximate optimization algorithm

Let $f(n)$ be the number of bits for representing natural number $n$: $f(n) = \lfloor \lg n + 1 \rfloor$. I am looking for an efficient algorithm for the following problem: Input: $w_1, w_2, \cdots, ...
1
vote
2answers
255 views

Quantum complexity of maximum inner product search

Given two matrices $X \in \mathbb{R}^{m \times k}$, $Y \in \mathbb{R}^{n \times k}$, maximum inner product search (MIPS) asks for the largest $l$ entries of $X Y^T$. Typically $k \ll m, n$ (many ...
5
votes
0answers
230 views

Maximizing the number of selected edges with opposing requirements

Consider the following problem: Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$. Output: a subset of vertices $W$ of size $k$ which maximizes the ...
1
vote
0answers
76 views

L-reduction From Matrix-Tiling To Minimal Dominating Set in Unit Disk Graph

Recently I read this paper which was published in FOCS2007. In section 4, just before Theorem 4.2, the author mentioned that the gadget construction of Minimum Dominating Set in UDG is similar to ...
1
vote
0answers
75 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
172 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
142 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
316 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
117 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
46 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
188 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
72 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
194 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
92 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
38 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
128 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
31 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
74 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
51 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 ...
4
votes
0answers
66 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
159 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
217 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
20 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
71 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 ...
5
votes
2answers
218 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
44 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
85 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
143 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
98 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
105 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
249 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
230 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
213 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 ...