|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Analysis of the Karmarkar-Karp Differencing Algorithm | | Stefan Boettcher
; Stephan Mertens
; | | Date: |
27 Feb 2008 | | Abstract: | The Karmarkar-Karp differencing algorithm is the best known polynomial time
heuristic for the number partitioning problem, fundamental in both theoretical
computer science and statistical physics. We analyze the performance of the
differencing algorithm on random instances by mapping it to a nonlinear rate
equation. Our analysis reveals strong finite size effects that explain why the
precise asymptotics of the differencing solution is hard to establish by
simulations. The asymptotic series emerging from the rate equation satisfies
all known bounds on the Karmarkar-Karp algorithm and projects a scaling
$n^{-cln n}$, where $c=1/(2ln2)=0.7213...$. Our calculations reveal subtle
relations between the algorithm and Fibonacci-like sequences, and we establish
an explicit identity to that effect. | | Source: | arXiv, 0802.4040 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER