Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Minimax approximation algorithm (view), Parameterized approximation algorithm (view)

searching for Approximation algorithm 104 found (317 total)

K-means++ (1,403 words) [view diff] exact match in snippet view article find links to article

proposed in 2007 by David Arthur and Sergei Vassilvitskii, as an approximation algorithm for the NP-hard k-means problem—a way of avoiding the sometimes

Degree-constrained spanning tree (374 words) [view diff] no match in snippet view article find links to article

In graph theory, a degree-constrained spanning tree is a spanning tree where the maximum vertex degree is limited to a certain constant k. The degree-constrained

Generalized assignment problem (1,054 words) [view diff] exact match in snippet view article find links to article

knapsack problem into an approximation algorithm for the GAP. Using any α {\displaystyle \alpha } -approximation algorithm ALG for the knapsack problem

Kinodynamic planning (305 words) [view diff] exact match in snippet view article find links to article

(PTAS) for the problem. By providing a provably polynomial-time ε-approximation algorithm, they resolved a long-standing open problem in optimal control

Egalitarian item allocation (2,969 words) [view diff] exact match in snippet view article find links to article

{n}}})} -approximation algorithm, based on rounding a linear program. Feige proved that a polynomial-time constant-factor approximation algorithm exists

Necklace splitting problem (1,764 words) [view diff] exact match in snippet view article find links to article

of n(k − 1) hyperplanes parallel to the sides for k thieves. An approximation algorithm for splitting a necklace can be derived from an algorithm for consensus

Optimal binary search tree (2,965 words) [view diff] no match in snippet view article find links to article

In computer science, an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree, is a binary search tree which provides

Alexander Zelikovsky (72 words) [view diff] exact match in snippet view article find links to article

computer science at Georgia State University. He is known for an approximation algorithm for the minimum Steiner tree problem with an approximation ratio

Exact algorithm (127 words) [view diff] exact match in snippet view article find links to article

problems with some constant-factor approximation algorithm Heuristic algorithm PTAS - a type of approximation algorithm that takes the approximation ratio

LaplacesDemon (414 words) [view diff] exact match in snippet view article find links to article

their own model specification function and selects a numerical approximation algorithm to update their Bayesian model. Some numerical approximation families

Benson's algorithm (370 words) [view diff] case mismatch in snippet view article find links to article

bensolve.org Inner Link to github Harold P. Benson (1998). "An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set

Polygon covering (2,229 words) [view diff] exact match in snippet view article find links to article

time O(n2), where n is the number of vertices of the polygon. An approximation algorithm which gives good empirical results on real-life data is presented

Graph partition (2,979 words) [view diff] exact match in snippet view article find links to article

a maximum of (1 + ε)·(n/k) nodes. We compare the cost of this approximation algorithm to the cost of a (k,1) cut, wherein each of the k components must

Teofilo F. Gonzalez (347 words) [view diff] exact match in snippet view article find links to article

hardness of approximation;[SG76] for his sub-linear and best possible approximation algorithm (unless P = NP) based on the farthest-first traversal for the metric

Parallel task scheduling (2,520 words) [view diff] exact match in snippet view article find links to article

back to 1960. For this problem, there exists no polynomial time approximation algorithm with a ratio smaller than 3 / 2 {\displaystyle 3/2} unless P =

Philip N. Klein (638 words) [view diff] exact match in snippet view article find links to article

Klein and his then-students Ajit Agrawal and R. Ravi gave an approximation algorithm for network design that is considered "the first highly sophisticated

Feedback vertex set (1,805 words) [view diff] exact match in snippet view article find links to article

Existing constant-factor approximation algorithms. The best known approximation algorithm on undirected graphs is by a factor of two. By contrast, the directed

Covering problems (938 words) [view diff] exact match in snippet view article find links to article

problem admits an r-approximation algorithm, then the conflict-free geometric cover problem admits a similar approximation algorithm in FPT time. Vazirani

Welfare maximization (2,835 words) [view diff] exact match in snippet view article find links to article

/ ( 2 n − 1 ) {\displaystyle n/(2n-1)} -approximation algorithm, and an (1-1/e)≈0.632-approximation algorithm for the special case in which the agents'

Simultaneous perturbation stochastic approximation (1,555 words) [view diff] exact match in snippet view article find links to article

systems with multiple unknown parameters. It is a type of stochastic approximation algorithm. As an optimization method, it is appropriately suited to large-scale

Matching pursuit (2,181 words) [view diff] exact match in snippet view article find links to article

Matching pursuit (MP) is a sparse approximation algorithm which finds the "best matching" projections of multidimensional data onto the span of an over-complete

Matroid-constrained number partitioning (974 words) [view diff] exact match in snippet view article find links to article

an approximation algorithm for minimizing (max,sum) with general matroid constraints. Abbassi, Mirrokni and Thakur present an approximation algorithm for

Simmons–Su protocols (2,087 words) [view diff] exact match in snippet view article find links to article

Hence, an approximation algorithm is the best that we can hope for in finite time. Currently, Simmons' algorithm is the only approximation algorithm for envy-free

András Sebő (563 words) [view diff] exact match in snippet view article find links to article

Combinatorial Optimization. In 2012, Sebő and Jens Vygen developed a 7/5-approximation algorithm for the graph version of the traveling salesman problem; currently

Unrelated-machines scheduling (1,846 words) [view diff] exact match in snippet view article find links to article

case. Lenstra, Shmoys and Tardos presented a polytime 2-factor approximation algorithm, and proved that no polytime algorithm with approximation factor

Charging argument (1,759 words) [view diff] exact match in snippet view article find links to article

be used to show that the earliest finish time algorithm is a 2-approximation algorithm for the job interval scheduling problem. Let OPT(I) and EFT(I)

Balanced number partitioning (3,242 words) [view diff] exact match in snippet view article find links to article

{1}{m(k+1)}}\right)} . In particular, their 7 / 6 {\displaystyle 7/6} -approximation algorithm for triplet partitioning (k = 3) can be used to obtain a heuristic

K-anonymity (1,862 words) [view diff] exact match in snippet view article find links to article

and Agrawal (2005) often yield effective results. A practical approximation algorithm that enables solving the k-anonymization problem with an approximation

Path (graph theory) (1,175 words) [view diff] exact match in snippet view article

Guohui; Su, Bing; Xu, Yao; Zhang, An (2019-07-01). "An improved approximation algorithm for the minimum 3-path partition problem". Journal of Combinatorial

Cut (graph theory) (1,132 words) [view diff] exact match in snippet view article

bisection). The problem is known to be NP-hard, and the best known approximation algorithm is an O ( log ⁡ n ) {\displaystyle O({\sqrt {\log n}})} approximation

Michel Goemans (341 words) [view diff] exact match in snippet view article find links to article

work with David P. Williamson on the semidefinite programming approximation algorithm for the maximum cut problem. In 2012 Goemans was awarded the Farkas

Boolean satisfiability algorithm heuristics (1,721 words) [view diff] exact match in snippet view article find links to article

assigning variable values is a ⁠1/2⁠-approximation algorithm, which means that is an optimal approximation algorithm unless P = NP. Suppose we are given

Uniform-machines scheduling (1,767 words) [view diff] exact match in snippet view article find links to article

Sahni presents an exponential-time algorithm and a polynomial-time approximation algorithm for identical machines. Horowitz and Sahni presented: Exact dynamic

Daniel Brélaz (385 words) [view diff] exact match in snippet view article find links to article

afterwards taught mathematics. He is responsible for a well-known approximation algorithm for graph colouring. In 1975, he joined the Group for the Protection

Minimum degree spanning tree (341 words) [view diff] exact match in snippet view article find links to article

Krishman and B. Raghavachari (2001) have a quasi-polynomial time approximation algorithm to solve the problem for directed graphs. M. Haque, Md. R. Uddin

Multiple subset sum (1,613 words) [view diff] exact match in snippet view article find links to article

for the case in which the subset capacities are different. A 3/4-approximation algorithm which runs in time O(m2n). For max-min MSSP: With variable m: a

Grothendieck inequality (4,840 words) [view diff] exact match in snippet view article find links to article

absolute constant. This approximation algorithm uses semidefinite programming. We give a sketch of this approximation algorithm. Let B = ( b i j ) {\displaystyle

Maximum disjoint set (4,745 words) [view diff] exact match in snippet view article find links to article

presented an O ( log ⁡ log ⁡ n ) {\displaystyle O(\log {\log {n}})} -approximation algorithm to the more general setting, in which each rectangle has a weight

Utilitarian cake-cutting (2,232 words) [view diff] exact match in snippet view article find links to article

furthermore no FPTAS is possible unless P=NP. There is an 8-factor approximation algorithm, and a fixed-parameter tractable algorithm which is exponential

Herbert Robbins (946 words) [view diff] exact match in snippet view article find links to article

Robbins was also one of the inventors of the first stochastic approximation algorithm, the Robbins–Monro method, and worked on the theory of power-one

Tutte polynomial (5,377 words) [view diff] exact match in snippet view article find links to article

good approximation algorithm has been very well studied. Apart from the points that can be computed exactly in polynomial time, the only approximation algorithm

Quadratic assignment problem (773 words) [view diff] exact match in snippet view article find links to article

computation time. It was also proven that the problem does not have an approximation algorithm running in polynomial time for any (constant) factor, unless P

Bayesian network (6,630 words) [view diff] exact match in snippet view article find links to article

algorithm developed by Dagum and Luby was the first provable fast approximation algorithm to efficiently approximate probabilistic inference in Bayesian

Harold Benson (894 words) [view diff] case mismatch in snippet view article find links to article

07165.5a. S2CID 120025863. Benson, Harold P. (1998). "An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set

Demand oracle (745 words) [view diff] exact match in snippet view article find links to article

Dobzinski, Shahar; Schapira, Michael (2006-01-22). "An improved approximation algorithm for combinatorial auctions with submodular bidders". Proceedings

Envy-free pricing (2,559 words) [view diff] exact match in snippet view article find links to article

seller's revenue is APX-hard in both cases. There is a logarithmic approximation algorithm for the revenue in both cases. There are polynomial-time algorithms

Connected dominating set (1,239 words) [view diff] exact match in snippet view article find links to article

doi:10.1016/0020-0190(94)90139-2. Solis-Oba, Roberto (1998), "2-approximation algorithm for finding a spanning tree with maximum number of leaves", Proc

Betweenness problem (978 words) [view diff] exact match in snippet view article find links to article

MR 2932455, S2CID 257225. Makarychev, Yury (2012), "Simple linear time approximation algorithm for betweenness", Operations Research Letters, 40 (6): 450–452

Distributed minimum spanning tree (2,554 words) [view diff] exact match in snippet view article find links to article

minimum spanning tree. An O ( log ⁡ n ) {\displaystyle O(\log n)} -approximation algorithm was developed by Maleq Khan and Gopal Pandurangan. This algorithm

Multiplicative inverse (2,360 words) [view diff] exact match in snippet view article find links to article

given a rational number r such that 0 < r < |x|. In terms of the approximation algorithm described above, this is needed to prove that the change in y will

Treewidth (4,569 words) [view diff] exact match in snippet view article find links to article

Daniel; Pilipczuk, Michal (2016), "A c k n {\displaystyle c^{k}n} 5-approximation algorithm for treewidth", SIAM Journal on Computing, 45 (2): 317–378, arXiv:1304

Treemapping (2,184 words) [view diff] exact match in snippet view article find links to article

2010. Nagamochi, H.; Abe, Y.; Wattenberg, Martin (2007). "An approximation algorithm for dissect-ing a rectangle into rectangles with specified areas"

Machtey Award (179 words) [view diff] case mismatch in snippet view article find links to article

for Sampling Colorings" 1998 Kamal Jain (Georgia Tech) "Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem" Daniele Micciancio

MAX-3SAT (1,450 words) [view diff] case mismatch in snippet view article find links to article

MAX-3SAT, ECCC TR 03-049 (2003). W.F.de la Vega and M.Karpinski, 9/8-Approximation Algorithm for Random MAX-3SAT, ECCC TR 02-070 (2002); RAIRO-Operations Research

Sorelle Friedler (661 words) [view diff] exact match in snippet view article find links to article

2020-12-23. Friedler, Sorelle A.; Mount, David M. (2010-08-01). "Approximation algorithm for the kinetic robust K-center problem". Computational Geometry

Set packing (1,514 words) [view diff] exact match in snippet view article find links to article

ISBN 978-3-319-09174-7. S2CID 15815885. Neuwohner, Meike (2021). "An improved approximation algorithm for the maximum weight independent set problem in d-claw free graphs"

Triangle-free graph (2,524 words) [view diff] exact match in snippet view article find links to article

Halldórsson (1992) p. 184, based on an idea from an earlier coloring approximation algorithm of Avi Wigderson. Kim (1995). Erdős, Suen & Winkler (1995); Bohman

Multi-objective linear programming (1,003 words) [view diff] exact match in snippet view article find links to article

ISSN 0022-3239. S2CID 120455645. Benson, Harold P. (1998). "An outer approximation algorithm for generating all efficient extreme points in the outcome set

Planarization (1,184 words) [view diff] exact match in snippet view article find links to article

Cristina G.; Finkler, Ulrich; Karloff, Howard (1998), "A better approximation algorithm for finding planar subgraphs", Journal of Algorithms, 27 (2): 269–302

Rooted graph (1,821 words) [view diff] case mismatch in snippet view article find links to article

(PDF) on 2015-03-26 Drescher, Matthew; Vetta, Adrian (2010), "An Approximation Algorithm for the Maximum Leaf Spanning Arborescence Problem", ACM Trans

Bounding sphere (1,515 words) [view diff] exact match in snippet view article find links to article

point into the set in each iteration. Kumar et al. improved this approximation algorithm so that it runs in time O ( n d ϵ + 1 ϵ 4.5 log ⁡ 1 ϵ ) {\displaystyle

Gadget (computer science) (1,604 words) [view diff] exact match in snippet view article

programming approximation algorithms for MAX 2-SAT, they provide an approximation algorithm for MAX 3-SAT with approximation ratio 0.801, better than previously

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

than previous algorithms when W is small. They also present an approximation algorithm that finds an e-approximate solution by solving O ( ϵ − 1 log ⁡

Blocking (statistics) (2,842 words) [view diff] exact match in snippet view article

Chapman & Hall/CRC Press, London. Karmakar, Bikram (2022). "An approximation algorithm for blocking of an experimental design". Journal of the Royal Statistical

Truthful job scheduling (1,748 words) [view diff] case mismatch in snippet view article find links to article

ISBN 978-3-540-31856-9. Kovács, Annamária (2005). "Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines". In Brodal, Gerth Stølting; Leonardi

Vertex cover in hypergraphs (1,328 words) [view diff] exact match in snippet view article find links to article

then the problem of finding a minimum d-hitting set permits a d-approximation algorithm. Assuming the unique games conjecture, this is the best constant-factor

Ding-Zhu Du (887 words) [view diff] case mismatch in snippet view article find links to article

1986-1987. He has been active in research on Design and Analysis of Approximation Algorithm for 30 years. And over these years he has published 177 Journal

K-d tree (3,770 words) [view diff] exact match in snippet view article find links to article

than any of the k current bests. It can also be converted to an approximation algorithm to run faster. For example, approximate nearest neighbour searching

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

larger than 1, and smaller is better). They present a 3/2-WMMS approximation algorithm for two agents, and an WMMS algorithm for n agents with binary

Wiener connector (1,129 words) [view diff] exact match in snippet view article find links to article

solution can be found in polynomial time. There is a constant-factor approximation algorithm for the minimum Wiener connector problem that runs in time O (

Chakravala method (3,308 words) [view diff] exact match in snippet view article find links to article

of the chakravala method, states "The method represents a best approximation algorithm of minimal length that, owing to several minimization properties

Generative model (2,431 words) [view diff] exact match in snippet view article find links to article

attribute Y. Mitchell 2015: "Logistic Regression is a function approximation algorithm that uses training data to directly estimate P ( Y ∣ X ) {\displaystyle

Method of moments (electromagnetics) (4,006 words) [view diff] case mismatch in snippet view article

the Characteristic Basis Function Method and the Adaptive Cross Approximation Algorithm". IEEE Transactions on Antennas and Propagation. 56 (11): 3440–3451

Stochastic variance reduction (1,858 words) [view diff] exact match in snippet view article find links to article

} . Any finite sum problem can be optimized using a stochastic approximation algorithm by using F ( ⋅ , ξ ) = f ξ {\displaystyle F(\cdot ,\xi )=f_{\xi

Streaming algorithm (3,608 words) [view diff] exact match in snippet view article find links to article

take action as soon as each point arrives. If the algorithm is an approximation algorithm then the accuracy of the answer is another key factor. The accuracy

N-body simulation (4,082 words) [view diff] exact match in snippet view article find links to article

universal physical constants Virgo Consortium Barnes–Hut simulation – Approximation algorithm for the n-body problem Bolshoi cosmological simulation – Computer

House (astrology) (5,033 words) [view diff] exact match in snippet view article

Placidus system. The topocentric system can also be described as an approximation algorithm for the Placidus system. Topocentric houses are also called Polich-Page

Single-machine scheduling (2,762 words) [view diff] exact match in snippet view article find links to article

presents both exact exponential-time algorithms and a polynomial-time approximation algorithm. The problem 1|| ∑ U j {\displaystyle \sum U_{j}} aims to minimize

Ignacio Grossmann (1,376 words) [view diff] exact match in snippet view article find links to article

Duran, Marco A.; Grossmann, Ignacio E. (1986-10-01). "An outer-approximation algorithm for a class of mixed-integer nonlinear programs". Mathematical

Attention economy (4,730 words) [view diff] case mismatch in snippet view article find links to article

Vee, Erik (2007). "Personalized Ad Delivery when Ads Fatigue: An Approximation Algorithm". In Deng, Xiaotie; Graham, Fan Chung (eds.). Internet and Network

Mixed Chinese postman problem (2,123 words) [view diff] case mismatch in snippet view article find links to article

Raghavachari, Balaji; Veerasamy, Jeyakesavan (January 1999). "A 3/2-Approximation Algorithm for the Mixed Postman Problem". SIAM Journal on Discrete Mathematics

Polygon partition (2,579 words) [view diff] exact match in snippet view article find links to article

Zheng, Si-Qing (1993-12-01). "An efficient divide-and-conquer approximation algorithm for partitioning into d-boxes". International Journal of Computational

Permutation pattern (4,037 words) [view diff] exact match in snippet view article find links to article

permutations, there are bounds and conjectures. Price (1997) used an approximation algorithm which suggests that the packing density of 1324 is around 0.244

Galactic algorithm (2,636 words) [view diff] case mismatch in snippet view article find links to article

Shayan Oveis Gharan (September 1, 2020). "A (Slightly) Improved Approximation Algorithm for Metric TSP". arXiv:2007.01409 [cs.DS]. Klarreich, Erica (8

Minimum evolution (2,440 words) [view diff] exact match in snippet view article find links to article

than a dozen taxa, even with multiprocessing. There is only one approximation algorithm with proven error bounds, published in 2012. In practical use,

E-graph (2,143 words) [view diff] exact match in snippet view article find links to article

e-class. This problem is NP-hard. There is also no constant-factor approximation algorithm for this problem, which can be shown by reduction from the set

Agreeable subset (1,620 words) [view diff] exact match in snippet view article find links to article

problem is strongly NP-hard. There exists a polynomial-time O(log n) approximation algorithm.: Thm.7-13 The agreeable subset problem was studied with additional

Neural coding (8,436 words) [view diff] exact match in snippet view article find links to article

neurons. Other models are based on matching pursuit, a sparse approximation algorithm which finds the "best matching" projections of multidimensional

Boson sampling (7,102 words) [view diff] exact match in snippet view article find links to article

Mark; Sinclair, Alistair; Vigoda, Eric (2001). "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries". Journal

Color rendering index (5,466 words) [view diff] exact match in snippet view article find links to article

10^{-3}.\end{aligned}}} We can verify the CCT by using McCamy's approximation algorithm to estimate the CCT from the xy chromaticities: CCT est. = − 449

Ryan O'Donnell (computer scientist) (669 words) [view diff] exact match in snippet view article

advised by Madhu Sudan. O'Donnell proved that the Goemans–Williamson approximation algorithm for MAX-CUT is optimal, assuming the unique games conjecture. The

Medoid (4,003 words) [view diff] exact match in snippet view article find links to article

distance between two points in the ensemble. Note that RAND is an approximation algorithm, and moreover Δ {\textstyle \Delta } may not be known apriori.

Interval scheduling (2,546 words) [view diff] exact match in snippet view article find links to article

3] from group #2 and then [4..6] from group #1. A more general approximation algorithm attains a 2-factor approximation for the weighted case. Using the

Fisher market (2,899 words) [view diff] exact match in snippet view article find links to article

whether CE exists is NP-hard even with 3 agents. They presented an approximation algorithm which relaxes the CE conditions in two ways: (1) The bundle allocated

Multiplicative weight update method (3,696 words) [view diff] exact match in snippet view article find links to article

D.; Khachiyan, Leonid G. (1995). "A sublinear-time randomized approximation algorithm for matrix games". Operations Research Letters. 18 (2): 53–58.

Quadratic knapsack problem (3,911 words) [view diff] exact match in snippet view article find links to article

mixed-integer quadratic package. George Dantzig proposed a greedy approximation algorithm to unbounded knapsack problem which can also be used to solve the

Arc routing (4,812 words) [view diff] case mismatch in snippet view article find links to article

Raghavachari, Balaji; Veerasamy, Jeyakesavan (January 1999). "A 3/2-Approximation Algorithm for the Mixed Postman Problem". SIAM Journal on Discrete Mathematics

Euclidean minimum spanning tree (6,676 words) [view diff] exact match in snippet view article find links to article

Another application of minimum spanning trees is a constant-factor approximation algorithm for the Euclidean traveling salesman problem, the problem of finding

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

O((m/\varepsilon )^{n^{2}+1})} . For a variable number of agents, a trivial approximation algorithm attains O P T + ( n − 1 ) ⋅ S {\displaystyle OPT+(n-1)\cdot S}

Pathwidth (7,684 words) [view diff] exact match in snippet view article find links to article

constant. The best known approximation ratio of a polynomial time approximation algorithm for pathwidth is O((log n)3/2). For earlier approximation algorithms

Multifit algorithm (4,574 words) [view diff] exact match in snippet view article find links to article

Return the resulting scheduling. Multifit is a constant-factor approximation algorithm. It always finds a partition in which the makespan is at most a

Analysis of Boolean functions (5,379 words) [view diff] exact match in snippet view article find links to article

devised. Majority is Stablest implies that the Goemans–Williamson approximation algorithm for MAX-CUT is optimal, assuming the unique games conjecture. This

Backpressure routing (7,659 words) [view diff] case mismatch in snippet view article find links to article

April 2010. B. Awerbuch and T. Leighton, "A Simple Local-Control Approximation Algorithm for Multicommodity Flow," Proc. 34th IEEE Conf. on Foundations

Maximin share (11,200 words) [view diff] case mismatch in snippet view article find links to article

ISBN 978-3-95977-099-6. Garg, Jugal; Taki, Setareh (2020-07-13). "An Improved Approximation Algorithm for Maximin Shares". Proceedings of the 21st ACM Conference on