Find link

language:

Find link is a tool written by Edward Betts.

searching for Strongly-polynomial time 18 found (29 total)

alternate case: strongly-polynomial time

Fulkerson Prize (1,854 words) [view diff] no match in snippet view article find links to article

degree. 1988: Éva Tardos for finding minimum cost circulations in strongly polynomial time. Narendra Karmarkar for Karmarkar's algorithm for linear programming

List of unsolved problems in computer science (694 words) [view diff] no match in snippet view article find links to article

identity testing be derandomized? Does linear programming admit a strongly polynomial-time algorithm? (This is problem #9 in Smale's list of problems.) How

Fractional Pareto efficiency (3,158 words) [view diff] exact match in snippet view article find links to article

and m objects with mixed (positive and negative) valuations, in strongly-polynomial time, using O(n2 m2 (n+m)) operations. Moreover, in the computed allocation

Submodular set function (3,284 words) [view diff] exact match in snippet view article find links to article

submodular function is computable in polynomial time, and even in strongly-polynomial time. Computing the minimum cut in a graph is a special case of this

Proportional item allocation (1,962 words) [view diff] no match in snippet view article find links to article

algorithm finding a PE+PROP1 allocation of chores. The algorithm is strongly-polynomial-time if either the number of objects or the number of agents (or both)

Pseudo-Boolean function (1,139 words) [view diff] no match in snippet view article find links to article

"A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time". Journal of Combinatorial Theory. B. 80 (2): 346–355. doi:10.1006/jctb

Smale's problems (786 words) [view diff] exact match in snippet view article find links to article

are provided as well. 9th The linear programming problem: Find a strongly-polynomial time algorithm which for given matrix A ∈ Rm×n and b ∈ Rm decides whether

Assignment problem (2,524 words) [view diff] exact match in snippet view article find links to article

problem in O ( m s + s 2 log ⁡ r ) {\displaystyle O(ms+s^{2}\log r)} strongly-polynomial time. In particular, if s=r then the runtime is O ( m r + r 2 log ⁡

Efficient approximately fair item allocation (5,444 words) [view diff] no match in snippet view article find links to article

guarantees PE, PROP1, and a 2-approximation to the max product, in strongly polynomial time. Caragiannis, Gravin and Huang present an algorithm that guarantees

Voltage graph (1,060 words) [view diff] no match in snippet view article find links to article

(1987), Example 2.1.2, p.58. Cohen, Edith; Megiddo, Nimrod (1989), "Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs", Proc

Matroid intersection (1,692 words) [view diff] no match in snippet view article find links to article

parallel computing model. Bérczi, Király, Yamaguchi and Yokoi present strongly polynomial-time algorithms for weighted matroid intersection using more restricted

Fractional matching (1,424 words) [view diff] exact match in snippet view article find links to article

fractions) can be found by linear programming. There is also a strongly-polynomial time algorithm, using augmenting paths, that runs in time O ( | V |

Entitlement (fair division) (2,290 words) [view diff] no match in snippet view article

3/5-fraction of the APS. Aziz, Moulin and Sandomirskiy present a strongly polynomial time algorithm that always finds a Pareto-optimal and WPROP(0,1) allocation

Turing machine (9,581 words) [view diff] no match in snippet view article find links to article

polynomial-time in the Turing model. Such an algorithm is said to run in strongly polynomial time. Robin Gandy (1919–1995)—a student of Alan Turing (1912–1954),

Congestion game (7,421 words) [view diff] exact match in snippet view article find links to article

assumptions, a Nash equilibirum in such a game can be approximated in strongly-polynomial time. If the strategies can be general subsets, or the players may have

Richard W. Cottle (1,885 words) [view diff] no match in snippet view article find links to article

Adler, Richard W. Cottle, Jong-Shi Pang: Some LCPs solvable in strongly polynomial time with Lemke's algorithm. Math. Program. 160(1-2): 477-493 (2016)

Fair allocation of items and money (3,950 words) [view diff] no match in snippet view article find links to article

cycles. An envy-free price with minimum subsidy can be computed in strongly polynomial time, by constructing the weighted envy-graph and giving, to each agent

Maximin share (11,167 words) [view diff] no match in snippet view article find links to article

MMS, which does not need to know the MMS value, and thus runs in strongly polynomial time. A proof of existence of ( 3 4 + 1 12 n ) {\displaystyle ({\frac