Questions tagged [approximation-algorithms]
Questions about approximation algorithms.
513
questions
5
votes
0
answers
211
views
On permanent of $\{\pm1,0\}$ matrices
Consider the problem of computing the permanent $Per(M)$ of a matrix $M\in\{0,-1,1\}^{n\times n}$ such that the result is bounded in absolute value, $|Per(M)|<B$ where $B$ is part of input.
Is ...
- 12.8k
3
votes
1
answer
242
views
Compression algorithms for low-complexity strings?
Let $s$ denote a string over a finite alphabet, $n_s = |s|$ be the length of $s$, and $n_s^{*}$ denote the minimum description size of $s$ under a given computational model (TM, CFG, etc.). Are there ...
- 35
3
votes
3
answers
184
views
Approaches for Theoretical Analysis of Estimates of Probability Distributions
Consider that you have a probability distribution p of some quantity X and you have obtained (via some algorithm) an estimate q of p according to some definition of closeness. Are there methods/papers ...
1
vote
0
answers
281
views
Maximize the weight of MST + sum of vertex weights
I am considering a problem where the goal is to choose a subset of size $k$ of the vertices in a graph, such that the weight of their minimum spanning tree + the sum of their vertex weights is ...
- 19
3
votes
0
answers
132
views
Given a matrix $A$ maximize the number of positive elements in $Ax$ under specific constraints for $x$
Let $A = [a_{ij}]$ be a symmetric matrix with nonnegative values and $k << n/2$ a given constant. We want to rearrange the columns of the matrix such that the number of rows with the following ...
- 31
7
votes
0
answers
266
views
Positive cut algorithm on bipartite graphs with negative weights
Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If ...
- 71
1
vote
0
answers
123
views
Truthful posted-price mechanism with optimal efficiency (social welfare)
I am interested in mechanism design. In the paper On Profit-Maximizing Envy-free Pricing, SODA, 2005, the authors provided a truthful competitive posted-price mechanism with $4\log h$ guarantee of ...
- 11
3
votes
0
answers
145
views
Maximize number of edges covered by an independent set of vertices
Smallest vertex cover which is also an independent set asks about finding an independent set that covers all edges. This problem is known as the independent vertex cover problem and is equivalent to ...
- 373
1
vote
0
answers
161
views
Algorithms to approximate a Riemann integrable function by a piecewise constant function
We know that any general function that is Riemann integrable can be approximated to arbitrary precision by piecewise constant functions. So in this regard, I was looking for references on algorithms (...
6
votes
2
answers
381
views
Finding smallest context free grammar that generates a set of sets
Are there any results known about the size of smallest context free grammar that generates a set of sets?
That is, I am given an alphabet $\Sigma$ as well as a set $S \subseteq \mathbb{P}(\Sigma)$ ...
- 338
3
votes
0
answers
380
views
Approximating the VM packing problem
In the wikipedia article on bin-packing it is stated that
A variant of bin packing that occurs in practice is when items can share space when packed into a bin. Specifically, a set of items could ...
- 1,096
3
votes
1
answer
121
views
Density of multiples
I have an infinite collection of positive integers $n_1,n_2,n_3,\ldots$ and I would like to find the density of the numbers divisible by one or more of these.* If the density does not exist, the ...
- 1,737
6
votes
1
answer
162
views
Brute force search algorithm for semidefinite programming (representation of spectrahedron)
I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for ...
- 451
-1
votes
1
answer
197
views
Given oracle for Max-3SAT compute clauses that cannot be satisfied
We know that Max-3SAT is NP-hard to compute exactly (and also hard to approximate to a particular constant multiplicative factor). However, suppose you are given an oracle for Max-3SAT that tells you ...
- 87
0
votes
1
answer
282
views
Online/approximate weighted and capacitated bipartite matching
I wish to take a look at online/approximate weighted and capacitated bipartite matching problem.
Consider $G=\{L\cup R, E\}$, $|L|=n_1$, $|R|=n_2$, $|E|=m$ and $E\subseteq L\times R$. For each $r_i\...
- 119
7
votes
1
answer
927
views
Ordering of a DAG minimizing some definition of cost
Consider a DAG $(V,A)$ with a topological ordering $(v_1,v_2,\ldots,v_n)$. I define the cost of this ordering as the maximum over all $1\leq i\leq n$ of $|\{j\leq i
\mid \exists k>i: (v_j,v_k)\in A\...
- 251
5
votes
2
answers
196
views
Solution/Hardness of the following (integer) budgeted problem?
I have no idea how to solve the following INTEGER problem or prove its hardness. Thanks for any help/comment/open discussion!
Assume there are $N$ startups. For each startup $i$, you can invest $x_i\...
- 119
1
vote
0
answers
112
views
algorithms for a large submatrix / general factor / quasi-biclique problem?
Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that ...
- 145
3
votes
1
answer
429
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 ...
- 115
1
vote
0
answers
105
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 ...
- 111
2
votes
0
answers
127
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 ...
- 729
2
votes
1
answer
1k
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 non-...
- 21
2
votes
1
answer
1k
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 ...
5
votes
0
answers
214
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}$ ...
- 143
2
votes
0
answers
97
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 $n$...
- 644
5
votes
1
answer
151
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 ...
- 51
2
votes
0
answers
45
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 ...
- 131
4
votes
1
answer
2k
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 ...
- 7,595
3
votes
2
answers
564
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 ...
- 3,243
5
votes
0
answers
247
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
0
answers
122
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 ...
- 11
3
votes
1
answer
446
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, ...
- 175
5
votes
1
answer
1k
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 ...
- 2,143
15
votes
0
answers
388
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,950
3
votes
0
answers
141
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., $A_1(...
- 338
3
votes
1
answer
252
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 (\mathbb{Z}^...
- 373
1
vote
0
answers
93
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 ...
- 119
3
votes
1
answer
509
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 ...
- 371
1
vote
0
answers
416
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$, $d(...
- 451
4
votes
1
answer
358
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 ...
- 1,224
0
votes
0
answers
33
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 ...
- 650
0
votes
0
answers
132
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 ...
- 101
1
vote
1
answer
107
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 ...
- 113
7
votes
1
answer
323
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 ...
- 133
10
votes
2
answers
349
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 ...
- 2,086
4
votes
1
answer
725
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 ...
- 639
1
vote
0
answers
27
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 ...
- 51
4
votes
1
answer
96
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 0-...
- 141
2
votes
0
answers
55
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. ...
- 439
1
vote
0
answers
83
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 ...
- 131