Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Probabilistic Analysis:
TR06-092 | 5th July 2006
Matthias Englert, Heiko Röglin, Berthold Vöcking

Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP

2-Opt is probably the most basic and widely used local search
heuristic for the TSP. This heuristic achieves amazingly good
results on "real world" Euclidean instances both with respect to
running time and approximation ratio. There are numerous
experimental studies on the performance of 2-Opt. However, the
theoretical knowledge about ... more >>>

TR20-156 | 22nd October 2020
Sankeerth Rao Karingula, Shachar Lovett

Codes over integers, and the singularity of random matrices with large entries

Revisions: 1

The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be ... more >>>

ISSN 1433-8092 | Imprint