An improved approximation algorithm for the partial Latin square extension problem.
DOI10.1016/J.ORL.2003.09.007zbMATH Open1078.68160OpenAlexW2046019946MaRDI QIDQ703265FDOQ703265
Authors: Carla P. Gomes, Rommel G. Regis, David B. Shmoys 
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
Recommendations
- On Completing Latin Squares
- Approximating latin square extensions
- An approximation algorithm for the partial covering 0-1 integer program
- An efficient local search for partial Latin square extension problem
- Iterated local search with Trellis-neighborhood for the partial Latin square extension problem
Combinatorics in computer science (68R05) Approximation algorithms (68W25) Integer programming (90C10) Orthogonal arrays, Latin squares, Room squares (05B15)
Cites Work
- Geometric algorithms and combinatorial optimization.
- The complexity of completing partial Latin squares
- Title not available (Why is that?)
- 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
- Latin squares. New developments in the theory and applications
- Title not available (Why is that?)
- Clique partitions, graph compression and speeding-up algorithms
- Approximating latin square extensions
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
Cited In (5)
- On residual approximation in solution extension problems
- An efficient local search for partial Latin square extension problem
- On Completing Latin Squares
- 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
This page was built for publication: An improved approximation algorithm for the partial Latin square extension problem.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703265)
