Questions tagged [approximation-algorithms]
Questions about approximation algorithms.
544 questions
2
votes
1
answer
113
views
Nontrivial algorithms for planar #P-complete problems
For general #P-complete problems, hashing-based approximate counting based on Stockmeyer's algorithm can provide a significant speedup over naive exhaustive enumeration (at least in practice). On the ...
- 1,074
1
vote
0
answers
50
views
Budgeted maximum coverage with integer weights
In the budgeted maximum coverage problem, we have a collection of sets with weights. The goal is to find a collection of sets whose total weight does not exceed some given budget L. One can also ...
3
votes
1
answer
245
views
Faster dimensionality reduction
The Johnson–Lindenstrauss lemma says that if we have $n$ points in $\mathbb{R}^d$ and if $k=\Theta(\log n)$ and if we choose the $k \times d$ matrix $A$ randomly from some appropriate distribution, ...
- 12.8k
1
vote
1
answer
125
views
Problem on a Directed Graph subcase of load time scheduling
I have the following graph optimization problem. In a directed graph G, each node $v$
is assigned a number $n(v)$ which is initially 0. At any time, I can make a move to assign the number $ max \{ n(...
- 358
2
votes
0
answers
77
views
Looking for survey/reference for hardness of approximation
Looking for a survey for hardness of approximation. I found this https://arxiv.org/abs/cs/0409043 but I'm hoping to find something more extensive.
- 358
4
votes
0
answers
163
views
Trying to find source for there is no PTAS for binary SCS
I'm trying to find a proof that there is no PTAS for binary Shortest common supersequence.
I know there is a paper here P. Bonizzoni, M. Duella and G. Mauri. Approximation complexity of longest common ...
- 358
8
votes
0
answers
220
views
Is there a theory of approximate dynamic programming?
By which I mean for problems which can be solved perfectly by dynamic programming but instead of computing all necessary subproblems you only compute a subset and each entry of the DP table that you ...
- 358
0
votes
1
answer
163
views
Truncated arithmetic with promise
Problem: Top two bits of arithmetic expression $ab+cd$ with promise
Input: Four $n$-bit integers $a, b, c, d$
Promise: $ab+cd<2^{2n}$ or $ab+cd \geq 2^{2n} + 2^{2n-1}$
Output: Whether $ab+cd<2^{...
- 1,074
3
votes
0
answers
87
views
Linear space approximation algorithm for string problems solvable by dynamic programming
I am looking for literatures about hardness or upper bound of approximation algorithms, using only linear space, for string related problems, which can be solved by dynamic programming in super linear ...
1
vote
0
answers
76
views
Random Constraint Satisfiability Problems without spin-glass structure
Many random constraint satisfiability problems can be mapped to spin-glass models. For example, finding solutions that maximally satisfy random MAX3XORSAT instances corresponds to finding near-ground-...
- 11
0
votes
0
answers
41
views
Do Approximate Equilibria Algorithms for Transit Frequency Games Exhibit Strong Logarithmic Efficiency in Large Networks?
In large-scale urban transit networks such as Gush Dan (Israel), with ~6,000 stops and dozens of competing operators (e.g., Egged, Dan, Metropoline), public transportation planning can be naturally ...
1
vote
1
answer
165
views
Confusion about PCP theorem and the soundness constant
I am studying the PCP theorem through different resources and I am a bit confused
First of all, why the soundness constant in the original proof is 1/2? If I understood well, for the one-sided ...
- 13
1
vote
1
answer
191
views
Bounding expected weight in a stochastic selection process with adaptive adversarial deletions
I am analyzing the following stochastic process, with the present of an adaptive adversary. Despite searching through several textbooks and lecture notes on randomized algorithms and adversarial ...
0
votes
0
answers
63
views
best size-approximation for non-metric k-Medians?
Question
What poly-time $O(\log n)$-size-approximation algorithms are known for the non-metric $k$-Median problem?
That is, algorithms that
open a set of $O(k\log n)$ centers,
having assignment cost ...
- 12.2k
3
votes
1
answer
174
views
Greedy algorithm for Tree Augmentation
The Tree Augmentation Problem is a special case of set cover where the ground set is the edges of a tree $T = (V,E)$, and the sets are edge-subpaths of $T$. The paths are usually called links.
There ...
- 701