翻訳と辞書 Words near each other ・ L-O-V-E ・ L-O-V-E (album) ・ L-O-V-E (Love) ・ L-olivosyl-oleandolide 3-O-methyltransferase ・ L-Orizzont ・ L-packet ・ L-peptidase ・ L-Photo-Leucine ・ L-pipecolate dehydrogenase ・ L-pipecolate oxidase ・ L-plan castle ・ L-plate ・ L-pop ・ L-proline amide hydrolase ・ L-R-G / The Maze / S II Examples ・ L-reduction ・ L-rhamnonate dehydratase ・ L-rhamnono-1,4-lactonase ・ L-rhamnose 1-dehydrogenase ・ L-rhamnose isomerase ・ L-Ribonucleic acid aptamer ・ L-ribulose-5-phosphate 3-epimerase ・ L-ribulose-5-phosphate 4-epimerase ・ L-Ron ・ L-saccharopine oxidase ・ L-selectin ・ L-selectride ・ L-series ・ L-serine ammonia-lyase ・ L-serine dehydratase Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク L-reduction ： ウィキペディア英語版 L-reduction In computer science, particularly the study of approximation algorithms, an L-reduction ("''linear reduction''") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preserving reduction. L-reductions in studies of approximability of optimization problems play a similar role to that of polynomial reductions in the studies of computational complexity of decision problems. The term ''L reduction'' is sometimes used to refer to log-space reductions, by analogy with the complexity class L, but this is a different concept. ==Definition== Let A and B be optimization problems and cA and cB their respective cost functions. A pair of functions ''f'' and ''g'' is an L-reduction if all of the following conditions are met: * functions ''f'' and ''g'' are computable in polynomial time, * if ''x'' is an instance of problem A, then ''f''(''x'') is an instance of problem B, * if ''y' '' is a solution to ''f''(''x''), then ''g''(''y' '') is a solution to ''x'', * there exists a positive constant α such that :$\backslash mathrm(f(x))\; \backslash le\; \backslash alpha\; \backslash mathrm(x)$, * there exists a positive constant β such that for every solution ''y' '' to ''f''(''x'') :$|\backslash mathrm(x)-c\_A(g(y\text{'}))|\; \backslash le\; \backslash beta\; |\backslash mathrm(f(x))-c\_B(y\text{'})|$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「L-reduction」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.