Large deviation based upper bounds for the LCS-problem
We analyse and apply a large deviation and Montecarlo simulation based method for the computation of improved upper bounds on the Chvatal-Sankoff constant for i.i.d. random sequences over a finite alphabet. Our theoretical results show that this method converges to the exact value of when a control...
| প্রধান লেখক: | , , |
|---|---|
| বিন্যাস: | Report |
| প্রকাশিত: |
Unspecified
2003
|
| _version_ | 1826300788069105664 |
|---|---|
| author | Hauser, R Martinez, S Matzinger, H |
| author_facet | Hauser, R Martinez, S Matzinger, H |
| author_sort | Hauser, R |
| collection | OXFORD |
| description | We analyse and apply a large deviation and Montecarlo simulation based method for the computation of improved upper bounds on the Chvatal-Sankoff constant for i.i.d. random sequences over a finite alphabet. Our theoretical results show that this method converges to the exact value of when a control parameter converges to infinity. We also give upper bounds on the complexity for numerically computing the Chvatal-Sankoff constant to any given precision via this method. Our numerical experiments confirm the theory and allow us to give new upper bounds that are correct to two digits. |
| first_indexed | 2024-03-07T05:22:28Z |
| format | Report |
| id | oxford-uuid:df6344ff-6be9-41a4-b1f7-4a6c295535a2 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:22:28Z |
| publishDate | 2003 |
| publisher | Unspecified |
| record_format | dspace |
| spelling | oxford-uuid:df6344ff-6be9-41a4-b1f7-4a6c295535a22022-03-27T09:39:03ZLarge deviation based upper bounds for the LCS-problemReporthttp://purl.org/coar/resource_type/c_93fcuuid:df6344ff-6be9-41a4-b1f7-4a6c295535a2Mathematical Institute - ePrintsUnspecified2003Hauser, RMartinez, SMatzinger, HWe analyse and apply a large deviation and Montecarlo simulation based method for the computation of improved upper bounds on the Chvatal-Sankoff constant for i.i.d. random sequences over a finite alphabet. Our theoretical results show that this method converges to the exact value of when a control parameter converges to infinity. We also give upper bounds on the complexity for numerically computing the Chvatal-Sankoff constant to any given precision via this method. Our numerical experiments confirm the theory and allow us to give new upper bounds that are correct to two digits. |
| spellingShingle | Hauser, R Martinez, S Matzinger, H Large deviation based upper bounds for the LCS-problem |
| title | Large deviation based upper bounds for the LCS-problem |
| title_full | Large deviation based upper bounds for the LCS-problem |
| title_fullStr | Large deviation based upper bounds for the LCS-problem |
| title_full_unstemmed | Large deviation based upper bounds for the LCS-problem |
| title_short | Large deviation based upper bounds for the LCS-problem |
| title_sort | large deviation based upper bounds for the lcs problem |
| work_keys_str_mv | AT hauserr largedeviationbasedupperboundsforthelcsproblem AT martinezs largedeviationbasedupperboundsforthelcsproblem AT matzingerh largedeviationbasedupperboundsforthelcsproblem |