Polynomial-time approximation scheme: Revision history

19 December 2024

• curprev 13:0913:09, 19 December 2024 Aadirulez8 talk contribs m 6,267 bytes −43 v2.05 - auto / Fix errors for CW project (Link equal to linktext) undo Tag: WPCleaner

7 August 2024

• curprev 07:4107:41, 7 August 2024 Citation bot talk contribs 6,310 bytes +55 Add: volume, series. | Use this bot. Report bugs. | Suggested by Abductive | Category:Approximation algorithms | #UCB_Category 29/39 undo

2 April 2023

• curprev 08:0208:02, 2 April 2023 CJKVR talk contribs m 6,255 bytes +82 →Deterministic: correct link for polylog function undo

1 February 2023

• curprev 11:4311:43, 1 February 2023 Astenosfear talk contribs 6,173 bytes +140 →Deterministic: an EPTAS runs in FPT time undo Tag: Visual edit
• curprev 11:4111:41, 1 February 2023 Astenosfear talk contribs 6,033 bytes +166 →Deterministic: variant: parameterized approximation scheme undo Tag: Visual edit
• curprev 11:0011:00, 1 February 2023 Astenosfear talk contribs 5,867 bytes −271 →See also: parameterized approximation scheme undo Tag: Visual edit

4 July 2022

• curprev 04:5604:56, 4 July 2022 OlliverWithDoubleL talk contribs m 6,138 bytes +44 math formatting undo Tags: Mobile edit Mobile app edit iOS app edit
• curprev 04:5004:50, 4 July 2022 OlliverWithDoubleL talk contribs 6,094 bytes +116 short description, math formatting undo Tags: Mobile edit Mobile app edit iOS app edit

28 May 2022

• curprev 23:5723:57, 28 May 2022 Malcolmxl5 talk contribs 5,978 bytes +600 Undid revision 1090336424 by 102.250.1.121 (talk). Unconstructive edit. undo Tag: Undo
• curprev 23:5323:53, 28 May 2022 102.250.1.121 talk 5,378 bytes −600 No edit summary undo Tags: Reverted references removed Visual edit Mobile edit Mobile web edit

13 December 2021

• curprev 14:3414:34, 13 December 2021 Erel Segal talk contribs 5,978 bytes −1,080 No edit summary undo Tag: Visual edit

6 July 2021

• curprev 13:2913:29, 6 July 2021 OAbot talk contribs m 7,058 bytes +17 Open access bot: doi added to citation with #oabot. undo

1 February 2021

• curprev 12:1212:12, 1 February 2021 5.44.169.192 talk 7,041 bytes −19 Removed bin packing from the examples of problems that have FPTAS (section "Deterministic" first paragraph). Bin packing does NOT have an FPTAS. This problem does not even have a (3/2-eps)-approximation! In Vazirani's book there is a an asymptotic PTAS for bin packing, but that's a different thing. undo

10 January 2021

• curprev 15:3015:30, 10 January 2021 62.198.4.86 talk 7,060 bytes −27 Fixed broken links undo

13 June 2020

• curprev 01:0701:07, 13 June 2020 InternetArchiveBot talk contribs 7,087 bytes +144 Bluelink 1 book for verifiability (prndis)) #IABot (v2.0.1) (GreenC bot undo

11 June 2020

• curprev 15:2515:25, 11 June 2020 88.100.229.159 talk 6,943 bytes +46 when saying FPT, we should say what the parameter is undo

1 April 2020

• curprev 05:2005:20, 1 April 2020 Citation bot talk contribs 6,897 bytes −47 Alter: pages. Removed URL that duplicated unique identifier. Removed parameters. Formatted dashes. | You can use this bot yourself. Report bugs here. | Activated by AManWithNoPlan | All pages linked from User:AManWithNoPlan/sandbox2 | via #UCB_webform_linked undo

15 March 2019

• curprev 17:1717:17, 15 March 2019 PirateImpulse talk contribs 6,944 bytes +27 unrolled an acronym that was not previously defined (CSPs -> constraint satisfaction problems) undo Tags: Mobile edit Mobile web edit

22 August 2018

• curprev 17:1317:13, 22 August 2018 195.113.30.252 talk 6,917 bytes 0 "Jourlal->Journal" undo

7 July 2018

• curprev 19:0919:09, 7 July 2018 93.84.3.39 talk 6,917 bytes +6 No edit summary undo

10 October 2017

• curprev 05:5805:58, 10 October 2017 AnomieBOT talk contribs m 6,911 bytes +18 Dating maintenance tags: {{Clarify}} undo
• curprev 03:5703:57, 10 October 2017 Siddharthist talk contribs 6,893 bytes +220 →Deterministic: Both knapsack and bin packing admit FPTAS. Cite Vazirani for this fact. undo Tag: Visual edit
• curprev 03:4403:44, 10 October 2017 Siddharthist talk contribs m 6,673 bytes +11 Clarification needed: what is a CSP? undo Tag: 2017 wikitext editor

10 August 2017

• curprev 10:0310:03, 10 August 2017 2001:67c:10ec:52c6:8000::20c talk 6,662 bytes +3 →Deterministic undo

22 June 2017

• curprev 21:5621:56, 22 June 2017 CBM talk contribs m 6,659 bytes +2 Copyediting in citations - nonbreaking spaces and en dashes (manually reviewed) undo

29 October 2016

• curprev 01:4101:41, 29 October 2016 Bender the Bot talk contribs m 6,657 bytes +1 →Deterministic: http→https for Google Books and Google News using AWB undo

30 September 2016

• curprev 02:2702:27, 30 September 2016 Cedar101 talk contribs m 6,656 bytes +15 →Deterministic: \operatorname undo

5 September 2016

• curprev 07:4907:49, 5 September 2016 2001:638:403:5050:224:1dff:fede:83a3 talk 6,641 bytes +4 typo undo
• curprev 07:4707:47, 5 September 2016 2001:638:403:5050:224:1dff:fede:83a3 talk 6,637 bytes +363 another result undo

4 July 2016

• curprev 05:4905:49, 4 July 2016 David Eppstein talk contribs m 6,274 bytes +29 Angelika Steger undo

19 September 2015

• curprev 06:3406:34, 19 September 2015 David Eppstein talk contribs m 6,245 bytes +25 →External links: Gerhard J. Woeginger undo

10 December 2014

• curprev 14:2214:22, 10 December 2014 131.159.44.149 talk 6,220 bytes +1 →As a complexity class: Typo undo

9 December 2014

• curprev 03:0403:04, 9 December 2014 Infinitestory talk contribs 6,219 bytes +888 No edit summary undo

9 November 2013

• curprev 07:5507:55, 9 November 2013 David Eppstein talk contribs 5,331 bytes +488 →Deterministic: supply requested citation undo

8 November 2013

• curprev 06:4306:43, 8 November 2013 AnomieBOT talk contribs m 4,843 bytes +19 Dating maintenance tags: {{Citation needed}} undo
• curprev 04:4204:42, 8 November 2013 AustinBuchanan talk contribs 4,824 bytes +19 →Deterministic undo

5 September 2013

• curprev 16:0516:05, 5 September 2013 75.151.80.11 talk 4,805 bytes −3 Fixed links to complexity zoo which is no longer hosted at Stanford undo

23 March 2013

• curprev 06:2106:21, 23 March 2013 Addbot talk contribs m 4,808 bytes −52 Bot: Migrating 1 interwiki links, now provided by Wikidata on d:q843550 undo

28 February 2013

• curprev 08:3908:39, 28 February 2013 Addbot talk contribs m 4,860 bytes −117 Bot: Migrating 3 interwiki links, now provided by Wikidata on d:q843550 (Report Errors) undo

4 January 2013

• curprev 18:2818:28, 4 January 2013 JackieBot talk contribs m 4,977 bytes +51 r2.7.2) (Robot: Adding fr:Schéma d'approximation en temps polynomial undo

18 July 2012

• curprev 19:4219:42, 18 July 2012 Creidieki talk contribs m 4,926 bytes −2 copyed commas undo

15 May 2012

• curprev 10:3410:34, 15 May 2012 Luckas-bot talk contribs m 4,928 bytes +41 r2.7.1) (Robot: Adding ja:多項式時間近似スキーム undo

11 May 2012

• curprev 23:2823:28, 11 May 2012 Helpful Pixie Bot talk contribs m 4,887 bytes +3 ISBNs (Build KH) undo

8 September 2011

• curprev 18:0318:03, 8 September 2011 Tmigler talk contribs 4,884 bytes +283 No edit summary undo

30 May 2011

• curprev 22:4022:40, 30 May 2011 80.202.100.34 talk 4,601 bytes +28 For maximization problems, the factor is 1 - ε, not 1 + ε, as that would give a better solution than the optimal undo

6 April 2011

• curprev 19:4519:45, 6 April 2011 Bender2k14 talk contribs 4,573 bytes +36 →Variants: added two subsections undo

3 April 2011

• curprev 22:2822:28, 3 April 2011 Yobot talk contribs m 4,537 bytes +53 WP:CHECKWIKI error 61 fixes + general fixes, References after punctuation per WP:REFPUNC and WP:PAIC using AWB (7671) undo

19 February 2011

• curprev 13:4413:44, 19 February 2011 77.3.117.165 talk 4,484 bytes +15 Corrected links to complexity zoo: qwiki.stanford.edu/wiki/... led to start page. qwiki.stanford.edu/index.php/ is the correct address. undo

23 November 2010

• curprev 17:3517:35, 23 November 2010 1.38.138.59 talk 4,469 bytes −1 an approximation scheme is a polynomial time approximation scheme if and only if for every fixed ε undo

20 October 2010

• curprev 13:5313:53, 20 October 2010 130.237.222.220 talk 4,470 bytes +14 No edit summary undo