René's URL Explorer Experiment


Title: Approximation algorithm - Wikipedia

Open Graph Title: Approximation algorithm - Wikipedia

Generator: MediaWiki 1.46.0-wmf.10

direct link

Domain: en.wikipedia.org

Hey, it has json ld scripts: 
{"@context":"https:\/\/schema.org","@type":"Article","name":"Approximation algorithm","url":"https:\/\/en.wikipedia.org\/wiki\/Approximation_algorithm","sameAs":"http:\/\/www.wikidata.org\/entity\/Q621751","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q621751","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2004-03-29T22:04:42Z","dateModified":"2025-12-18T09:26:09Z","headline":"class of algorithms that find approximate solutions to optimization problems"}
referrerorigin-when-cross-origin
format-detectiontelephone=no
og:typewebsite

Links:

Jump to contenthttps://en.wikipedia.org/wiki/Approximation_algorithm#bodyContent
Main pagehttps://en.wikipedia.org/wiki/Main_Page
Contentshttps://en.wikipedia.org/wiki/Wikipedia:Contents
Current eventshttps://en.wikipedia.org/wiki/Portal:Current_events
Random articlehttps://en.wikipedia.org/wiki/Special:Random
About Wikipediahttps://en.wikipedia.org/wiki/Wikipedia:About
Contact ushttps://en.wikipedia.org/wiki/Wikipedia:Contact_us
Helphttps://en.wikipedia.org/wiki/Help:Contents
Learn to edithttps://en.wikipedia.org/wiki/Help:Introduction
Community portalhttps://en.wikipedia.org/wiki/Wikipedia:Community_portal
Recent changeshttps://en.wikipedia.org/wiki/Special:RecentChanges
Upload filehttps://en.wikipedia.org/wiki/Wikipedia:File_upload_wizard
Special pageshttps://en.wikipedia.org/wiki/Special:SpecialPages
https://en.wikipedia.org/wiki/Main_Page
Search https://en.wikipedia.org/wiki/Special:Search
Donatehttps://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en
Create accounthttps://en.wikipedia.org/w/index.php?title=Special:CreateAccount&returnto=Approximation+algorithm
Log inhttps://en.wikipedia.org/w/index.php?title=Special:UserLogin&returnto=Approximation+algorithm
Donatehttps://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en
Create accounthttps://en.wikipedia.org/w/index.php?title=Special:CreateAccount&returnto=Approximation+algorithm
Log inhttps://en.wikipedia.org/w/index.php?title=Special:UserLogin&returnto=Approximation+algorithm
(Top) https://en.wikipedia.org/wiki/Approximation_algorithm
1 Introduction https://en.wikipedia.org/wiki/Approximation_algorithm#Introduction
2 Algorithm design techniques https://en.wikipedia.org/wiki/Approximation_algorithm#Algorithm_design_techniques
3 A posteriori guarantees https://en.wikipedia.org/wiki/Approximation_algorithm#A_posteriori_guarantees
4 Hardness of approximation https://en.wikipedia.org/wiki/Approximation_algorithm#Hardness_of_approximation
5 Practicality https://en.wikipedia.org/wiki/Approximation_algorithm#Practicality
6 Structure of approximation algorithms https://en.wikipedia.org/wiki/Approximation_algorithm#Structure_of_approximation_algorithms
7 Performance guarantees https://en.wikipedia.org/wiki/Approximation_algorithm#Performance_guarantees
8 Epsilon terms https://en.wikipedia.org/wiki/Approximation_algorithm#Epsilon_terms
9 See also https://en.wikipedia.org/wiki/Approximation_algorithm#See_also
10 Citations https://en.wikipedia.org/wiki/Approximation_algorithm#Citations
11 References https://en.wikipedia.org/wiki/Approximation_algorithm#References
12 External links https://en.wikipedia.org/wiki/Approximation_algorithm#External_links
العربيةhttps://ar.wikipedia.org/wiki/%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D8%AA%D9%82%D8%B1%D9%8A%D8%A8
Češtinahttps://cs.wikipedia.org/wiki/Aproxima%C4%8Dn%C3%AD_algoritmy
Deutschhttps://de.wikipedia.org/wiki/Approximationsalgorithmus
Españolhttps://es.wikipedia.org/wiki/Algoritmo_de_aproximaci%C3%B3n
فارسیhttps://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AA%D9%82%D8%B1%DB%8C%D8%A8%DB%8C
Françaishttps://fr.wikipedia.org/wiki/Algorithme_d%27approximation
한국어https://ko.wikipedia.org/wiki/%EA%B7%BC%EC%82%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
Italianohttps://it.wikipedia.org/wiki/Algoritmo_di_approssimazione
עבריתhttps://he.wikipedia.org/wiki/%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9D_%D7%A7%D7%99%D7%A8%D7%95%D7%91
日本語https://ja.wikipedia.org/wiki/%E8%BF%91%E4%BC%BC%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
Polskihttps://pl.wikipedia.org/wiki/Algorytm_aproksymacyjny
Portuguêshttps://pt.wikipedia.org/wiki/Algoritmo_de_aproxima%C3%A7%C3%A3o
Русскийhttps://ru.wikipedia.org/wiki/%D0%90%D0%BF%D0%BF%D1%80%D0%BE%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC
Српски / srpskihttps://sr.wikipedia.org/wiki/%D0%90%D0%BF%D1%80%D0%BE%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%B0%D0%BC
ไทยhttps://th.wikipedia.org/wiki/%E0%B8%82%E0%B8%B1%E0%B9%89%E0%B8%99%E0%B8%95%E0%B8%AD%E0%B8%99%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%9B%E0%B8%A3%E0%B8%B0%E0%B8%A1%E0%B8%B2%E0%B8%93
Українськаhttps://uk.wikipedia.org/wiki/%D0%90%D0%BF%D1%80%D0%BE%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D1%86%D1%96%D0%B9%D0%BD%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC
Tiếng Việthttps://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_x%E1%BA%A5p_x%E1%BB%89
粵語https://zh-yue.wikipedia.org/wiki/%E8%BF%91%E4%BC%BC%E6%BC%94%E7%AE%97%E6%B3%95
中文https://zh.wikipedia.org/wiki/%E8%BF%91%E4%BC%BC%E7%AE%97%E6%B3%95
Edit linkshttps://www.wikidata.org/wiki/Special:EntityPage/Q621751#sitelinks-wikipedia
Articlehttps://en.wikipedia.org/wiki/Approximation_algorithm
Talkhttps://en.wikipedia.org/wiki/Talk:Approximation_algorithm
Readhttps://en.wikipedia.org/wiki/Approximation_algorithm
Edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit
View historyhttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=history
Readhttps://en.wikipedia.org/wiki/Approximation_algorithm
Edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit
View historyhttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=history
What links herehttps://en.wikipedia.org/wiki/Special:WhatLinksHere/Approximation_algorithm
Related changeshttps://en.wikipedia.org/wiki/Special:RecentChangesLinked/Approximation_algorithm
Upload filehttps://en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard
Permanent linkhttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&oldid=1328179852
Page informationhttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=info
Cite this pagehttps://en.wikipedia.org/w/index.php?title=Special:CiteThisPage&page=Approximation_algorithm&id=1328179852&wpFormIdentifier=titleform
Get shortened URLhttps://en.wikipedia.org/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FApproximation_algorithm
Download QR codehttps://en.wikipedia.org/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FApproximation_algorithm
Download as PDFhttps://en.wikipedia.org/w/index.php?title=Special:DownloadAsPdf&page=Approximation_algorithm&action=show-download-screen
Printable versionhttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&printable=yes
Wikidata itemhttps://www.wikidata.org/wiki/Special:EntityPage/Q621751
computer sciencehttps://en.wikipedia.org/wiki/Computer_science
operations researchhttps://en.wikipedia.org/wiki/Operations_research
efficienthttps://en.wikipedia.org/wiki/Time_complexity#Polynomial_time
algorithmshttps://en.wikipedia.org/wiki/Algorithm
approximatehttps://en.wikipedia.org/wiki/Approximation
optimization problemshttps://en.wikipedia.org/wiki/Optimization_problem
NP-hardhttps://en.wikipedia.org/wiki/NP-hardness
[1]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-Bernard._2011-1
theoretical computer sciencehttps://en.wikipedia.org/wiki/Theoretical_computer_science
P ≠ NPhttps://en.wikipedia.org/wiki/P_versus_NP_problem
polynomial timehttps://en.wikipedia.org/wiki/Time_complexity
Christofides-Serdyukov algorithmhttps://en.wikipedia.org/wiki/Christofides-Serdyukov_algorithm
Travelling salesman problemhttps://en.wikipedia.org/wiki/Travelling_salesman_problem
Vizing’s theoremhttps://en.wikipedia.org/wiki/Vizing%27s_theorem
Lenstrahttps://en.wikipedia.org/wiki/Jan_Karel_Lenstra
Shmoyshttps://en.wikipedia.org/wiki/David_Shmoys
Tardoshttps://en.wikipedia.org/wiki/%C3%89va_Tardos
[2]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-2
schedulinghttps://en.wikipedia.org/wiki/Scheduling_(computing)
analysishttps://en.wikipedia.org/wiki/Mathematical_analysis
mathematical proofhttps://en.wikipedia.org/wiki/Mathematical_proof
[1]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-Bernard._2011-1
heuristicshttps://en.wikipedia.org/wiki/Heuristic_(computer_science)
annealinghttps://en.wikipedia.org/wiki/Simulated_annealing
genetic algorithmshttps://en.wikipedia.org/wiki/Genetic_algorithm
theoretical computer sciencehttps://en.wikipedia.org/wiki/Theoretical_computer_science
[3]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-3
Goemans–Williamson algorithmhttps://en.wikipedia.org/wiki/Semidefinite_programming#Example_3_(Goemans–Williamson_max_cut_approximation_algorithm)
maximum cuthttps://en.wikipedia.org/wiki/Maximum_cut
[4]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-4
edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit§ion=1
minimum vertex coverhttps://en.wikipedia.org/wiki/Vertex_cover
vertex coverhttps://en.wikipedia.org/wiki/Vertex_cover
matchinghttps://en.wikipedia.org/wiki/Matching_(graph_theory)
constant-factor approximation algorithmhttps://en.wikipedia.org/wiki/Constant-factor_approximation_algorithm
unique games conjecturehttps://en.wikipedia.org/wiki/Unique_games_conjecture
[5]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-5
knapsack problemhttps://en.wikipedia.org/wiki/Knapsack_problem
polynomial-time approximation schemehttps://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme
P = NPhttps://en.wikipedia.org/wiki/P_%3D_NP
maximum clique problemhttps://en.wikipedia.org/wiki/Clique_problem
theory of NP-completenesshttps://en.wikipedia.org/wiki/NP-completeness
edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit§ion=2
Greedy algorithmhttps://en.wikipedia.org/wiki/Greedy_algorithm
Local searchhttps://en.wikipedia.org/wiki/Local_search_(optimization)
dynamic programminghttps://en.wikipedia.org/wiki/Dynamic_programming
parameterized approximationshttps://en.wikipedia.org/wiki/Parameterized_approximation_algorithm
convex programminghttps://en.wikipedia.org/wiki/Convex_programming
Linear programminghttps://en.wikipedia.org/wiki/Linear_programming
Semidefinite programminghttps://en.wikipedia.org/wiki/Semidefinite_programming
Randomized roundinghttps://en.wikipedia.org/wiki/Randomized_rounding
Iterative roundinghttps://en.wikipedia.org/w/index.php?title=Iterative_rounding&action=edit&redlink=1
edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit§ion=3
convex relaxationhttps://en.wikipedia.org/wiki/Convex_programming
linear programming relaxationhttps://en.wikipedia.org/wiki/Linear_programming_relaxation
edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit§ion=4
inapproximability theoryhttps://en.wikipedia.org/wiki/Hardness_of_approximation
reductionshttps://en.wikipedia.org/wiki/Reduction_(complexity)
[6]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-6
Independent Sethttps://en.wikipedia.org/wiki/Independent_set_(graph_theory)
[7]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-7
PCP theoremhttps://en.wikipedia.org/wiki/PCP_theorem
[8]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-8
Johnson'shttps://en.wikipedia.org/wiki/David_S._Johnson
Max SAThttps://en.wikipedia.org/wiki/Maximum_satisfiability_problem
set coverhttps://en.wikipedia.org/wiki/Set_cover_problem
independent sethttps://en.wikipedia.org/wiki/Independent_set_(graph_theory)
coloringhttps://en.wikipedia.org/wiki/Graph_coloring
[9]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-9
edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit§ion=5
Galactic algorithmhttps://en.wikipedia.org/wiki/Galactic_algorithm
linear programminghttps://en.wikipedia.org/wiki/Linear_programming_relaxation
semidefinitehttps://en.wikipedia.org/wiki/Semidefinite_programming
ellipsoid algorithmhttps://en.wikipedia.org/wiki/Ellipsoid_method
Euclidean TSPhttps://en.wikipedia.org/wiki/Euclidean_traveling_salesman_problem
Sanjeev Arorahttps://en.wikipedia.org/wiki/Sanjeev_Arora_(computer_scientist)
Joseph Mitchellhttps://en.wikipedia.org/wiki/Joseph_S._B._Mitchell
[10]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-10
[11]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-11
edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit§ion=6
edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit§ion=7
[12]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-ausiello99complexity-12
[13]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-kann92onthe-13
[12]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-ausiello99complexity-12
[13]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-kann92onthe-13
[13]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-kann92onthe-13
[12]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-ausiello99complexity-12
[12]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-ausiello99complexity-12
[13]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-kann92onthe-13
[12]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-ausiello99complexity-12
[13]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-kann92onthe-13
edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit§ion=8
MAX-3SAThttps://en.wikipedia.org/wiki/MAX-3SAT
Johan Håstadhttps://en.wikipedia.org/wiki/Johan_H%C3%A5stad
[14]https://en.wikipedia.org/wiki/Approximation_algorithm#cite_note-hastad99someoptimal-14
polynomial-time approximation schemehttps://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme
edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit§ion=9
Domination analysishttps://en.wikipedia.org/wiki/Domination_analysis
PTAShttps://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme
Parameterized approximation algorithmhttps://en.wikipedia.org/wiki/Parameterized_approximation_algorithm
FPThttps://en.wikipedia.org/wiki/Fixed-parameter_algorithm
APXhttps://en.wikipedia.org/wiki/APX
Approximation-preserving reductionhttps://en.wikipedia.org/wiki/Approximation-preserving_reduction
Exact algorithmhttps://en.wikipedia.org/wiki/Exact_algorithm
edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit§ion=10
general referenceshttps://en.wikipedia.org/wiki/Wikipedia:Citing_sources#General_references
inline citationshttps://en.wikipedia.org/wiki/Wikipedia:Citing_sources#Inline_citations
improvehttps://en.wikipedia.org/wiki/Wikipedia:WikiProject_Reliability
introducinghttps://en.wikipedia.org/wiki/Wikipedia:When_to_cite
Learn how and when to remove this messagehttps://en.wikipedia.org/wiki/Help:Maintenance_template_removal
ahttps://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-Bernard._2011_1-0
bhttps://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-Bernard._2011_1-1
The design of approximation algorithmshttp://www.designofapproxalgs.com/
ISBNhttps://en.wikipedia.org/wiki/ISBN_(identifier)
9780521195270https://en.wikipedia.org/wiki/Special:BookSources/9780521195270
OCLChttps://en.wikipedia.org/wiki/OCLC_(identifier)
671709856https://search.worldcat.org/oclc/671709856
cite bookhttps://en.wikipedia.org/wiki/Template:Cite_book
linkhttps://en.wikipedia.org/wiki/Category:CS1_maint:_multiple_names:_authors_list
^https://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-2
CiteSeerXhttps://en.wikipedia.org/wiki/CiteSeerX_(identifier)
10.1.1.115.708https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.708
doihttps://en.wikipedia.org/wiki/Doi_(identifier)
10.1007/BF01585745https://doi.org/10.1007%2FBF01585745
ISSNhttps://en.wikipedia.org/wiki/ISSN_(identifier)
0025-5610https://search.worldcat.org/issn/0025-5610
S2CIDhttps://en.wikipedia.org/wiki/S2CID_(identifier)
206799898https://api.semanticscholar.org/CorpusID:206799898
^https://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-3
"When trees collide"http://portal.acm.org/citation.cfm?doid=103418.103437
doihttps://en.wikipedia.org/wiki/Doi_(identifier)
10.1145/103418.103437https://doi.org/10.1145%2F103418.103437
ISBNhttps://en.wikipedia.org/wiki/ISBN_(identifier)
978-0-89791-397-3https://en.wikipedia.org/wiki/Special:BookSources/978-0-89791-397-3
S2CIDhttps://en.wikipedia.org/wiki/S2CID_(identifier)
1245448https://api.semanticscholar.org/CorpusID:1245448
^https://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-4
CiteSeerXhttps://en.wikipedia.org/wiki/CiteSeerX_(identifier)
10.1.1.34.8500https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.8500
doihttps://en.wikipedia.org/wiki/Doi_(identifier)
10.1145/227683.227684https://doi.org/10.1145%2F227683.227684
ISSNhttps://en.wikipedia.org/wiki/ISSN_(identifier)
0004-5411https://search.worldcat.org/issn/0004-5411
S2CIDhttps://en.wikipedia.org/wiki/S2CID_(identifier)
15794408https://api.semanticscholar.org/CorpusID:15794408
^https://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-5
"Vertex cover might be hard to approximate to within 2−ε"https://doi.org/10.1016%2Fj.jcss.2007.06.019
doihttps://en.wikipedia.org/wiki/Doi_(identifier)
10.1016/j.jcss.2007.06.019https://doi.org/10.1016%2Fj.jcss.2007.06.019
^https://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-6
arXivhttps://en.wikipedia.org/wiki/ArXiv_(identifier)
1303.6437https://arxiv.org/abs/1303.6437
doihttps://en.wikipedia.org/wiki/Doi_(identifier)
10.1016/j.jcss.2015.06.003https://doi.org/10.1016%2Fj.jcss.2015.06.003
^https://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-7
"Interactive Proofs and the Hardness of Approximating Cliques"https://doi.org/10.1145%2F226643.226652
doihttps://en.wikipedia.org/wiki/Doi_(identifier)
10.1145/226643.226652https://doi.org/10.1145%2F226643.226652
ISSNhttps://en.wikipedia.org/wiki/ISSN_(identifier)
0004-5411https://search.worldcat.org/issn/0004-5411
^https://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-8
"Probabilistic Checking of Proofs: A New Characterization of NP"https://doi.org/10.1145%2F273865.273901
doihttps://en.wikipedia.org/wiki/Doi_(identifier)
10.1145/273865.273901https://doi.org/10.1145%2F273865.273901
ISSNhttps://en.wikipedia.org/wiki/ISSN_(identifier)
0004-5411https://search.worldcat.org/issn/0004-5411
S2CIDhttps://en.wikipedia.org/wiki/S2CID_(identifier)
751563https://api.semanticscholar.org/CorpusID:751563
^https://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-9
"Approximation algorithms for combinatorial problems"https://doi.org/10.1016%2FS0022-0000%2874%2980044-9
doihttps://en.wikipedia.org/wiki/Doi_(identifier)
10.1016/S0022-0000(74)80044-9https://doi.org/10.1016%2FS0022-0000%2874%2980044-9
^https://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-10
CiteSeerXhttps://en.wikipedia.org/wiki/CiteSeerX_(identifier)
10.1.1.32.3376https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.3376
doihttps://en.wikipedia.org/wiki/Doi_(identifier)
10.1109/SFCS.1996.548458https://doi.org/10.1109%2FSFCS.1996.548458
ISBNhttps://en.wikipedia.org/wiki/ISBN_(identifier)
978-0-8186-7594-2https://en.wikipedia.org/wiki/Special:BookSources/978-0-8186-7594-2
S2CIDhttps://en.wikipedia.org/wiki/S2CID_(identifier)
1499391https://api.semanticscholar.org/CorpusID:1499391
^https://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-11
doihttps://en.wikipedia.org/wiki/Doi_(identifier)
10.1109/SFCS.1997.646145https://doi.org/10.1109%2FSFCS.1997.646145
ISBNhttps://en.wikipedia.org/wiki/ISBN_(identifier)
978-0-8186-8197-4https://en.wikipedia.org/wiki/Special:BookSources/978-0-8186-8197-4
S2CIDhttps://en.wikipedia.org/wiki/S2CID_(identifier)
10656723https://api.semanticscholar.org/CorpusID:10656723
ahttps://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-ausiello99complexity_12-0
bhttps://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-ausiello99complexity_12-1
chttps://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-ausiello99complexity_12-2
dhttps://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-ausiello99complexity_12-3
ehttps://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-ausiello99complexity_12-4
ahttps://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-kann92onthe_13-0
bhttps://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-kann92onthe_13-1
chttps://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-kann92onthe_13-2
dhttps://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-kann92onthe_13-3
ehttps://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-kann92onthe_13-4
On the Approximability of NP-complete Optimization Problemshttps://www.csc.kth.se/~viggo/papers/phdthesis.pdf
^https://en.wikipedia.org/wiki/Approximation_algorithm#cite_ref-hastad99someoptimal_14-0
Johan Håstadhttps://en.wikipedia.org/wiki/Johan_H%C3%A5stad
"Some Optimal Inapproximability Results"http://www.nada.kth.se/~johanh/optimalinap.ps
CiteSeerXhttps://en.wikipedia.org/wiki/CiteSeerX_(identifier)
10.1.1.638.2808https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.638.2808
doihttps://en.wikipedia.org/wiki/Doi_(identifier)
10.1145/502090.502098https://doi.org/10.1145%2F502090.502098
S2CIDhttps://en.wikipedia.org/wiki/S2CID_(identifier)
5120748https://api.semanticscholar.org/CorpusID:5120748
edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit§ion=11
Vazirani, Vijay V.https://en.wikipedia.org/wiki/Vijay_Vazirani
ISBNhttps://en.wikipedia.org/wiki/ISBN_(identifier)
978-3-540-65367-7https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-65367-7
Thomas H. Cormenhttps://en.wikipedia.org/wiki/Thomas_H._Cormen
Charles E. Leisersonhttps://en.wikipedia.org/wiki/Charles_E._Leiserson
Ronald L. Rivesthttps://en.wikipedia.org/wiki/Ronald_L._Rivest
Clifford Steinhttps://en.wikipedia.org/wiki/Clifford_Stein
Introduction to Algorithmshttps://en.wikipedia.org/wiki/Introduction_to_Algorithms
ISBNhttps://en.wikipedia.org/wiki/ISBN_(identifier)
0-262-03293-7https://en.wikipedia.org/wiki/Special:BookSources/0-262-03293-7
Dorit S. Hochbaumhttps://en.wikipedia.org/wiki/Dorit_S._Hochbaum
Approximation Algorithms for NP-Hard problemshttps://en.wikipedia.org/w/index.php?title=Approximation_Algorithms_for_NP-Hard_problems&action=edit&redlink=1
ISBNhttps://en.wikipedia.org/wiki/ISBN_(identifier)
0-534-94968-1https://en.wikipedia.org/wiki/Special:BookSources/0-534-94968-1
Williamson, David P.https://en.wikipedia.org/wiki/David_P._Williamson
Shmoys, David B.https://en.wikipedia.org/wiki/David_Shmoys
Cambridge University Presshttps://en.wikipedia.org/wiki/Cambridge_University_Press
ISBNhttps://en.wikipedia.org/wiki/ISBN_(identifier)
978-0521195270https://en.wikipedia.org/wiki/Special:BookSources/978-0521195270
edithttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&action=edit§ion=12
Marek Karpinskihttps://en.wikipedia.org/wiki/Marek_Karpinski
Gerhard Woegingerhttps://en.wikipedia.org/wiki/Gerhard_J._Woeginger
A compendium of NP optimization problemshttps://www.csc.kth.se/tcs/compendium/
vhttps://en.wikipedia.org/wiki/Template:Optimization_algorithms
thttps://en.wikipedia.org/wiki/Template_talk:Optimization_algorithms
ehttps://en.wikipedia.org/wiki/Special:EditPage/Template:Optimization_algorithms
Optimizationhttps://en.wikipedia.org/wiki/Mathematical_optimization
Algorithmshttps://en.wikipedia.org/wiki/Optimization_algorithm
methodshttps://en.wikipedia.org/wiki/Iterative_method
heuristicshttps://en.wikipedia.org/wiki/Heuristic_algorithm
Unconstrained nonlinearhttps://en.wikipedia.org/wiki/Nonlinear_programming
Functionshttps://en.wikipedia.org/wiki/Function_(mathematics)
Golden-section searchhttps://en.wikipedia.org/wiki/Golden-section_search
Powell's methodhttps://en.wikipedia.org/wiki/Powell%27s_method
Line searchhttps://en.wikipedia.org/wiki/Line_search
Nelder–Mead methodhttps://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method
Successive parabolic interpolationhttps://en.wikipedia.org/wiki/Successive_parabolic_interpolation
Gradientshttps://en.wikipedia.org/wiki/Gradient
Convergencehttps://en.wikipedia.org/wiki/Local_convergence
Trust regionhttps://en.wikipedia.org/wiki/Trust_region
Wolfe conditionshttps://en.wikipedia.org/wiki/Wolfe_conditions
Quasi–Newtonhttps://en.wikipedia.org/wiki/Quasi-Newton_method
Berndt–Hall–Hall–Hausmanhttps://en.wikipedia.org/wiki/Berndt%E2%80%93Hall%E2%80%93Hall%E2%80%93Hausman_algorithm
Broyden–Fletcher–Goldfarb–Shannohttps://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm
L-BFGShttps://en.wikipedia.org/wiki/Limited-memory_BFGS
Davidon–Fletcher–Powellhttps://en.wikipedia.org/wiki/Davidon%E2%80%93Fletcher%E2%80%93Powell_formula
Symmetric rank-one (SR1)https://en.wikipedia.org/wiki/Symmetric_rank-one
Other methodshttps://en.wikipedia.org/wiki/Iterative_method
Conjugate gradienthttps://en.wikipedia.org/wiki/Nonlinear_conjugate_gradient_method
Gauss–Newtonhttps://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm
Gradienthttps://en.wikipedia.org/wiki/Gradient_descent
Mirrorhttps://en.wikipedia.org/wiki/Mirror_descent
Levenberg–Marquardthttps://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm
Powell's dog leg methodhttps://en.wikipedia.org/wiki/Powell%27s_dog_leg_method
Truncated Newtonhttps://en.wikipedia.org/wiki/Truncated_Newton_method
Hessianshttps://en.wikipedia.org/wiki/Hessian_matrix
Newton's methodhttps://en.wikipedia.org/wiki/Newton%27s_method_in_optimization
https://en.wikipedia.org/wiki/File:Max_paraboloid.svg
Constrained nonlinearhttps://en.wikipedia.org/wiki/Nonlinear_programming
Barrier methodshttps://en.wikipedia.org/wiki/Barrier_function
Penalty methodshttps://en.wikipedia.org/wiki/Penalty_method
Augmented Lagrangian methodshttps://en.wikipedia.org/wiki/Augmented_Lagrangian_method
Sequential quadratic programminghttps://en.wikipedia.org/wiki/Sequential_quadratic_programming
Successive linear programminghttps://en.wikipedia.org/wiki/Successive_linear_programming
Convex optimizationhttps://en.wikipedia.org/wiki/Convex_optimization
Convex minimizationhttps://en.wikipedia.org/wiki/Convex_minimization
Cutting-plane methodhttps://en.wikipedia.org/wiki/Cutting-plane_method
Reduced gradient (Frank–Wolfe)https://en.wikipedia.org/wiki/Frank%E2%80%93Wolfe_algorithm
Subgradient methodhttps://en.wikipedia.org/wiki/Subgradient_method
Linearhttps://en.wikipedia.org/wiki/Linear_programming
quadratichttps://en.wikipedia.org/wiki/Quadratic_programming
Interior pointhttps://en.wikipedia.org/wiki/Linear_programming#Interior_point
Affine scalinghttps://en.wikipedia.org/wiki/Affine_scaling
Ellipsoid algorithm of Khachiyanhttps://en.wikipedia.org/wiki/Ellipsoid_method
Projective algorithm of Karmarkarhttps://en.wikipedia.org/wiki/Karmarkar%27s_algorithm
Basis-https://en.wikipedia.org/wiki/Matroid
exchangehttps://en.wikipedia.org/wiki/Exchange_algorithm
Simplex algorithm of Dantzighttps://en.wikipedia.org/wiki/Simplex_algorithm
Revised simplex algorithmhttps://en.wikipedia.org/wiki/Revised_simplex_method
Criss-cross algorithmhttps://en.wikipedia.org/wiki/Criss-cross_algorithm
Principal pivoting algorithm of Lemkehttps://en.wikipedia.org/wiki/Lemke%27s_algorithm
Active-set methodhttps://en.wikipedia.org/wiki/Active-set_method
Combinatorialhttps://en.wikipedia.org/wiki/Combinatorial_optimization
Dynamic programminghttps://en.wikipedia.org/wiki/Dynamic_programming
Greedy algorithmhttps://en.wikipedia.org/wiki/Greedy_algorithm
Integer programminghttps://en.wikipedia.org/wiki/Integer_programming
Branch and boundhttps://en.wikipedia.org/wiki/Branch_and_bound
cuthttps://en.wikipedia.org/wiki/Branch_and_cut
Graph algorithmshttps://en.wikipedia.org/wiki/Graph_algorithm
Minimum spanning treehttps://en.wikipedia.org/wiki/Minimum_spanning_tree
Borůvkahttps://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm
Primhttps://en.wikipedia.org/wiki/Prim%27s_algorithm
Kruskalhttps://en.wikipedia.org/wiki/Kruskal%27s_algorithm
Shortest pathhttps://en.wikipedia.org/wiki/Shortest_path_problem
Bellman–Fordhttps://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
SPFAhttps://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm
Dijkstrahttps://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Floyd–Warshallhttps://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
Network flowshttps://en.wikipedia.org/wiki/Flow_network
Dinichttps://en.wikipedia.org/wiki/Dinic%27s_algorithm
Edmonds–Karphttps://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm
Ford–Fulkersonhttps://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
Push–relabel maximum flowhttps://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm
Metaheuristicshttps://en.wikipedia.org/wiki/Metaheuristic
Evolutionary algorithmhttps://en.wikipedia.org/wiki/Evolutionary_algorithm
Hill climbinghttps://en.wikipedia.org/wiki/Hill_climbing
Local searchhttps://en.wikipedia.org/wiki/Local_search_(optimization)
Parallel metaheuristicshttps://en.wikipedia.org/wiki/Parallel_metaheuristic
Simulated annealinghttps://en.wikipedia.org/wiki/Simulated_annealing
Spiral optimization algorithmhttps://en.wikipedia.org/wiki/Spiral_optimization_algorithm
Tabu searchhttps://en.wikipedia.org/wiki/Tabu_search
Softwarehttps://en.wikipedia.org/wiki/Comparison_of_optimization_software
Authority control databaseshttps://en.wikipedia.org/wiki/Help:Authority_control
https://www.wikidata.org/wiki/Q621751#identifiers
GNDhttps://d-nb.info/gnd/4500954-5
United Stateshttps://id.loc.gov/authorities/sh2009010988
Francehttps://catalogue.bnf.fr/ark:/12148/cb16603384f
BnF datahttps://data.bnf.fr/ark:/12148/cb16603384f
Israelhttps://www.nli.org.il/en/authorities/987007475469205171
Yale LUXhttps://lux.collections.yale.edu/view/concept/fdc2ae0c-bf65-44a9-925f-fc05addbfadf
https://en.wikipedia.org/w/index.php?title=Approximation_algorithm&oldid=1328179852https://en.wikipedia.org/w/index.php?title=Approximation_algorithm&oldid=1328179852
Categorieshttps://en.wikipedia.org/wiki/Help:Category
Computational complexity theoryhttps://en.wikipedia.org/wiki/Category:Computational_complexity_theory
Approximation algorithmshttps://en.wikipedia.org/wiki/Category:Approximation_algorithms
CS1 maint: multiple names: authors listhttps://en.wikipedia.org/wiki/Category:CS1_maint:_multiple_names:_authors_list
Articles with short descriptionhttps://en.wikipedia.org/wiki/Category:Articles_with_short_description
Short description matches Wikidatahttps://en.wikipedia.org/wiki/Category:Short_description_matches_Wikidata
Articles lacking in-text citations from April 2009https://en.wikipedia.org/wiki/Category:Articles_lacking_in-text_citations_from_April_2009
All articles lacking in-text citationshttps://en.wikipedia.org/wiki/Category:All_articles_lacking_in-text_citations
Creative Commons Attribution-ShareAlike 4.0 Licensehttps://en.wikipedia.org/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License
Terms of Usehttps://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use
Privacy Policyhttps://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy
Wikimedia Foundation, Inc.https://wikimediafoundation.org/
Privacy policyhttps://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy
About Wikipediahttps://en.wikipedia.org/wiki/Wikipedia:About
Disclaimershttps://en.wikipedia.org/wiki/Wikipedia:General_disclaimer
Contact Wikipediahttps://en.wikipedia.org/wiki/Wikipedia:Contact_us
Legal & safety contactshttps://foundation.wikimedia.org/wiki/Special:MyLanguage/Legal:Wikimedia_Foundation_Legal_and_Safety_Contact_Information
Code of Conducthttps://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct
Developershttps://developer.wikimedia.org
Statisticshttps://stats.wikimedia.org/#/en.wikipedia.org
Cookie statementhttps://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement
Mobile viewhttps://en.wikipedia.org/w/index.php?title=Approximation_algorithm&mobileaction=toggle_view_mobile
https://www.wikimedia.org/
https://www.mediawiki.org/
https://en.wikipedia.org/wiki/Approximation_algorithm
https://en.wikipedia.org/wiki/Approximation_algorithm
https://en.wikipedia.org/wiki/Approximation_algorithm
https://en.wikipedia.org/wiki/Approximation_algorithm
https://en.wikipedia.org/wiki/Approximation_algorithm
https://en.wikipedia.org/wiki/Approximation_algorithm
https://en.wikipedia.org/wiki/Approximation_algorithm
Add topic https://en.wikipedia.org/wiki/Approximation_algorithm

Viewport: width=1120

Robots: max-image-preview:standard

URLs of crawlers that visited me.