The tag has no wiki summary.

learn more… | top users | synonyms

-1
votes
0answers
12 views

determing the max flow with only edge capacities from n/w with additional vertex capacities?

Let ((V, E); s, t; c) be an extended flow network where not only edge capacities, but also vertex capacities are constrained, i. e., c : E ∪ V → R^ + 0 and a flow f : E → R^ + 0 must satisfy, in ...
5
votes
1answer
57 views

What is the state of the art research in analysing algorithms on GPU architectures?

I have found many papers on sequential algorithms that have been implemented and tested on GPU architectures. Each of these papers usually as a result contains the amount of speedup that was achieved ...
1
vote
0answers
44 views

Bounding the cost of an approximation algorithm when subtraction involve [closed]

Given an algorithm with approximation ratio $\alpha$, and another algorithm with approximation ratio $\beta=n^\epsilon$, and a solution to a problem with cost $c$. What is the standard way to bound ...
21
votes
3answers
828 views

Using Kolmogorov complexity as input “size”

Say we have a computational problem, e.g. 3-SAT, that has a set of problem instances (possible inputs) $S$. Normally in the analysis of algorithms or computational complexity theory, we have some ...
1
vote
1answer
232 views

What are good conferences for algorithms about finite automata?

I am writing a research paper, which describes some properties about finite automata. It also provides a couple of algorithms that can measure some aspects of the properties. Could you point out some ...
13
votes
1answer
292 views

Polynomial speedups with algorithms based on semidefinite programming

This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time. I am still puzzling over the actual running time of algorithms that compute the solution of ...
2
votes
0answers
452 views

Tricky big-O calculation

I have a recursive algorithm in which the time for each step depends on the time for smaller steps. Essentially a structure is built at steps 1, 2, ..., n which must be searched at larger heights: $$ ...