Transcript slides

On Completing Latin Squares
Iman Hajirasouliha
Joint work with
Hossein Jowhari, Ravi Kumar, and Ravi Sundaram
1
Definitions



What is a Latin Square and a
Partial Latin Square (PLS)?
The PLSE problem: Given a
PLS, fill the maximum number
of empty cells using numbers
in [n] without violating the
constraints.
1
2
4
2
3
1
4
4
2
3
1
3
2
4
The k-PLSE problem: How
many empty cells of a PLS
can be filled properly using at
most k ≤ n different numbers?
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
2
Motivations and Applications

Interesting object for mathematicians,
Evans conjecture(1960) says that a PLS
with n-1 filled cells can be completed.
(Proved by Smetaniuk in 1981)

Sudoku puzzles, one of the current fads,
are PLSs with additional properties.

The problem has application in errorcorrecting codes and recently optical
networks.
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
3
Previous and New Results

The PLSE problem is NP-Complete (Colbourn 1984)
The PLSE problem is APX-hard (This paper)

1-1/e+ε hardness for the k-PLSE problem. (This paper)

Problem Approx.
factor
Authors, Year
Technique
PLSE
1/2
Kumar, Russell,
Sundaram, 1995
Combinatorial ideas
PLSE
1-1/e
Gomes, Regis, Shmoys, LP and Randomized
2003
Rounding
PLSE
2/3-ε
This paper
Local Search
k-PLSE
1-1/e-ε
This paper
LP and Randomized
Rounding
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
4
A problem equivalent to PLSE

The 3EDM Problem: finding the number of maximum
edge disjoint triangles in a tripartite simple graph.
columns
a
a
b
1
2
b
2
3
c
d
4
1
c
d
rows
4
1
4
2
3
3
a
a
b
b
c
c
d
d
1
numbers
2
3
4
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
5
Local Search Algorithm for 3EDM

Let G be an instance of 3EDM



Fix a constant t ≥ 7.
Start from any arbitrary valid solution.
If possible, replace s ≤ t triangles in the current
solution with s+1 edge-disjoint triangles to get
another valid solution.
Since the size of solution increases in each step by
one, the algorithm runs in polynomial time.
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
6
Local Search Analysis



Let T={T1,…, Tm} be the set of
edge disjoint triangles of OPT and
T’={T’1,…, T’n} be the set of
triangles found by the heuristic.
Construct a bipartite graph H with
vertex set T  T’.
Connect Ti and T’j in H, iff Ti
and T’j share an edge in G.
T1
T’1
T2
T’2
.
.
.
Tm
T’n
H
Optimal TrianglesLocal Search
Triangles
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
7
Hurkens-Schrijver Theorem:


Let H be a bipartite graph with vertex set X  Y;
|X|=n, |Y|=m.
Let k ≥3 and assume:


For each y in Y, deg (y) ≤ k.
Every subset of size ≤ t of X has a system of distinct
representatives in Y.
Then:
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
8
PLSE and H-S Theorem


H satisfies the Hurkens-Schrijver
conditions.
 deg (T’j) ≤ 3 for each T’j.
 Every subset of size t in T has
a
System of Distinct Representation in
T’ (due to local search).
T1
T’1
T2
T’2
Setting k=3, we get the 2/3-ε bound.
Tm
.
.
.
For t=7 we beat the previous result:
m k (k  1) r  k 3*16  3
1



r
n 2(k  1)  k 2*16  3 1  1
e
T’n
H
Optimal
Triangles
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
Local Search
Triangles
9
The k-PLSE problem

How many cells of a PLS can be filled using at most
k ≤ n different numbers?
A natural greedy algorithm:
Repeat k times:
Pick the number c which can fill the most cells.
Fill those cells with c.
The greedy algorithm is a ½ - approximation algorithm.
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
10
Greedy algorithm analysis

OPT solution and greedy solution are sets of
triples {(i, j, k)}. To each triple y in OPT, we
assign a triple x in greedy solution as
accountable.
Given y=(i, j, k) in OPT, we have three cases:
1) cell x=(i, j, t) is in Greedy. x is accountable for y.
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
11
2) (i, j) is empty in Greedy but k has been used in
Greedy. We can assign a distinct x=(i’, j’, k) in Greedy to
y. Consider the iteration where Greedy chooses k.
Cells with number 1 in OPT
Cells with number 1 in Greedy
1
1
1
1
1
1
1
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
12
3) cell (i, j) is empty in Greedy and number k is
missing in Greedy. For each number c in OPT we can
assign a number c’ in Greedy which is missing in
OPT.
OPT
1
2
4
1
2
Greedy
4
4
4
Red cells in OPT are mapped to Yellow cells in Greedy
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
13
LP relaxation of the problem



A way to extend the
PLS with a number
represents a matching.
Mc is the set of all
matchings that extends
the PLS with number c.
ycM is 1 when Matching
M is chosen.
Introduction, 2/3-ε Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
14
1-1/e-ε approximation
1. Solve the LP program.
2. Multiply the variables by 1-ε.
3. For each number pick a matching randomly according
to the probability associated with the matchings.
4. If matchings intersect in a cell, choose one of them
arbitrarily for the cell.


Expectation of the size of solution obtained is bigger
than (1-1/e-ε)LPOPT
With a constant probability, at most k numbers have
been picked.
Introduction, 2/3 Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
15
Conclusion


We defined a new and natural variation of the
PLSE problem and obtained simple
approximation algorithms for the PLSE and
k-PLSE problems.
Our results for the PLSE problem is an
improvement and for the k-PLSE problem is
the best possible.
Introduction, 2/3 Approx. for PLSE, 1-1/e-ε Approx. for k-PLSE, Conclusion
16