An improved approximation algorithm for the partial Latin square extension problem.

DOI10.1016/j.orl.2003.09.007zbMath1078.68160OpenAlexW2046019946MaRDI QIDQ703265

David B. Shmoys, Carla P. Gomes, Rommel G. Regis

Publication date: 11 January 2005

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2003.09.007

zbMATH Keywords

Latin squareRandomized roundingApproximation algorithm

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorics in computer science (68R05) Orthogonal arrays, Latin squares, Room squares (05B15) Approximation algorithms (68W25)

Related Items (2)

A massively parallel evolutionary algorithm for the partial Latin square extension problem ⋮ Iterated local search with Trellis-neighborhood for the partial Latin square extension problem

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of completing partial Latin squares
• Latin squares. New developments in the theory and applications
• Approximating latin square extensions
• Geometric algorithms and combinatorial optimization.
• Clique partitions, graph compression and speeding-up algorithms
• Open Shop Scheduling to Minimize Finish Time
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Fast Approximation Algorithms for Fractional Packing and Covering Problems

This page was built for publication: An improved approximation algorithm for the partial Latin square extension problem.