Redução linear

Em Ciência da Computação, em particular no estudo de algoritmos de aproximação, uma L-redução ("redução linear") é uma transformação de problemas de otimização que linearmente preservam características de aproximação. Nos estudos de aproximação de problemas de otimização as reduções lineares desempenham um papel semelhante ao de reduções polinomiais no estudos da complexidade computacional de problemas de decisão.

O termo L-redução é por vezes utilizado para se referir a reduções em espaço logarítmico, por analogia com a classe de complexidade L, mas isto é um conceito diferente.

Definição

Sejam A e B problemas de otimização e cA e cB suas respetivas funções de custo. Um par de funções f e g é uma L-redução se todas as seguintes condições são encontradas:

  • funções f e g são computáveis em tempo polinomial,
  • se x é uma instância do problema A, então f(x) é uma instância do problema B,
  • se y é a solução para f(x), então g(y) é a solução para x,
  • existe uma constante positiva α tal que
,
  • existe uma constante positiva β tal que para toda solução y para f(x)
.

Propriedades

Seja f uma (1±ε)-algoritmo de aproximação para o problema A tal que é no máximo distante de , para toda instância de x. (Nesta notação, + implicitamente significa um problema de minimização, e significa um problema de maximização.)

O ponto principal de uma L-redução é o seguinte: dado uma (f,g,α,β) L-redução do problema A para o problema B, e um (1±ε)-algoritmo de aproximação para B, nós obtemos em tempo polinomial um (1±δ)-algoritmo de aproximação para A onde .[1][2] Isto implica que se B tem um esquema de aproximação em tempo polinomial (PTAS) então A também terá.

Ver também

Referências

  1. ↑ Kann, Viggo (1992). On the Approximability of NP-complete Optimization Problems. [S.l.]: Royal Institute of Technology, Sweden. ISBN 91-7170-082-X 
  2. ↑ Christos H. Papadimitriou; Mihalis Yannakakis (1988). «Optimization, Approximation, and Complexity Classes». STOC '88: Proceedings of the twentieth annual ACM Symposium on Theory of Computing. doi:10.1145/62212.62233 
  • Pierluigi Crescenzi: A Short Guide to Approximation Preserving Reductions. In: Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, June 24-27, 1997, Ulm, Germany. Pages 262-273. IEEE Computer Society Press, 1997. ISBN 0-8186-7907-7
  • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complexity and Approximation. Combinatorial optimization problems and their approximability properties. 1999, Springer. ISBN 3-540-65431-3
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.

Read other articles:

Çandarlı Halil Pasha yang Muda

Çandarlı HalilPasha Wazir Agung Kesultanan Utsmaniyah ke-11Masa jabatan1439 – 1 Juni 1453Penguasa monarkiMurad IIMehmed II PendahuluKoca Mehmed Nizamüddin PashaPenggantiZaganos Pasha Informasi pribadiMeninggal10 Juli 1453Konstantinopel, Kesultanan UtsmaniyahKebangsaan TurkiDihukum mati Mehmed IISunting kotak info • L • B Çandarlı Halil Pasha (meninggal 10 Juli 1453), yang dikenal dengan julukan Yang Muda, adalah Wazir Agung Kesultanan Utsmaniyah yang sangat berpe...

 

Atletica leggera

Atletica leggeraVeduta parziale di uno stadio con annesse pista outdoor e pedaneFederazioneWorld Athletics InventatoAntica Grecia Componenti di una squadraSport individuale(eccetto che per le staffette nelle quali gareggiano 3 o 4 atleti per squadra) ContattoNo GenereMaschile e femminile Indoor/outdoorIndoor e outdoor Olimpicodal 1896 Manuale L'atletica leggera è un insieme di svariate discipline sportive che possono essere raggruppate in quattro categorie: corse, marcia, concorsi (salti...

 

Dyaus Pita

Untuk nama dewa tertinggi Proto-Indo-Eropa, lihat Dyeus. Dyaus PitaDewa LangitNama lainAkashaAfiliasiDewa, Pancha BhootaKediamanDyuloka, Sky (ākāśa, आकाश)PustakaRegwedaPrithviKeturunanSurya, Ushas, dan dewa lainnyaYunaniZeusRomawiJupiter Bagian dari seriAgama Hindu Umat Sejarah Topik Sejarah Mitologi Kosmologi Dewa-Dewi Keyakinan Brahman Atman Karmaphala Samsara Moksa Ahimsa Purushartha Maya Filsafat Samkhya Yoga Mimamsa Nyaya Waisesika Wedanta Dwaita Adwaita Wisistadwaita Pustaka ...

Howell Cobb

American politician (1815–1868) For other uses, see Howell Cobb (disambiguation). Howell CobbPresident of the Confederate States Provisional CongressIn officeFebruary 4, 1861 – February 18, 1862Preceded byPosition establishedSucceeded byPosition abolished22nd United States Secretary of the TreasuryIn officeMarch 7, 1857 – December 8, 1860PresidentJames BuchananPreceded byJames GuthrieSucceeded byPhilip Thomas40th Governor of GeorgiaIn officeNovember 5, 1851 –...

 

'n Beetje

n BeetjePerwakilan Kontes Lagu Eurovision 1959NegaraBelandaArtisTeddy ScholtenBahasaBelandaKomposerDick Schallies[1]Penulis lirikWilly van HemertKonduktorDolf van der LindenHasil FinalHasil final1Poin di final21Kronologi partisipasi◄ Heel de wereld (1958)   Wat een geluk (1960) ► ‘n Beetje (Sebuah gigitan kecil),[2] yang berjudul lengkap Een Beetje, adalah lagu pemenang Kontes Lagu Eurovision 1959. Dipentaskan dalam bahasa Belanda oleh Teddy Scholten, lagu ter...

 

American Enterprise Institute

American conservative think tank founded in 1938 American Enterprise InstituteAEI's headquarters near DuPont Circle in Washington, D.C.AbbreviationAEIFormation1938; 86 years ago (1938)TypePublic policy think tankTax ID no. 53-0218495HeadquartersWashington, D.C.LocationUnited StatesCoordinates38°54′33″N 77°02′29″W / 38.909230°N 77.041470°W / 38.909230; -77.041470PresidentRobert DoarRevenue (2020) $43.5 million[1]Expenses (2020)$47.8...

Trebišov

Lambang kota Kastil Kastil dan museum Trebišov (bahasa Hungaria: Tőketerebes, bahasa Jerman: Trebischau) merupakan sebuah kota industri kecil di Slowakia bagian timur. Kota ini berpenduduk 22.934 jiwa (31 Desember 2004) dan merupakan ibu kota Distrik Trebišov. Sejarah Penyebutan pertama dalam dokumen tertulis berasal dari tahun 1254 (sebagai Terebus). Desa ini diberi nama yang sejarang pada tahun 1330, setelah penganugerahan hak kota. Pada abad ke-14, kastil dan desa sekitarnya menjadi sat...

 

Ultimate Jet

Airline of the United States This article needs to be updated. Please help update this article to reflect recent events or newly available information. (November 2023) Ultimate Jet IATA ICAO Callsign UE UJC ULTIMATE Founded2009; 15 years ago (2009)Commenced operationsJuly 2009 (2009-07)[1]Fleet size8Parent companyUltimate JetHeadquartersNorth Canton, Ohio, U.S.WebsiteOfficial Website Ultimate Jet, formerly Ultimate Jet Charters, is a private jet charter cha...

 

William Reeves

Artikel ini perlu dikembangkan agar dapat memenuhi kriteria sebagai entri Wikipedia.Bantulah untuk mengembangkan artikel ini. Jika tidak dikembangkan, artikel ini akan dihapus. William ReevesReeves pada Desember 2011 di kampus PixarLahirToronto, Ontario, KanadaTempat kerjaPixar Animation StudiosSuami/istriRicki BlauAnakJulia, Oliver, & Ian Reeves William Bill Reeves adalah seorang animator dan pengarah teknikal asal Kanada, Ia dikenal karena berkarya dengan John Lasseter pada film-film pe...

Pensacola International Airport

International airport in Pensacola, Florida, United States Not to be confused with Naval Air Station Pensacola. Pensacola International AirportIATA: PNSICAO: KPNSFAA LID: PNSWMO: 72222SummaryAirport typePublicOwnerCity of PensacolaServesPensacola, Florida and Mobile, AlabamaElevation AMSL121 ft / 37 mCoordinates30°28′24″N 087°11′12″W / 30.47333°N 87.18667°W / 30.47333; -87.18667Websitewww.FlyPensacola.comMapsFAA airport diagramRunways Directi...

 

Присоединение Литвы к СССР

См. также: Присоединение Прибалтики к СССР Присоединение Литвы к СССР — политический процесс в истории Литвы, приведший Литовскую Республику к включению её в состав СССР. Период нахождения республики в составе СССР самой Литвой, странами Балтии и многими другими стра...

 

Hugh Edwin Munroe

Canadian politician The HonourableHugh Edwin MunroeOBEHugh Edwin Munroe during his time as Lieutenant Governor of Saskatchewan.5th Lieutenant Governor of SaskatchewanIn officeMarch 31, 1931 – September 10, 1936MonarchsGeorge VEdward VIIIGovernors GeneralThe Earl of WillingdonThe Earl of BessboroughThe Lord TweedsmuirPremierJ.T.M. AndersonJames G. GardinerWilliam John PattersonPreceded byHenry William NewlandsSucceeded byArchibald Peter McNab Personal detailsBorn(1878-05-31)May ...

Lewi Pethrus

Swedish minister and hymnwriter (1884–1974) PastorLewi PethrusLewi Pethrus in 1937BornPethrus Lewi Johansson(1884-03-11)11 March 1884Vargön, Västra Tunhem, Älvsborg, SwedenDied4 September 1974(1974-09-04) (aged 90)Stockholm, SwedenEducationBethel Seminary (Betelseminariet) in StockholmSpouseLydia Danielsen This article is part of a series onConservatism in Sweden Ideologies Christian democracy Liberal Moderate Nationalist Principles Cameralism Duty Elitism Meritocracy Law and order ...

 

Edamitsu Station

Railway station in Kitakyushu, Japan JA  24  Edamitsu Station枝光駅 General informationLocation2-chōme-1 Edamitsu, Yahatahigashi-ku, Kitakyushu-shi, Fukuoka-ken 805-0002JapanCoordinates33°52′45″N 130°48′46″E / 33.879167°N 130.812875°E / 33.879167; 130.812875Operated by JR KyushuLine(s)JA Kagoshima Main Line Distance20.0 km from MojikōPlatforms2 side platformsTracks2ConstructionStructure typeElevatedOther informationStatusStaffedWebsiteOf...

 

Taiping Rebellion

Major rebellion in China (1850–1864) This article may be in need of reorganization to comply with Wikipedia's layout guidelines. Please help by editing the article to make improvements to the overall structure. (May 2024) (Learn how and when to remove this message) Taiping RebellionPart of the Century of HumiliationTop: An 1884 painting of the Battle of Anqing (1861)Bottom: Naval battle between Taiping and Qing on YangtzeDateDecember 1850 – August 1864LocationChinaResult Qing victoryBelli...

Jazz in India

Indian music genre Tyagaraju known for his extensive contributions to Carnatic music. Music of India Genres Traditional Classical Carnatic Odissi Hindustani Folk Borgeet Baul Bhajan Kirtana Shyama Sangeet Ramprasadi Rabindra Sangeet Nazrul Geeti Dwijendrageeti Atulprasadi Prabhat Samgiita Thumri Dadra Chaiti Kajari Sufi Ghazal Qawwali Sikh Modern Bhangra Bhangragga Filmi Bollywood Ghazal Qawwali Goa trance Dance Indi-pop Asian Underground Jazz Rock Bengali Raga Hip hop Media and performance M...

 

Chiesa di San Carpoforo (Milano)

Chiesa di San CarpoforoFacciata più recente della chiesa di San CarpoforoStato Italia RegioneLombardia LocalitàMilano, via Formentini 10 IndirizzoVia Formentini, 10 e Via Formentini 10 Coordinate45°28′18.25″N 9°11′11.1″E45°28′18.25″N, 9°11′11.1″E Religionecattolica di rito ambrosiano Arcidiocesi Milano Consacrazioneante 813 Sconsacrazione24 dicembre 1787 FondatoreSanta Marcellina Inizio costruzioneV secolo Modifica dati su Wikidata · Manuale La chiesa di San C...

 

Acidi carbossilici

Modello molecolare di un acido carbossilico:R gruppo alchilico      carbonio      ossigeno      idrogeno Gli acidi carbossilici sono una classe di molecole organiche che contengono uno o più gruppi carbossilici (−COOH o −CO2H). A seconda della struttura legata al gruppo carbossilico, possono essere molecole alifatiche, eterocicliche, aromatiche, sia sature sia insature.[1][2] Indice 1 Nomenclatura ...

Cedilla

Diacritical mark (¸) Cedille redirects here. For the record label, see Cedille Records. Not to be confused with Sedilia. For the similar looking diacritics, see Ogonek and Diacritical comma. You can help expand this article with text translated from the corresponding article in French. (July 2020) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as nec...

 

Tension oculaire

Cet article est une ébauche concernant la médecine. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Pour les articles homonymes, voir PIO et IOP. Patient dont on mesure la tension oculaire au moyen d'un tonomètre. La tension oculaire (également appelée pression intra-oculaire ou PIO ; en anglais, Intraocular pressure ou IOP) correspond à la pression régnant à l'intérieur du globe oculaire, qui est ...