arXiv:1706.02075v1 [math.OC] 7 Jun 2017

Approximate Shifted Combinatorial Optimization
Martin Koutecký

∗

Asaf Levin

†

Syed M. Meesum

‡

Shmuel Onn†§

Abstract
Shifted combinatorial optimization is a new nonlinear optimization framework, which
is a broad extension of standard combinatorial optimization, involving the choice of several feasible solutions at a time. It captures well studied and diverse problems ranging
from congestive to partitioning problems. In particular, every standard combinatorial
optimization problem has its shifted counterpart, which is typically much harder. Here
we initiate a study of approximation algorithms for this broad optimization framework.
Keywords: combinatorial optimization, packing problems, independence system, matroid, matching, approximation algorithms, linear optimization.

1

Introduction

The following optimization problem has been studied extensively in the literature.
(Standard) Combinatorial Optimization. Given S ⊆ {0, 1}d and w ∈ Zd , solve
max{ws : s ∈ S} .

(1)

The complexity of the problem depends on w and the type and presentation of S. Often,
S arises as the set of indicating vectors of members of a family of subsets over a ground set
[d] := {1, . . . , d} such as the family of matchings in a given graph with d edges or the set of
independent sets in a matroid over [d] given by an independence oracle. See [11] for a detailed
account of the literature and bibliography of thousands of articles on this problem.
In this article we study a broad nonlinear extension of this problem, which involves the
choice of several feasible solutions from S at a time, and which is defined as follows.
We denote the i-th row and j-th column of a matrix x by xi and xj respectively. For a
set S ⊆ Rd let S n be the set of d × n matrices having each column in S,
S n := {x ∈ Rd×n : xj ∈ S , j = 1, . . . , n} .
Call matrices x, y ∈ Rd×n equivalent and write x ∼ y if each row of x is a permutation of the
corresponding row of y. The shift of x ∈ Rd×n is the unique matrix x ∈ Rd×n satisfying x ∼ x
and x1 ≥ · · · ≥ xn , that is, the unique matrix equivalent to x with each row nonincreasing. We
∗

Charles University, Prague. Email: koutecky@kam.mff.cuni.cz
Technion - Israel Institute of Technology, Haifa. Email: levinas@ie.technion.ac.il
‡
Institute of Mathematical Sciences, HBNI, Chennai. Email: meesum@imsc.res.in
§
Technion - Israel Institute of Technology, Haifa. Email: onn@ie.technion.ac.il

†

1

2
say that a matrix x is shifted if x = x. We study the following broad nonlinear combinatorial
optimization problem (also called the shifting problem and denoted as SCO).
Shifted Combinatorial Optimization (SCO). Given S ⊆ {0, 1}d and c ∈ Zd×n , solve
max{cx : x ∈ S n } .

(2)

This problem has a very broad expressive power. In particular, every standard combinatorial optimization has its shifted counterpart which is typically much harder. For instance,
when S is given explicitly as a list of vectors, the standard problem is trivial, but the shifted
counterpart may be hard. To see this, let G be a graph with d edges and m vertices. Let
S := {s1 , . . . , sm } ⊆ {0, 1}d with sj the indicator of the set of edges incident on vertex j.
Define c ∈ Zd×n by ci,1 := 0 for all i and ci,j := −1 for all i and j ≥ 2. Then the optimal
objective value of the shifted problem is 0 if and only if G has an independent set of size n.
One interpretation of the problem is in terms of the social cost in a congestion game [10].
We are given a set S ⊆ {0, 1}d of indicators of members of a family over [d] as above. For
i = 1, . . . , d we are now given a function fi : {0, 1, . . . , n} → Z. Each x ∈ S n represents a
j
choice of n players
Pn i ∈ [d]
Pn with x ∈ S the choice of player j. The congestion of x at element
is the number j=1 xi,j of players using i in x. The cost of x at i is the value fi ( j=1 xi,j )
P
P
of fi on the congestion at i. The social cost of x is di=1 fi ( nj=1 xi,j ) and we want to find
x ∈ S n minimizing social cost. For instance, S may be the set of s − t dipaths in a digraph;
each player chooses a dipath; and the cost at edge i may be an increasing function fi of the
congestion at i. Now define c ∈ Zd×n by ci,j := fi (j − 1) − fi (j) for all i and j. Then for
P
P
P
every x ∈ S n we have cx = di=1 fi (0) − di=1 fi ( nj=1 xi,j ) and so x maximizes cx if and
only if it minimizes the social cost. So these congestion and shifted problems are equivalent.
In particular, a case of special interest is when the fi are convex, implying that the rows of c
are nonincreasing, that is, c = c is shifted. This case will be considered in Section 3.
Shifted combinatorial optimization has been introduced and studied recently in [3, 6, 8].
In [6] it was shown that for S = {s ∈ {0, 1}d : As ≤ b} presented by linear inequalities where
A is a totally unimodular matrix and b is integer, with shifted c, the shifting problem can be
solved in polynomial time. This in particular implies that shifting with shifted c can be solved
in polynomial time for S the set of matchings in a bipartite graph or the set of s−t dipaths in a
digraph. In [8] it was shown that with shifted c, for S the set of independent sets in a matroid
presented by a linear optimization oracle or S the intersection of two so-called strongly-baseorderable matroids, shifting with shifted c can again be done in polynomial time. Finally, in
[3] the parameterized complexity of the problem with S given explicitly and |S| as parameter
was studied, and it was also shown that shifted combinatorial optimization parameterized by
µ and τ over any property defined by any monadic-second-order-logic formula of length at
most µ over any graph of tree-width at most τ , is in the complexity class XP.
In this article we initiate a study of approximation algorithms for shifted combinatorial
optimization. We assume that S is an independence system, also called downward monotone,
namely, 0 ∈ S and if u ∈ {0, 1}d and u ≤ v ∈ S then u ∈ S. We assume that S is presented
by a linear optimization oracle that, queried on w ∈ Zd , returns s ∈ S maximizing ws, that
is, we can at least solve the standard combinatorial optimization problem over S to begin
with. For instance, S may be the independent sets in a matroid or the matchings in a graph.

3
The article is organized as follows. In Section 2 we discuss the complexity of the problem
for matchings. This is done via the so-called prescribed congestion problem which is of interest
on its own right. We show that for shifted c, shifting is hard already for n = 2 and matchings
in general graphs, and for general c, it is hard already for n = 2 and matchings in bipartite
graphs. This motivates the need in approximation algorithms for shifted combinatorial optimization over independence systems, which are developed in Sections 3 – 5. As usual, an
algorithm for a maximization problem has approximation ratio α if it always returns a feasible
solution with objective value that is at least α times the optimal objective value (that is, we
use the convention of α ≤ 1 for maximization problems). Also, an algorithm is polynomial
time if its running time including the number of calls to the oracle presenting S is polynomial.
In Section 3 we prove the following result (see therein for the precise statement).
Theorem 3.4. SCO for any shifted c and any independence system S can be approximated
in polynomial time with constant approximation ratio which is independent of n.
In Section 4 we prove the following result (see therein for the precise statement).
Theorem 4.3. SCO for any c and any independence system S can be approximated in
polynomial time with approximation ratio which is decreasing logarithmically in n.
In Section 5 we establish better approximation ratios for the small values n = 2, 3, 4.
We conclude our article in Section 6 with some final remarks.

2

The complexity of shifted matching

In this section we discuss the computational complexity of the shifted problem over matchings.
It is convenient to introduce first the following decision problem, of interest on its own right.
Prescribed Congestion Problem. Given S ⊆ {0, 1}d , n and C1 ,P
. . . , Cd ⊆ {0, 1, . . . , n},
n
decide if there is an x ∈ S whose congestion at i satisfies m(i, x) := nj=1 xi,j ∈ Ci for all i.
Lemma 2.1 The prescribed congestion problem reduces to shifting with c ∈ {−1, 0, 1}d×n .

Proof. Define functions fi on {0, 1, . . . , n} by fi (j) := 0 if j ∈ Ci and fi (j) := −1 if j 6∈ Ci .
Now define c ∈ {−1, 0, 1}d×n by ci,j := fi (j) − fi (j − 1) for i = 1, . . . , d and j = 1, . . . , n.
Consider any x ∈ S n . We then have


 


m(i,x)
d
d
d
d
n
X
X
X
X
X
X






c
c
=
fi
fi (0) = −|{i : 0 6∈ Ci }|
xi,j − fi (0) ≤ −
cx =
i xi =
i,j
i=1

i=1

j=1

with equality if and only if

i=1

Pn

j=1 xi,j

j=1

i=1

∈ Ci for all i. So the problem reduces to shifting.

The following theorem summarizes the complexity of the shifted matching problem.
Theorem 2.2 Consider the shifting problem max{cx : x ∈ S n } over the independence
system S ⊆ {0, 1}d of matchings in a given graph G with d edges and c ∈ Zd×n . We have:
1. For bipartite graphs and c = c shifted the problem is polynomial time solvable for all n.

4
2. For cubic graphs the problem is NP-hard already for c = c shifted and n = 2.
3. For bipartite graphs and arbitrary c the problem is NP-hard already for n = 2.
Before presenting the proof of the theorem, we will show the next lemma.
P P
Lemma 2.3 For any matrix z, let |z| :=
i
j |zi,j | and let k ∈ [d] be an integer. Let
Pd
d
d
T ⊆ {t ∈ {0, 1} :
i=1 ti = k} and let S := {s ∈ {0, 1} : s ≤ t for some t ∈ T } be the
independence system generated by T . Then, the shifting problem max{cx : x ∈ T n } over T
with c ∈ Zd×n reduces to the shifting problem max{bx : x ∈ S n } over S with b ∈ Zd×n defined
by bi,j := ci,j + 2|c| + 1 for all i, j.
Proof. Consider any x, y ∈ T n and any z ∈ S n \ T n . Then
bx = cx + (2|c| + 1)|x| = cx + (2|c| + 1)nk ≥ −|c| + (2|c| + 1)nk ,
bz = cz + (2|c| + 1)|z| ≤ |c| + (2|c| + 1)(nk − 1) .
So bx > bz hence an optimizer of bu over S n will be attained at T n . Also, bx − by = cx − cy
and so an optimal solution of bu over S n will also be an optimal solution of cu over T n .
We now return to prove Theorem 2.2.
Proof. Part 1 is proven in [6]. Note that the claim similar to Part 2 regarding perfect
matchings is shown in [8], here, for completeness, we will prove it for matchings. Let G be
a cubic graph with d edges. It is NP-complete to decide if G is 3-edge-colorable [5]. This
is equivalent to deciding if G has two edge-disjoint perfect matchings. This is equivalent to
the prescribed congestion problem with T ⊂ {0, 1}d the set of perfect matchings in G, n = 2
and Ci = {0, 1} for all i. This problem reduces by Lemma 2.1 to shifting over T with shifted
matrix c = c given by ci,1 = 0 and ci,2 = −1 for all i. By Lemma 2.3, this reduces to shifting
over the independence system S of all matchings in G with suitable b which is shifted since c
is. So this problem is NP-hard and Part 2 follows.
Finally, we prove Part 3. Let F1 , . . . , Fm ⊆ [k] be sets with all |Fi | = 3. It is NP-complete
to decide if [k] is partitionable by the Fi , that is, if ⊎i∈I Fi = [k] for some I ⊆ [m], see [2].
Construct a graph G with d := 12m edges and 6m+2k vertices as follows. For i = 1, . . . , m
include a 6-cycle (ui,1 , vi,1 , ui,2 , vi,2 , ui,3 , vi,3 ), which will be referred to as a hexagon. For each
j ∈ [k] include two vertices aj , bj . For any i ∈ [m], Fi = {r, s, t} for some 1 ≤ r < s < t ≤ k.
We introduce the six edges {ar , ui,1 }, {as , ui,2 }, {at , ui,3 }, {br , vi,1 }, {bs , vi,2 }, {bt , vi,3 } to the
graph, these edges will be referred to as non-hexagon edges. This graph is bipartite with the
ui,r , bj on one side and the vi,r , aj on the other side. We claim that the partitioning problem
reduces to the prescribed congestion problem with T ⊂ {0, 1}d the set of perfect matchings in
G, n = 2, and Ce = {0, 1} for each hexagon edge and Ce = {0, 2} for each non-hexagon edge.
Suppose I ⊆ [m] gives a partition ⊎i∈I Fi = [k]. Construct two perfect matchings M1 , M2
in G as follows. For each i ∈ I include in both M1 , M2 the six non-hexagon edges incident on
the vertices ui,r , vi,r . For each i 6∈ I include the three hexagon edges {ui,r , vi,r } in M1 and the
other three hexagon edges in M2 . Clearly each vertex ui,r , vi,r is incident on exactly one edge
in M1 and one in M2 . Now consider j ∈ [k]. Then j ∈ Fi for exactly one i ∈ I. So for exactly
one 1 ≤ r ≤ 3 we have that aj is incident in both M1 , M2 exactly once on {aj , ui,r } and bj is

5
incident in both M1 , M2 exactly once on {bj , vi,r }. So both M1 , M2 are perfect matchings in
G, and by the construction, the congestion on each edge e is in Ce .
Conversely, suppose M1 , M2 are two perfect matchings in G with the prescribed congestion
on each edge. Construct I ⊆ [m] as follows. Consider any i ∈ [m] and the corresponding
hexagon. Consider any two consecutive hexagon edges, say {ui,1 , vi,1 }, {vi,1 , ui,2 }. We claim
that both must have the same congestion under M1 ∪ M2 . Indeed, if one has congestion 0
and the other has congestion 1, then the congestion of the non-hexagon edge incident on
vi,1 must be 1, which is impossible. So either all edges of hexagon i have congestion 0 and
all non-hexagon edges touching it have congestion 2, in which case we include i in I, or all
edges of hexagon i have congestion 1 and all non-hexagon edges touching it have congestion
0, in which case we exclude i from I. Next, we prove that I is a solution to the partitioning
problem. For any j ∈ [k], consider any edge {aj , ui,r } incident on aj ; then j ∈ Fi . Now either
{aj , ui,r } has congestion 0 under M1 , M2 in which case all edges of hexagon i have congestion
1 and i 6∈ I, or this edge has congestion 2 in which case all edges of hexagon i have congestion
0 and i ∈ I. Since exactly one edge incident on aj has congestion 2, it follows that j is in
exactly one Fi with i ∈ I. So ⊎i∈I Fi = [k] is a partitioning.
Now this prescribed congestion problem reduces by Lemma 2.1 to the shifting problem
over T . By Lemma 2.3, this reduces in turn to shifted combinatorial optimization over the independence system S of all matchings in G. So this problem is NP-hard and Part 3 follows.

3

Constant approximation of monotone shifting

A matrix x ∈ {0, 1}d×n is orthogonal ifP
its columns are pairwise orthogonal, that is, have
disjoint supports, which is equivalent to nj=1 xj ∈ {0, 1}d . In our approximation algorithms
here and in Section 4 we will use the following problem over the orthogonal matrices in S n .
Disjoint Union Problem (DUP). Given S ⊆ {0, 1}d , positive integer n, and w ∈ Zd , solve
max{w

n
X
j=1

xj : x ∈ S n ,

n
X

xj ∈ {0, 1}d } .

(3)

j=1

Here and in Section 4 we will assume the existence of a polynomial time β-approximation
algorithm for DUP for some β ≤ 1. For β = 1 this means that DUP can be solved to optimality
in polynomial time; this holds for instance for the set of indicators of independent sets of a
matroid, the set of indicators of common independent sets in the intersection of two so-called
strongly-base-orderable matroids, or the set of {0, 1}-valued solutions to a system Ax ≤ b with
A a totally unimodular matrix and b an integer vector. However, DUP is generally NP-hard
(for instance, when S is the set of indicators of matchings in a graph, already for n = 2, see
proof of Theorem 2.2); so we will need the next lemma which follows from the classical result
of [1] on the greedy algorithm for the so-called maximum coverage problem.
Lemma 3.1 Given an independence system S ⊆ {0, 1}d presented by a linear optimization
oracle, positive integer n, and w ∈ Zd , we can find in polynomial time an orthogonal matrix
x ∈ S n which provides a β-approximation for DUP with ratio β = 1 − (1 − n1 )n ≥ 1 − 1e .

6
P
Pn
Proof. The maximum coverage problem is to find x ∈ S n maximizing {wi :
j=1 xi,j ≥ 1}.
0
0
The greedy algorithm for this problem is the following. Set w := w and x := 0. For
k = 1, . . . , n do: define wk ∈ Zd by wik := wik−1 if xik−1 = 0 and wik := 0 if xik−1 = 1;
query the linear optimization oracle of S on wk and obtain xk . Let x := [x1 , . . . , xn ] ∈ S n .
Then the classical result of [1] on the greedy algorithm guarantees that x has the claimed
approximation ratio for the maximum coverage problem, see also [4, page 136] for a short
illuminating analysis.
Pn Now let y be the orthogonal matrix obtained
Pnfrom x by zeroing out, in
each row i with j=1 xi,j ≥ 1, all entries but the first 1, so that j=1 yi,j = 1. Since S is an
independence system we have y ∈ S n and clearly for all orthogonal z ∈ S n we have
w

n
X
j=1

yj =

n
n
n
n
X
X
X
X
X
X
X
zj
zi,j ≥ 1} = βw
xi,j ≥ 1} ≥ β
{wi :
yi,j ≥ 1} =
{wi :
{wi :
j=1

j=1

j=1

j=1

so y is the desired greedily computable β-approximation for the disjoint union problem.
We proceed to show that for any shifted c ∈ Zd×n , that is, c = c having nonincreasing rows,
we can use the above to approximate max{cx : x ∈ S n } to within the same approximation
ratio β in polynomial time. Below we use some notation introduced in [8].
Define the n-lift of a set of vectors S ⊆ {0, 1}d to be the set of matrices
d×n

↑n S := {x ∈ {0, 1}

:

n
X

xj ∈ S} .

j=1

Clearly, if S is an independence system then so is ↑n S. Moreover, the following holds.
Lemma 3.2 A linear optimization oracle for ↑n S is efficiently realizable from one for S.
Proof. Let c ∈ Zd×n be given. For i = 1, . . . , d let j(i) and wi be such that wi = ci,j(i) =
max{ci,1 , . . . , ci,n }. Query the oracle of S on w = (w1 , . . . , wd ) and let s ∈ S be its answer.
Then x ∈↑n S defined by xi,j := sj if j = j(i) and xi,j := 0 otherwise is optimal for c.
Define the n-disjoint-union of a set M ⊆ {0, 1}U where U is any finite ground set to be
U

∨n M := {x ∈ {0, 1}

: ∃x1 , . . . , xn ∈ M , x =

n
X

xk } .

k=1

For M ⊆ {0, 1}d×n let [M ] be the set of matrices equivalent to some matrix in M ,
[M ] := {x ∈ {0, 1}d×n : ∃ y ∈ M , x ∼ y} .
The next lemma is form [8] and its proof can be found therein.
Lemma 3.3 For any set S ⊆ {0, 1}d and any n we have that [S n ] = ∨n ↑n S in {0, 1}d×n .
We can now prove the following result.

7
Theorem 3.4 There is a polynomial time algorithm that, given a shifted c ∈ Zd×n and an
independence system S ⊆ {0, 1}d presented by a linear optimization oracle, finds y ∈ S n with


1
1 n
n
cy ≥ β · max{cz : z ∈ S } ,
≥ 0.6321 .
≥1−
β =1− 1−
n
e
Proof. By Lemma 3.2 we can realize a linear optimization oracle for the independence system
M :=↑n S ⊆ {0, 1}d×n over the ground set U := [d] × [n]. We then consider the disjoint union
problem over M with n and w := c. By Lemma
3.1 we can find matrices x1 , . . . , xn ∈ M with
P
pairwise disjoint supports, that is, with nk=1 xk ∈ {0, 1}d×n , such that
c

n
X

xk ≥ β · max{c

k=1

n
X

v k : v 1 , . . . , vn ∈ M ,

k=1

n
X

vk ∈ {0, 1}d×n } .

k=1

P
For k = 1, . . . , n define a vector y k := nj=1 xjk and note that xk ∈↑n S implies y k ∈ S for all
P
k. Let x be the matrix x := nk=1 xk and let y ∈ S n be the matrix with columns y 1 , . . . , y n .
Consider any feasible solution z ∈ S n for the shifting problem. We claim the inequality
cy = cx ≥ cx ≥ βcz .
First, we have

n
X
j=1

x

j

=

n X
n
X
j=1 k=1

xjk

=

n
n X
X

xjk

(4)

=

k=1 j=1

n
X

yk .

k=1

This implies x ∼ y and y = x, and so the left equality of (4) follows. Second, c is shifted,
that is, nonincreasing, and so by a trivial exchange argument, the middle inequality of (4)
follows. Third, by Lemma 3.3 we have that z ∈ S n implies z ∈ [S n ] = ∨n ↑n S = ∨n M , and
hence by the choice of x1 , . . . , xn ,
cx ≥ β · max{cv : v ∈ ∨n M } ≥ βcz ,
which is the right inequality of (4). So inequality (4) holds throughout which implies that y
is the desired β-approximation for the shifted combinatorial optimization problem.

4

Logarithmic approximation of shifting

In this section we develop our approximation algorithm for SCO with arbitrary matrix c.

4.1

The cleaning procedure

P
Given a feasible solution x to SCO, for i ∈ [d], we let m(i, x) = j xi,j be the congestion
Pm(i,x)
of i in x; we let fi (x) = ci xi = j=1 ci,j be the profit of x from element i, and thus the
P
P
goal is to find x ∈ S n that maximizes cx = i∈[d] fi (x); we let Pi (x) = maxℓ≤m(i,x) ℓj=1 ci,j
be the potential P
profit of x from element i, and a maximizer in the last maximum is denoted
as p(i, x). Let i∈[d] Pi (x) be the total potential profit of x. Then we have the following
observation that follows by a cleaning post-processing phase:

8
Lemma 4.1 There exists a polynomial time algorithm that takes as an input a feasible solution x ∈ S n to SCO and returns a feasible solution x′ ∈ S n such that the objective function
value of x′ as a solution to SCO equals the total potential profit of x.
Proof. We modify x as follows. We go over all elements and for each element i ∈ [d] we
compute m(i, x) − p(i, x) and if this is strictly positive, we replace exactly m(i, x) − p(i, x) 1’s
in the i-th row of x with 0’s. In the resulting matrix that we denote by x′ , the congestion of
i is exactly p(i, x) (for every i ∈ [d]). Thus, the objective function value of x′ as a solution to
SCO is exactly the total potential profit of x. The feasibility of x′ follows by our assumption
that x ∈ S n , x′ ≤ x, and S is downward monotone.
The procedure described in the proof of the last lemma of transforming the solution x
into the solution x′ will be named the cleaning procedure applied on x.

4.2

The approximation algorithm for SCO

The algorithm we present to approximate SCO chooses one of ⌈log2 n⌉ + 1 solutions. That
is, the following procedure is applied for ℓ = 0, 1, . . . , ⌈log 2 n⌉ with k(ℓ) = ⌊ 2nℓ ⌋ for ℓ ≤ log2 n
and k(ℓ) = 1 for ℓ > log2 n. For each such value of ℓ, we compute its corresponding k(ℓ) and
construct a feasible solution to SCO as described below. Last, we choose the best solution
among all the solutions we computed.
In the iteration for a fixed value of ℓ and its corresponding k(ℓ) we use the β approximation
algorithm for approximating DUP over S with the positive integer k(ℓ) standing for the
required number of columns
in the output of DUP and the weight vector w ∈ Zd defined as
Pq
wi = maxq≤min{2ℓ ,n} j=1 ci,j the maximum profit that can be achieved from element i by
covering it by at most 2ℓ times. We denote by y(ℓ) the matrix of dimension d × k(ℓ) returned
by the approximation algorithm for DUP.
If ℓ ≤ log2 n, then we replace each column of y(ℓ) by 2ℓ copies of the same column and
we add another n − k(ℓ) · 2ℓ = n − ⌊ 2nℓ ⌋ · 2ℓ ≥ 0 zero columns to get a feasible solution for
SCO and otherwise if ℓ > log2 n we have k(ℓ) = 1 and we replace the unique column of y(ℓ)
by n copies of the same column to obtain a feasible solution for SCO. In either case we have
computed a feasible solution for SCO on which we apply the cleaning procedure to obtain
our ℓ-th candidate solution AP Xℓ whose objective function value (as a solution for SCO) is
denoted by apxℓ .
Our output is the solution AP Xℓ for the value of ℓ for which apxℓ is maximized. We denote
by apx = maxℓ apxℓ the objective function value of the solution returned by the algorithm.

4.3

The analysis

Next, we turn into the analysis of this algorithm. Let o be an optimal solution for SCO. Recall
that for i ∈ [d], m(i, o) is the number of columns in o that cover i, that is, the congestion of
i in o. For ℓ = 0, 1, . . . , ⌈log2 n⌉ we let
O(ℓ) =

X

i∈[d]:2ℓ−1 <m(i,o)≤2ℓ

fi (o)

9
be the total reward of o from elements that are covered more than 2ℓ−1 times and at most 2ℓ
times, we let
S(ℓ) = {i ∈ [d] : 2ℓ−1 < m(i, o) ≤ 2ℓ }
be the set of elements that contribute to the value of O(ℓ), and for i ∈ [d] we let q(i) be the
index such that i ∈ S(q(i)).
Then, we have that the value of o as a solution to SCO denoted as OP T satisfies
⌈log2 n⌉

OP T =

X

O(ℓ).

ℓ=0

In the next lemma we prove lower bounds on apx in terms of {O(ℓ)}ℓ .
Lemma 4.2 For every ℓ = 0, 1, . . . , ⌈log2 n⌉, we have
apx ≥ apxℓ ≥ β ·

X

S
i∈ ℓq=0 S(q)



 ℓ−q(i)+3
 ℓ−q+3
ℓ
X
1
1
.
fi (o) ·
=β·
O(q) ·
2
2
q=0

Proof. Note that we have
 ℓ−q+3
 ℓ−q+3 X
ℓ
X
1
1
fi (o) ·
=
=
O(q) ·
2
2
q=0
q=0

ℓ
X

i∈S(q)

X

i∈∪ℓq=0 S(q)

 ℓ−q(i)+3
1
,
fi (o) ·
2

and thus the last equality in the statement of the lemma holds.
Consider the n columns of o. We choose uniformly at random k(ℓ) columns of o and
construct a feasible solution to SCO based on these chosen columns. First, if the chosen
columns are not pairwise disjoint, we make them disjoint by replacing some of the 1’s by
0’s (we replace a minimum number of such 1’s, and thus do not change the set of elements
that are covered by at least one chosen column). So we obtain a collection of k(ℓ) pairwise
disjoint columns. Second, we take min{n, 2ℓ } copies of each column in the collection of disjoint
columns. If ℓ < log2 n, then we augment this collection of columns by n−k(ℓ)·2ℓ zero columns.
Then we apply the cleaning procedure on the matrix of dimensions d × n we obtained, and
denote the resulting matrix by o′ . Observe that o′ is a random variable, and thus for i ∈ [d],
fi (o′ ) is also a random variable whose expected value is denoted as E(fi (o′ )).
Observe that the objective function value of o′ as a solution to SCO is exactly the objective
function value of the collection
of disjoint
P
 columns as a solution to DUP. Therefore, we know
′
that apx ≥ apxℓ ≥ β ·
i∈[d] E(fi (o )) . Thus, it suffices to show
X

′

E(fi (o )) ≥

X

i∈∪ℓq=0 S(q)

i∈[d]

 ℓ−q(i)+3
1
,
fi (o) ·
2

and thus it suffices to show that for every i ∈ ∪ℓq=0 S(q), we have
 ℓ−q(i)+3
1
E(fi (o )) ≥ fi (o) ·
.
2
′

10
Consider such i ∈ ∪ℓq=0 S(q), and let q = q(i). By the cleaning procedure, we conclude
that if i is covered by (at least) one chosen column, then the realization of fi (o′ ) is at least
fi (o). Thus, it suffices to show that the probability that i is covered by at least one chosen
ℓ−q+3
.
column is at least 12
For t = 1, 2, . . . k(ℓ), we define a random variable Xt that equals 1 if the t-th chosen
Pk(ℓ)
column covers the element i and it equals 0 otherwise. Let X = t=1 Xt . Then, we need to
ℓ−q+3
. To do that, we will use Chernoff bound.
show that the probability P r(X 6= 0) ≥ 21
First, note that


2q−1
2q−1
,
=
E(Xt ) = P r(Xt = 1) = 1 − P r(Xt = 0) ≥ 1 − 1 −
n
n
and thus using k(ℓ) = max{1, ⌊ 2nℓ ⌋} ≥

n
,
2ℓ+1

we have

n
2q−1
2q−1
≥ ℓ+1 ·
=
E(X) ≥ k(ℓ) ·
n
2
n

 ℓ−q+2
1
.
2

1
We use Lemma 5.27 in [12] to conclude that P r(X = 0) < e−( 2 )
bility that i is covered by at least one chosen column is at least
 ℓ−q+3
ℓ−q+2
1
−( 21 )
,
P r(X 6= 0) > 1 − e
≥
2

ℓ−q+2

. Thus, the proba-

2

where the last inequality holds because for every 0 < z < 1 we have e−z ≤ 1−z + z2 < 1− z2 .
We are now in position to prove the following main result.
Theorem 4.3 There is a polynomial time algorithm that, given any c ∈ Zd×n and any independence system S ⊆ {0, 1}d presented by a linear optimization oracle, finds y ∈ S n with
cy ≥

β
· max{cz : z ∈ S n } ,
4 · ⌈log2 n⌉ + 8

where β = 1 − (1 − n1 )n ≥ 1 − 1e ≥ 0.6321 is the approximation ratio of the greedy algorithm
for the disjoint union problem over S, and if DUP is solvable in polynomial time, then β = 1.
Proof. We consider the
family of constraintsthat we proved in Lemma 4.2. That is, for every
P

ℓ
1 ℓ−q+3
ℓ we have apx ≥ β ·
. We multiply the constraint corresponding to
q=0 O(q) · 2
ℓ = ⌈log2 n⌉ by 2, and we sum up all the constraints. Thus, we obtain
⌈log2 n⌉

(⌈log2 n⌉ + 2) · apx ≥ β ·

X
ℓ=0

1
O(ℓ) · .
4

To see that indeed the coefficient of every O(ℓ) in the resulting sum is β · 41 note that the
coefficient is the result of a sum of geometric sequence whose ratio is 12 , the largest element
in the sequence is β8 , and the smallest element appears twice. These properties hold for every
value of ℓ, and every such sequence of numbers has sum of β4 .

11

5

Improved approximations for small values of n

Here, we would like to analyze the approximation ratio of our approximation algorithm of
Section 4 and variants of it for small values of n. Thus, we will show that the analysis can be
tightened further for these values. We note that similar improvements are possible also for
larger values of n. To illustrate the improvements, we consider the cases where n = 2, 3, 4.
We use the approximation algorithm for DUP and Lemma 3.1 for several values of k ≤ n.

5.1

The case n = 2

Assume that n = 2, we will apply the algorithm of Section 4 for ℓ = 0 with k(0) = 2, and
for ℓ = 1 with k(1) = 1. Using the notation of Section 4, we will prove the following lower
bounds on apx.
Lemma 5.1 We have apx ≥ apx1 ≥

1
2

· O(0) + O(1) and apx ≥ apx0 ≥ βO(0).

Proof. For the first bound, observe that for k = 1, we can solve DUP in polynomial time
using the linear optimization oracle. We pick one column of o uniformly at random. Using
the proof of Lemma 4.2, it suffices to show that for an element i ∈ [d] the probability that
the chosen column covers i is at least 12 if m(i, o) = 1 and 1 if m(i, o) = 2. This last claim
holds because we pick each of the two columns in o with probability 12 .
Similarly, if we pick the ortogonal matrix obtained from o as a solution to DUP with
k = 2, then we are guaranteed to get a solution to DUP of value at least O(0). Since we can
approximate DUP within an approximation ratio of β, the claim follows.
Using the two inequalities in the last lemma we get
apx · (1 +

1
) ≥ O(0) + O(1) = OP T,
2β

and thus the approximation ratio of the algorithm is

1
1
1+ 2β

=

Thus, the approximation ratio of the algorithm for n = 2 is

2β
2β+1
3
5.

where β = 1− (1− 21 )2 = 34 .

Theorem 5.2 The approximation ratio of the algorithm for n = 2 is

5.2

3
5

.

The case n = 3

Here we apply similar arguments to the case n = 2. We apply our approximation algorithm
for ℓ = 0 with k(0) = 3, and for ℓ = 1 with k(1) = 1. For the case ℓ = 1, we note that we can
solve the instance of DUP in polynomial time optimally, whereas for ℓ = 0, we approximate
1 3
19
the instance of DUP
P within a factor of β = 1 − (1
P− 3 ) = 27 . Here, we modify our notation
and let O(0) = i∈[d]:m(i,o)=1 fi (o), and O(1) = i∈[d]:m(i,o)∈{2,3} fi (o).
We prove the following lower bounds on apx.
Lemma 5.3 We have apx ≥ apx1 ≥

1
3

· O(0) +

2
3

· O(1) and apx ≥ apx0 ≥ βO(0).

12
Proof. For the first bound, we pick one column of o uniformly at random. Using the proof
of Lemma 4.2, it suffices to show that for an element i ∈ [d] the probability that the chosen
column covers i is 13 if m(i, o) = 1 and at least 32 if m(i, o) ∈ {2, 3}. This last claim holds
because we pick each of the three columns in o with probability 13 .
For the second bound, if we pick the ortogonal matrix obtained from o as a solution to
DUP with k = 3, then we are guaranteed to get a solution to DUP of value at least O(0).
Since we can approximate DUP within an approximation ratio of β, the claim follows.
By multiplying the inequality apx ≥ 31 ·O(0)+ 23 ·O(1) by 32 we get 23 ·apx ≥ 12 ·O(0)+O(1).
1
times the inequality apx ≥ βO(0) ,we get
Then by adding 2β


3
1
+
2 2β



· apx ≥ O(0) + O(1) = OP T,

and thus the approximation ratio of the algorithm for n = 3 is

1


3
+ 1
2 2β

Theorem 5.4 The approximation ratio of the algorithm for n = 3 is

5.3



=

2β
3β+1

=

19
42 .

19
42 .

The case n = 4

We apply our approximation algorithm for ℓ = 0 with k(0) = 4, for ℓ = 1 with k(1) = 2, and
for ℓ = 2 with k(2) = 1. For the case ℓ = 2, we note that we can solve the instance of DUP in
polynomial time optimally, whereas for ℓ = 1, we approximate the instance of DUP within a
factor of 1 − (1 − 21 )2 = 34 , and for ℓ = 0, we approximate the instance of DUP
P within a factor
of 1 − (1P− 41 )4 = 175
.
Here,
we
use
our
original
notation
and
let
O(0)
=
i∈[d]:m(i,o)=1 fi (o),
256
P
O(1) = i∈[d]:m(i,o)=2 fi (o), and O(2) = i∈[d]:m(i,o)∈{3,4} fi (o).
We prove the following lower bounds on apx.
1
3
1
Lemma 5.5 We have
4 · O(2), apx ≥ apx1 ≥
 3apx ≥ apx5 2 ≥ 4 · O(0) + 2 · O(1) +175
5
1
2 · O(0) + 6 · O(1) = 8 · O(0) + 8 · O(1), and apx ≥ apx0 ≥ 256 · O(0).

3
4

·

Proof. For the first bound, we pick one column of o uniformly at random. Using the proof
of Lemma 4.2, it suffices to show that for an element i ∈ [d] the probability that the chosen
column covers i is 14 if m(i, o) = 1, it is 21 if m(i, o) = 2, and it is at least 34 if m(i, o) ∈ {3, 4}.
This last claim holds because we pick each of the four columns in o with probability 14 .
For the second bound, recall that we approximate the corresponding DUP instance within
a factor of 43 . We pick a pair of distinct columns of o uniformly at random. Using the proof
of Lemma 4.2, it suffices to show that for an element i ∈ [d] the probability that at least one
chosen column covers i is 12 if m(i, o) = 1 and it is 56 if m(i, o) = 2. This last claim holds
because we choose each pair of columns with equal probability (that is, 61 ) , and there is only
one pair of columns that does not cover an element i ∈ [d] with m(i, o) = 2.
For the last bound, if we pick the ortogonal matrix obtained from o as a solution to DUP
with k = 4, then we are guaranteed to get a solution to DUP of value at least O(0). Since we
can approximate DUP within an approximation ratio of 175
256 , the claim follows.

13
We multiply the constraint apx ≥ 14 · O(0) + 12 · O(1) + 43 · O(2) by 43 , we multiply the
8
175
, and we multiply the constraint apx ≥ 256
· O(0)
constraint apx ≥ 83 · O(0) + 58 · O(1) by 15

1792
4
8
by 2625 . Last we sum up the resulting three constraints to get that apx · 3 + 15 + 1792
2625 ≥
6692
= apx · 2625
≥ OP T , and we conclude
O(0) + O(1) + O(2) = OP T . Thus apx · 3500+1400+1792
2625
the following theorem.
Theorem 5.6 The approximation ratio of the algorithm for n = 4 is

6

2625
6692

∼ 0.392259.

Remarks

First, we point out the following possible generalization of shifted optimization, which in the
congestion games context of [10] corresponds to an individual set of strategies for each player.
We have a matrix c ∈ Zd×n as before, but are now given n sets S1 , . . . , Sn ⊆ {0, 1}d rather
than one. The generalized shifted optimization problem is then max{cx : xk ∈ Sk }. However,
we note that this problem becomes hard quickly. Let n = 3 and let S1 , S2 , S3 be matroids of
common rank r. Let ci,1 := ci,2 := 0 and ci,3 := 1 for all i. Then the optimal value of this
generalized shifted problem is r if and only if the three matroids have a common basis. It is
easy to construct three matroids from a given digraph that have a common basis if and only
if the digraph has an s − t Hamiltonian path, which is hard to decide, see [9, Chapter 2].
Another possible generalization of the problem is the following. We have one nonempty
S ⊆ {0, 1}d as before, but are now given a function f : {0, 1, . . . , n}d → Z. The objective
value of x ∈ S n is f evaluated
P at the vector whose i-th component is the congestion of x at
i. So the problem is max{f ( nj=1 xj ) : x ∈ S n }. Assuming S 6= ∅ we have the following.
Proposition 6.1 If f is convex then there is an optimal solution x having identical columns,
and so the generalized shifted problem reduces to solving max{f (ns) : s ∈ S} over the set S.

Proof. Assume f is convex and let x̂ be an optimal solution to the generalized shifted problem.
Let s1 , . . . , sm ∈ S be the distinct columns of x̂. Define a d × m matrix M := [s1 , . . . , sm ] and
a function g : Zm → Z by g(y) := f (M y), which is convex since f is. Consider the integer
simplex Y := {y ∈ Zm
+ : y1 + · · · + ym = n} and the auxiliary problem max{g(y) : y ∈ Y }.
For each y ∈ Y let x(y) := [s1 , . . . , s1 , . . . , sm , . . . , sm ] ∈ S n be the d × n matrix consisting of
yi copies of si . Permuting the columns of x̂ we may assume that x̂ = x(ŷ) for some ŷ ∈ Y .
Now, g is convex, so the auxiliary problem has an optimal solution which is a vertex of Y ,
namely, a multiple ỹ = n1i of a unit vector in Zm . It then follows that x̃ := x(ỹ) = [si , . . . , si ]
is the desired optimal solution for the shifted problem, proving the proposition, since
n
n
X
X
j
x̂j ) .
x̃ ) = f (M ỹ) = g(ỹ) ≥ g(ŷ) = f (M ŷ) = f (
f(
j=1

j=1

Finally we note that our work in this article is part of a more general line of study of the
possibility of amplifying linear to nonlinear optimization over independence systems. In [7]
this line was also considered, for a certain family of nonlinear multicriteria problems. It was
shown therein that under some assumptions, a so termed r-best solution, having the property
that at most r better objective values can be attained by other solutions, can be obtained
in polynomial time. It was also shown therein that under milder assumptions, exponentially

14
many queries to the linear optimization oracle presenting the independence system may be
required. See [9, Chapter 6] and references therein for more details on this line of research.

Acknowledgment
M. Koutecký was partially supported by the project 17-09142S of the Czech Science Foundation. A. Levin was partially supported by a Grant from GIF - the German-Israeli Foundation
for Scientific Research and Development. S.M. Meesum was partially supported by a grant
at the Technion. S. Onn was partially supported by the Dresner Chair at the Technion.

References
[1] Cornuejols G., Fisher M.L., Nemhauser G.L.: Location of bank accounts to optimize float:
an analytic study of exact and approximate algorithms. Management Science 23:789–810
(1977)
[2] Dyer M.E., Frieze A.M.: Planar 3DM is NP-complete. Journal of Algorirhns 7:174–184
(1986)
[3] Gajarský J., Hliněný P., Koutecký M., Onn S.: Parameterized shifted combinatorial optimization. Proceedings of the 23rd Annual International Computing and Combinatorics
Conference (2017), Lecture Notes in Computer Science, Springer, to appear.
[4] Hochbaum D.S.: Approximation Algorithms for NP-Hard Problems. PWS Publishing
Company (1997)
[5] Holyer I.: The NP-Completeness of Edge-Coloring. SIAM Journal on Computing 10:718–
720 (1981)
[6] Kaibel V., Onn S., Sarrabezolles P.: The unimodular intersection problem. Operations
Research Letters 43:592–594 (2015)
[7] Lee J., Onn S., Weismantel R.: Approximate nonlinear optimization over weighted independence systems. SIAM Journal on Discrete Mathematics 23:1667–1681 (2009)
[8] Levin A., Onn S.: Shifted matroid optimization. Operations Research Letters 44:535–539
(2016)
[9] Onn S.: Nonlinear Discrete Optimization. Zurich Lectures in Advanced Mathematics, European Mathematical Society (2010), http://ie.technion.ac.il/∼onn/Book/NDO.pdf
[10] Rosenthal R.R.: A class of games possessing pure-strategy Nash-equilibria. International
Journal of Game Theory 2:65–67 (1973)
[11] Schrijver A.: Combinatorial Optimization. Springer (2003)
[12] Williamson D.P. and Shmoys D.B.: The Design of Approximation Algorithms. Cambridge University Press (2011)

