برچسب: الگوریتم های قطعی تقریب NCP

Deterministic Approximation Algorithms for the Nearest Codeword Problem

ترجمه مقاله الگوریتم های تخمین قطعی، برای مسئله ی نزدیک ترین رمزواژه

دسته : فناوری اطلاعات

---

چکیده

مسئله ی نزدیک ترین رمز واژه(NCP)، در نظریه ی کدهای تصحیح خطا، یک سوال الگوریتمی میباشد. در یک نقطه ی ، و یک فضای خطی ، با ابعادk، NCP به دنبال یک نقطه ی  بوده، که این نقطه، فاصله ی  تا v را کمینه می­کند. مسئله ی نزدیک ترین رمزواژه، یک مسئله ی NP-hard میباشد. بنابراین، در این زمینه، الگوریتم های تقریب، مورد توجه میباشد. کارآمدترین الگوریتم های تقریب برای NCP، تا به امروز، مربوط به Bermn و Karpinski میباشد. اینها  الگوریتم ها به ترتیب، یک الگوریتم قطعی بوده که به یک نسبت تقریبِ  برای ثابت دلخواه c نائل شده و یک الگوریتم تصادفی میباشد که به نسبت تقریب  نائل میشود.

در این مقاله، ما الگوریتم های قطعی را برای تقریب NCP ارائه میدهیم، که در مقایسه با کارهای قبلی، به طور قابل ملاحظه ای بهبود یافته است.

فهرست مطالب

1-مقدمه

2-الگوریتم تقریبO(n/ Loog n)

3-یک الگوریتم تقریب  O(k log^(s) n/ log n) بازگشتی

4-مسئله ی نقطه از راه دور

5-نتیجه گیری

6-مراجع

 

Abstract

The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point and a linear space dimension k NCP asks to find a point that minimizes the (Hamming) distance from v: It is well-known that the nearest codeword problem is NP-hard. Therefore approximation algorithms are of interest. The best e_cient approximation algorithms for the NCP to date are due to Berman and Karpinski. They are a deterministic algorithm that achieves an approximation ratio of for an arbitrary constant ; and a randomized algorithm that achieves an approximation ratio of . In this paper we present new deterministic algorithms for approximating the NCP that improve substantially upon the earlier work

Contents

1. Introduction
2. An O(n/ log n)-approximation algorithm
3. A recursive O(k log^(s) n/ log n)-approximation algorithm
4. The remote point problem
5. Conclusion

6.References