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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: $$ ...