Displaying similar documents to “Correspondence between two antimatroid algorithmic characterizations.”

Census algorithms for chinese remainder pseudorank

David Laing, Bruce Litow (2008)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We investigate the density and distribution behaviors of the chinese remainder representation pseudorank. We give a very strong approximation to density, and derive two efficient algorithms to carry out an exact count (census) of the bad pseudorank integers. One of these algorithms has been implemented, giving results in excellent agreement with our density analysis out to 5189 -bit integers.

On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications

Evripidis Bampis, R. Giroudeau, J.-C. König (2002)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

We consider the unit execution time unit communication time ( UET-UCT ) scheduling model with hierarchical communications [1], and we study the impact of the hierarchical communications hypothesis on the hardness of approximation. We prove that there is no polynomial time approximation algorithm with performance guarantee smaller than 5 / 4 (unless 𝒫 = 𝒩𝒫 ). This result is an extension of the result of Hoogeveen et al. [6] who proved that there is no polynomial time ρ -approximation algorithm with...

Continuous reformulations and heuristics for the euclidean travelling salesperson problem

Tuomo Valkonen, Tommi Kärkkäinen (2009)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

We consider continuous reformulations of the euclidean travelling salesperson problem (TSP), based on certain clustering problem formulations. These reformulations allow us to apply a generalisation with perturbations of the Weiszfeld algorithm in an attempt to find local approximate solutions to the euclidean TSP.