Find link

language:

Find link is a tool written by Edward Betts.

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

alternate case: strongly-polynomial time

Fulkerson Prize (1,965 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

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

List of unsolved problems in computer science (1,168 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

Alexander Schrijver (941 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, Series B 80 (2): 346–355, 2000

Submodular set function (3,349 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,976 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,141 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. 80 (2): 346–355. doi:10.1006/jctb

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

Efficient approximately fair item allocation (5,471 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

Matroid intersection (1,718 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 |

Assignment problem (2,961 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 ⁡

Entitlement (fair division) (2,058 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,420 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),

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)

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

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

Fair allocation of items and money (3,957 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,200 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