Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
633 questions
0
votes
1
answer
69
views
Ordered-Scheduling Approximation Algorithm for Load Balancing and Proof
Given a list of $n$ jobs to be executed on $m$ identical machines, the load balancing problem is to distribute the $n$ jobs over the $m$ machines, such that the makespan is minimised. The makespan is ...
- 71
0
votes
1
answer
85
views
Best mutations for Simulated Annealing on real graph
Here’s what I’m working on: I want to build routes that maximize my custom metrics. I don’t want to share the exact details of these metrics, but for every candidate route I calculate N metrics and I’...
- 1
1
vote
1
answer
77
views
Randomised Algorithm for Maximum Matching
Consider the following randomised distributed algorithm for computing (constant-approximation) maximum matching. The algorithm
has $\log ∆$ iterations indexed by $i∈{0,1,2,\ldots,\log ∆−
1}$. We ...
- 21
0
votes
0
answers
72
views
Hardness of approximation for complexity class $\mathsf{MA}$
Under the derandomization assumption $\mathsf{MA=NP}$, one can obtain the hardness of approximation result for the class $\mathsf{MA}$. (Note: By invoking the PCP theorem.)
Has there been another way/...
- 189
1
vote
0
answers
45
views
More Precise Interval Analysis
I am building an inference engine that uses interval analysis to compute variable bounds. Efficiency is very important in my case:
I cannot use SMT solvers
I cannot afford full enumeration, since ...
- 11
3
votes
1
answer
401
views
Finding the solution to an equation closest to an arbitrary state
There are a number of numerical methods for finding a solution to an equation that is usually close to the initial guess, but not always the closest. Is there an algorithm that will always find the ...
1
vote
1
answer
101
views
Convex Programming in FPTAS?
Let us consider a very simple convex program of the form
$$\mathsf{opt} = \inf_{\substack{Ax = b\\Cx\leq d}} f(x)$$
where $x\in\mathbb{R}^n$, $f$ is a (smooth enough) convex function, and $A$, $C$ are ...
- 178
2
votes
0
answers
125
views
The problem of reachability in a directed graph, but all predecessors must be reached to reach a node
Let $S$ be a set of nodes belonging to a directed graph $G = (V,E)$. A vertex $v$ of $G$ is said to be reachable from $S$ if and only if $v \in S$, or if each predecessor of $v$ is reachable from $S$ ...
0
votes
0
answers
76
views
Graham's Greedy Algorithm is optimal for (2m) machines
I am reading up on Graham's algorithm and want to prove it's $4/3 - 1/(3m)$ optimality.
To do that, we need to prove that if $j$ is the last job assigned to the most heavily loaded machine in the ...
- 71
2
votes
1
answer
109
views
Approximation algorithm for a problem similar to load balancing
This's exercise $7$ of chp $11$ from the popular book algorithm design by Jon and Eva. It's about designing a $2$-approximation algorithm for a problem similar to Load balancing on parallel machine. ...
- 225
1
vote
0
answers
109
views
Inapproximability of Maximum Independent Set
Lemma1. There exists a polynomial time computable transformation $f$ from the 3CNF formulas to graphs such that for every 3CNF formula $\varphi$, $f(\varphi)$ is an $n$-vertex graph whose $|MIS| = \...
- 73
7
votes
2
answers
3k
views
Numerical methods: why doesn't this python code return 1.0?
I typed the following into the python console:
...
- 71
2
votes
0
answers
38
views
Isolated cut points for probabilistic automata
I have a basic question on a point of the famous paper by Rabin (1963) about probabilistic automata. Therein it’s explained the reason why the notion of isolated cut point is natural.
In the remark of ...
- 21
1
vote
1
answer
136
views
Knapsack with both upper and lower capacity
In the usual knapsack problem, there are $n$ items with values $v_1,\ldots,v_n$ and costs $c_1,\ldots,c_n$ and a total budget $B$, and the goal is to select a subset of items with maximum total value ...
- 6,087
2
votes
0
answers
47
views
Is spanner a subgraph?
I've recently came across Spanners and Emulators, which seem to be pretty much the same thing, apart from whether or not the approximation is multiplicative or additive. However, I saw that a $k$-...
- 535