Integer Programming and Combinatorial Optimization

Lattice-based reformulation techniques have been used successfully both theoretically and computationally. One such reformulation is obtained from the lattice ker

ℤ

(

A

) = {

x

 ∈ ℤ

n

|

Ax

 = 

0

}. Some of the hard instances in the literature that have been successfully tackled by lattice-based techniques, such as market split and certain classes of knapsack instances, have randomly generated input

A

. These instances have been posed to stimulate algorithmic research. Since the considered instances are very hard even in low dimension, less experience is available for larger instances. Recently we have studied larger instances and observed that the LLL-reduced basis of ker

ℤ

(

A

) has a specific sparse structure. In particular, this translates into a map in which some of the original variables get a “rich” translation into a new variable space, whereas some variables are only substituted in the new space. If an original variable is important in the sense of branching or cutting planes, this variable should be translated in a non-trivial way. In this paper we partially explain the obtained structure of the LLL-reduced basis in the case that the input matrix

A

consists of one row

a

. Since the input is randomly generated our analysis will be probabilistic. The key ingredient is a bound on the probability that the LLL algorithm will interchange two subsequent basis vectors. It is worth noticing that computational experiments indicate that the results of this analysis seem to apply in the same way also in the general case that

A

consists of multiple rows. Our analysis has yet to be extended to this general case. Along with our analysis we also present some computational indications that illustrate that the probabilistic analysis conforms well with the practical behavior.

We study a variant of the

generalized assignment problem

(

gap

) which we label

all-or-nothing

gap

(

agap

)

. We are given a set of items, partitioned into

n

groups, and a set of

m

bins. Each item ℓ has size

s

ℓ

 > 0, and utility

a

ℓ

j

 ≥ 0 if packed in bin

j

. Each bin can accommodate at most one item from each group, and the total size of the items in a bin cannot exceed its capacity. A group of items is

satisfied

if all of its items are packed. The goal is to find a feasible packing of a subset of the items in the bins such that the total utility from satisfied groups is maximized. We motivate the study of

agap

by pointing out a central application in scheduling advertising campaigns.

Our main result is an

O

(1)-approximation algorithm for

agap

instances arising in practice, where each group consists of at most

m

/2 items. Our algorithm uses a novel reduction of

agap

to maximizing submodular function subject to a matroid constraint. For

agap

instances with fixed number of bins, we develop a randomized

polynomial time approximation scheme (PTAS)

, relying on a non-trivial LP relaxation of the problem.

We present a (3 + 

ε

)-approximation as well as PTASs for other special cases of

agap

, where the utility of any item does not depend on the bin in which it is packed. Finally, we derive hardness results for the different variants of

agap

studied in the paper.

The

Unsplittable Flow Problem on a Path

(UFPP) is a core problem in many important settings such as network flows, bandwidth allocation, resource constraint scheduling, and interval packing. We are given a path with capacities on the edges and a set of tasks, each task having a demand, a profit, a source and a destination vertex on the path. The goal is to compute a subset of tasks of maximum profit that does not violate the edge capacities.

In practical applications generic approaches such as integer programming (IP) methods are desirable. Unfortunately, no IP-formulation is known for the problem whose LP-relaxation has an integrality gap that is provably constant. For the unweighted case, we show that adding a few constraints to the standard LP of the problem is sufficient to make the integrality gap drop from Ω(

n

) to

O

(1). This positively answers an open question in [Chekuri et al., APPROX 2009].

For the general (weighted) case, we present an extended formulation with integrality gap bounded by 7 + 

ε

. This matches the best known approximation factor for the problem [Bonsma et al., FOCS 2011]. This result exploits crucially a technique for embedding dynamic programs into linear programs. We believe that this method could be useful to strengthen LP-formulations for other problems as well and might eventually speed up computations due to stronger problem formulations.

Balas introduced intersection cuts for mixed integer linear sets. Intersection cuts are given by closed form formulas and form an important class of cuts for solving mixed integer linear programs. In this paper we introduce an extension of intersection cuts to mixed integer conic quadratic sets. We identify the formula for the conic quadratic intersection cut by formulating a system of polynomial equations with additional variables that are satisfied by points on a certain piece of the boundary defined by the intersection cut. Using a software package from algebraic geometry we then eliminate variables from the system and get a formula for the intersection cut in dimension three. This formula is finally generalized and proved for any dimension. The intersection cut we present generalizes a conic quadratic cut introduced by Modaresi, Kilinc and Vielma.

We empirically study the exponential potential function (EPF) approach to linear programming (LP), as applied to optimizing content placement in a video-on-demand (VoD) system. Even instances of modest size (e.g., 50 servers and 20k videos) stretch the capabilities of LP solvers such as CPLEX. These are packing LPs with block-diagonal structure, where the blocks are fractional uncapacitated facility location (UFL) problems. Our implementation of the EPF framework allows us to solve large instances to 1% accuracy 2000x faster than CPLEX, and scale to instances much larger than CPLEX can handle on our hardware.

Starting from the packing LP code described by Bienstock [4], we add many innovations. Our most interesting one uses priority sampling to shortcut lower bound computations, leveraging fast block heuristics to magnify these benefits. Other impactful changes include smoothing the duals to obtain effective Lagrangian lower bounds, shuffling the blocks after every round-robin pass, and better ways of searching for OPT and adjusting a critical scale parameter. By documenting these innovations and their practical impact on our testbed of synthetic VoD instances designed to mimic the proprietary instances that motivated this work, we aim to give a head-start to researchers wishing to apply the EPF framework in other practical domains.

We give an algorithm for testing the extremality of a large class of minimal valid functions for the two-dimensional infinite group problem.

The problem of covering minimum cost common bases of two matroids is NP-complete, even if the two matroids coincide, and the costs are all equal to 1. In this paper we show that the following special case is solvable in polynomial time: given a digraph

D

 = (

V

,

A

) with a designated root node

r

 ∈ 

V

and arc-costs

c

:

A

 → ℝ, find a minimum cardinality subset

H

of the arc set

A

such that

H

intersects every minimum

c

-cost

r

-arborescence. The algorithm we give solves a weighted version as well, in which a nonnegative weight function

w

:

A

 → ℝ

 + 

is also given, and we want to find a subset

H

of the arc set such that

H

intersects every minimum

c

-cost

r

-arborescence, and

w

(

H

) is minimum. The running time of the algorithm is

O

(

n

3

T

(

n

,

m

)), where

n

and

m

denote the number of nodes and arcs of the input digraph, and

T

(

n

,

m

) is the time needed for a minimum

s

 − 

t

cut computation in this digraph. A polyhedral description is not given, and seems rather challenging.

We give new algorithms for the minimum (weighted) clique cover in a claw-free perfect graph

G

, improving the complexity from

O

(|

V

(

G

)|

5

) to

O

(|

V

(

G

)|

3

). The new algorithms build upon neat reformulations of the problem: it basically reduces either to solving a 2-SAT instance (in the unweighted case) or to testing if a polyhedra associated with the edge-vertex incidence matrix of a bidirected graph has an integer solution (in the weighted case). The latter question was elegantly answered using neat polyhedral arguments by Schrijver in 1994. We give an alternative approach to this question combining pure combinatorial arguments (using techniques from 2-SAT and shortest paths) with polyhedral ones. Our approach is inspired by an algorithm from the Constraint Logic Programming community and we give as a side benefit a formal proof that the corresponding algorithm is correct (apparently answering an open question in this community). Interestingly, the systems we study have properties closely connected with the so-called Edmonds-Johnson property and we study some interesting related questions.

We analyze three fundamental variants of the bilevel knapsack problem, which all are complete for the second level of the polynomial hierarchy. If the weight and profit coefficients in the knapsack problem are encoded in unary, then two of the bilevel variants are solvable in polynomial time, whereas the third is NP-complete. Furthermore we design a polynomial time approximation scheme for this third variant, whereas the other two variants cannot be approximated in polynomial time within any constant factor (assuming P≠NP).

In the classic

k

-center problem, we are given a metric graph, and the objective is to open

k

nodes as centers such that the maximum distance from any vertex to its closest center is minimized. In this paper, we consider two important generalizations of

k

-center, the matroid center problem and the knapsack center problem. Both problems are motivated by recent content distribution network applications. Our contributions can be summarized as follows:

1

We consider the matroid center problem in which the centers are required to form an independent set of a given matroid. We show this problem is NP-hard even on a line. We present a 3-approximation algorithm for the problem on general metrics. We also consider the outlier version of the problem where a given number of vertices can be excluded as the outliers from the solution. We present a 7-approximation for the outlier version.

2

We consider the (multi-)knapsack center problem in which the centers are required to satisfy one (or more) knapsack constraint(s). It is known that the knapsack center problem with a single knapsack constraint admits a 3-approximation. However, when there are at least two knapsack constraints, we show this problem is not approximable at all. To complement the hardness result, we present a polynomial time algorithm that gives a 3-approximate solution such that one knapsack constraint is satisfied and the others may be violated by at most a factor of 1 + 

ε

. We also obtain a 3-approximation for the outlier version that may violate the knapsack constraint by 1 + 

ε

.

In optimization problems such as integer programs or their relaxations, one encounters feasible regions of the form

$\{x\in\mathbb{R}_+^n:\: Rx\in S\}$

where

R

is a general real matrix and

S

 ⊂ ℝ

q

is a specific closed set with 0 ∉ 

S

. For example, in a relaxation of integer programs introduced in [ALWW2007],

S

is of the form ℤ

q

 − 

b

where

$b \not\in \mathbb{Z}^q$

. One would like to generate valid inequalities that cut off the infeasible solution

x

 = 0. Formulas for such inequalities can be obtained through cut-generating functions. This paper presents a formal theory of minimal cut-generating functions and maximal

S

-free sets which is valid independently of the particular

S

. This theory relies on tools of convex analysis.

We introduce the

reverse Chvátal-Gomory rank

r

*

(

P

) of an integral polyhedron

P

, defined as the supremum of the Chvátal-Gomory ranks of all rational polyhedra whose integer hull is

P

. A well-known example in dimension two shows that there exist integral polytopes

P

with

r

*

(

P

) = + ∞. We provide a geometric characterization of polyhedra with this property in general dimension, and investigate upper bounds on

r

*

(

P

) when this value is finite. We also sketch possible extensions, in particular to the reverse split rank.

Split cuts form a well-known class of valid inequalities for mixed-integer programming problems (MIP). Cook et al. (1990) showed that the split closure of a rational polyhedron

P

is again a polyhedron. In this paper, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We also show how this result can be used to prove that some generalizations of split cuts, namely cross cuts, also yield closures that are rational polyhedra.

In the

Packing Interdiction

problem we are given a packing LP together with a separate interdiction cost for each LP variable and a global interdiction budget. Our goal is to harm the LP: which variables should we forbid the LP from using (subject to forbidding variables of total interdiction cost at most the budget) in order to minimize the value of the resulting LP? Interdiction problems on graphs (interdicting the maximum flow, the shortest path, the minimum spanning tree, etc.) have been considered before; here we initiate a study of interdicting packing linear programs. Zenklusen showed that matching interdiction, a special case, is NP-hard and gave a 4-approximation for unit edge weights. We obtain an constant-factor approximation to the matching interdiction problem without the unit weight assumption. This is a corollary of our main result, an

O

(log

q

· min {

q

, log

k

})-approximation to Packing Interdiction where

q

is the row-sparsity of the packing LP and

k

is the column-sparsity.

In this paper we study valid inequalities for a set that involves a continuous vector variable

x

 ∈ [0,1]

n

, its associated quadratic form

x

x

T

, and binary indicators on whether or not

x

 > 0. This structure appears when deriving strong relaxations for mixed integer quadratic programs (MIQPs). Valid inequalities for this set can be obtained by lifting inequalities for a related set without binary variables (

QPB

), that was studied by Burer and Letchford. After closing a theoretical gap about

QPB

, we characterize the strength of different classes of lifted

QPB

inequalities. We show that one class,

lifted-posdiag-QPB inequalities

, capture no new information from the binary indicators. However, we demonstrate the importance of the other class, called

lifted-concave-QPB inequalities

, in two ways. First, all lifted-concave-QPB inequalities define the relevant convex hull for the case of

convex

quadratic programming with indicators. Second, we show that all

perspective constraints

are a special case of lifted-concave-QPB inequalities, and we further show that adding the perspective constraints to a semidefinite programming relaxation of convex quadratic programs with binary indicators results in a problem whose bound is equivalent to the recent optimal diagonal splitting approach of Zheng

et al.

. Finally, we show the separation problem for lifted-concave-QPB inequalities is tractable if the number of binary variables involved in the inequality is small. Our study points out a direction to generalize perspective cuts to deal with non-separable nonconvex quadratic functions with indicators in global optimization. Several interesting questions arise from our results, which we detail in our concluding section.

The Asymmetric Traveling Salesperson Path (ATSPP) problem is one where, given an

asymmetric

metric space (

V

,

d

) with specified vertices

s

and

t

, the goal is to find an

s

-

t

path of minimum length that visits all the vertices in

V

.

This problem is closely related to the Asymmetric TSP (ATSP) problem, which seeks to find a tour (instead of an

s

-

t

path) visiting all the nodes: for ATSP, a

ρ

-approximation guarantee implies an

O

(

ρ

)-approximation for ATSPP. However, no such connection is known for the

integrality gaps

of the linear programming relxations for these problems: the current-best approximation algorithm for ATSPP is

O

(log

n

/loglog

n

), whereas the best bound on the integrality gap of the natural LP relaxation (the subtour elmination LP) for ATSPP is

O

(log

n

).

In this paper, we close this gap, and improve the current best bound on the integrality gap from

O

(log

n

) to

O

(log

n

/loglog

n

). The resulting algorithm uses the structure of narrow

s

-

t

cuts in the LP solution to construct a (random) tree witnessing this integrality gap. We also give a simpler family of instances showing the integrality gap of this LP is at least 2.

Consider a binary matroid

M

given by its matrix representation. We show that if

M

is a lift of a graphic or a co-graphic matroid, then in polynomial time we can either solve the single commodity flow problem for

M

or find an obstruction for which the Max-Flow Min-Cut relation does not hold. The key tool is an algorithmic version of Lehman’s Theorem for the set covering polyhedron.

We study a general

stochastic probing

problem defined on a universe

V

, where each element

e

 ∈ 

V

is “active” independently with probability

p

e

. Elements have weights {

w

e

:

e

 ∈ 

V

} and the goal is to maximize the weight of a chosen subset

S

of active elements. However, we are given only the

p

e

values—to determine whether or not an element

e

is active, our algorithm must

probe

e

. If element

e

is probed and happens to be active, then

e

must irrevocably be added to the chosen set

S

; if

e

is not active then it is not included in

S

. Moreover, the following conditions must hold in every random instantiation:

the set

Q

of probed elements satisfy an “outer” packing constraint,

the set

S

of chosen elements satisfy an “inner” packing constraint.

The kinds of packing constraints we consider are intersections of matroids and knapsacks. Our results provide a simple and unified view of results in stochastic matching [1, 2] and Bayesian mechanism design [3], and can also handle more general constraints. As an application, we obtain the first polynomial-time Ω(1/

k

)-approximate “Sequential Posted Price Mechanism” under

k

-matroid intersection feasibility constraints, improving on prior work [3-5].

We consider a class of multi-stage robust covering problems, where additional information is revealed about the problem instance in each stage, but the cost of taking actions increases. The dilemma for the decision-maker is whether to wait for additional information and risk the inflation, or to take early actions to hedge against rising costs. We study the “

k

-robust” uncertainty model: in each stage

i

 = 0, 1, …,

T

, the algorithm is shown some subset of size

k

i

that completely contains the eventual demands to be covered; here

k

1

 > 

k

2

 > ⋯ > 

k

T

which ensures increasing information over time. The goal is to minimize the cost incurred in the

worst-case

possible sequence of revelations.

For the

multistage k-robust set cover

problem, we give an

O

(log

m

 + log

n

)-approximation algorithm, nearly matching the

$\Omega\left(\log n+\frac{\log m}{\log\log m}\right)$

hardness of approximation [4] even for

T

 = 2 stages. Moreover, our algorithm has a useful “thrifty” property: it takes actions on just two stages. We show similar thrifty algorithms for multi-stage

k

-robust

Steiner tree

,

Steiner forest

, and

minimum-cut

. For these problems our approximation guarantees are

O

( min {

T

, log

n

, log

λ

max

}), where

λ

max

is the maximum inflation over all the stages. We conjecture that these problems also admit

O

(1)-approximate thrifty algorithms.

We consider the problem of constructing a Steiner arborescence broadcasting a signal from a root

r

to a set

T

of sinks in a metric space, with out-degrees of Steiner vertices restricted to 2. The arborescence must obey delay bounds for each

r

-

t

-path (

t

 ∈ 

T

), where the path delay is imposed by its total edge length and its inner vertices.

We want to minimize the total length. Computing such arborescences is a central step in timing optimization of VLSI design where the problem is known as the repeater tree problem [1,5]. We prove that there is no constant factor approximation algorithm unless

$\mbox{\slshape P}=\mbox{\slshape NP}$

and develop a bicriteria approximation algorithm trading off signal speed (shallowness) and total length (lightness). The latter generalizes results of [8,3], which do not consider vertex delays. Finally, we demonstrate that the new algorithm improves existing algorithms on real world VLSI instances.

We propose an optimal mechanism for a sequencing problem where the jobs’ processing times and waiting costs are private. Given public priors for jobs’ private data, we seek to find a scheduling rule and incentive compatible payments that minimize the total expected payments to the jobs. Here, incentive compatible refers to a Bayes-Nash equilibrium. While the problem can be efficiently solved when jobs have single dimensional private data, we here address the problem with two dimensional private data. We show that the problem can be solved in polynomial time by linear programming techniques, answering an open problem in [13]. Our implementation is randomized and truthful in expectation. The main steps are a compactification of an exponential size linear program, and a combinatorial algorithm to decompose feasible interim schedules. In addition, in computational experiments with random instances, we generate some more insights.

The best-known conjecture in the context of matroid secretary problems claims the existence of an

O

(1)-approximation applicable to any matroid. Whereas this conjecture remains open, modified forms of it were shown to be true, when assuming that the assignment of weights to the secretaries is not adversarial but uniformly at random [20,18]. However, so far, no variant of the matroid secretary problem with adversarial weight assignment is known that admits an

O

(1)-approximation. We address this point by presenting a 9-approximation for the

free order model

, a model suggested shortly after the introduction of the matroid secretary problem, and for which no

O

(1)-approximation was known so far. The free order model is a relaxed version of the original matroid secretary problem, with the only difference that one can choose the order in which secretaries are interviewed.

Furthermore, we consider the classical matroid secretary problem for the special case of laminar matroids. Only recently, a

O

(1)-approximation has been found for this case, using a clever but rather involved method and analysis [12] that leads to a 16000/3-approximation. This is arguably the most involved special case of the matroid secretary problem for which an

O

(1)-approximation is known. We present a considerably simpler and stronger

$3\sqrt{3}e\approx 14.12$

-approximation, based on reducing the problem to a matroid secretary problem on a partition matroid.

Let

$\textbf{L}^{m}$

be the Lorentz cone in ℝ

m

. Given

$A \in {\mathbb{Q}}^{m \times n_1}$

,

$B \in {\mathbb{Q}}^{m \times n_2}$

and

b

 ∈ ℚ

m

, a

simple

second order conic mixed-integer set (SOCMIS) is a set of the form

$\{(x,y)\in {\mathbb{Z}}^{n_1} \times {\mathbb{R}}^{n_2}\,|\,\ Ax +By -b \in \textbf{L}^{m}\}$

. We show that there exists a polynomial-time algorithm to check the closedness of the convex hull of simple SOCMISs. Moreover, in the special case of pure integer problems, we present sufficient conditions, that can be checked in polynomial-time, to verify the closedness of intersection of simple SOCMISs.

We consider computing optimal

k

-norm preemptive schedules of jobs that arrive over time. In particular, we show that computing the optimal

k

-norm of flow schedule, 1 |

r

j

,

pmtn

| ∑ 

j

(

C

j

 − 

r

j

)

k

in standard 3-field scheduling notation, is strongly NP-hard for

k

 ∈ (0, 1) and integers

k

 ∈ (1, ∞ ). Further we show that computing the optimal

k

-norm of stretch schedule, 1 |

r

j

,

pmtn

| ∑ 

j

((

C

j

 − 

r

j

)/

p

j

)

k

in standard 3-field scheduling notation, is strongly NP-hard for

k

 ∈ (0, 1) and integers

k

 ∈ ∪ (1, ∞ ).

In the

k-supplier

problem, we are given a set of clients

C

and set of facilities

F

located in a metric (

C

 ∪ 

F

,

d

), along with a bound

k

. The goal is to open a subset of

k

facilities so as to minimize the maximum distance of a client to an open facility, i.e., min

S

 ⊆ 

F

: |

S

| = 

k

max

v

 ∈ 

C

d

(

v

,

S

), where

d

(

v

,

S

) =  min

u

 ∈ 

S

d

(

v

,

u

) is the minimum distance of client

v

to any facility in

S

. We present a

$1+\sqrt{3}<2.74$

approximation algorithm for the

k

-supplier problem in Euclidean metrics. This improves the previously known 3-approximation algorithm [9] which also holds for general metrics (where it is known to be tight). It is NP-hard to approximate Euclidean

k

-supplier to better than a factor of

$\sqrt{7}\approx 2.65$

, even in dimension two [5]. Our algorithm is based on a relation to the

edge cover

problem. We also present a nearly linear

O

(

n

·log

2

n

) time algorithm for Euclidean

k

-supplier in constant dimensions that achieves an approximation ratio of 2.965, where

n

 = |

C

 ∪ 

F

|.

For a convex set

S

, we study the facial structure of its integer hull,

S

ℤ

. Crucial to our study is the decomposition of the integer hull into the convex hull of its extreme points, conv(ext(

S

ℤ

)), and its recession cone. Although conv(ext(

S

ℤ

)) might not be a polyhedron, or might not even be closed, we show that it shares several interesting properties with polyhedra: all faces are exposed, perfect, and isolated, and maximal faces are facets. We show that

S

ℤ

has an infinite number of extreme points if and only if conv(ext(

S

ℤ

)) has an infinite number of facets. Using these results, we provide a necessary and sufficient condition for semidefinite representability of conv(ext(

S

ℤ

)).

We give an efficient polynomial-time approximation scheme (EPTAS) for the Joint Replenishment Problem (JRP) with stationary demand. Moreover, using a similar technique, we give a PTAS for the capacitated JRP with non-stationary demand but constant size capacities.

We consider the problem of finding a spanning tree satisfying a family of additional constraints. Several settings have been considered previously, the most famous being the problem of finding a spanning tree with degree constraints. Since the problem is hard, the goal is typically to find a spanning tree that violates the constraints as little as possible.

Iterative rounding became the tool of choice for constrained spanning tree problems. However, iterative rounding approaches are very hard to adapt to settings where an edge can be part of a super-constant number of constraints. We consider a natural constrained spanning tree problem of this type, namely where upper bounds are imposed on a family of cuts forming a chain. Our approach reduces the problem to a family of independent matroid intersection problems, leading to a spanning tree that violates each constraint by a factor of at most 9.

We also present strong hardness results: among other implications, these are the first to show, in the setting of a basic constrained spanning tree problem, a qualitative difference between what can be achieved when allowing multiplicative as opposed to additive constraint violations.

In the

store-and-forward routing

problem, packets have to be routed along given paths such that the arrival time of the latest packet is minimized. A groundbreaking result of Leighton, Maggs and Rao says that this can always be done in time

$O(\textrm{congestion} + \textrm{dilation})$

, where the

congestion

is the maximum number of paths using an edge and the

dilation

is the maximum length of a path. However, the analysis is quite arcane and complicated and works by iteratively improving an infeasible schedule. Here, we provide a more accessible analysis which is based on conditional expectations. Like [LMR94], our easier analysis also guarantees that constant size edge buffers suffice.

Moreover, it was an open problem stated e.g. by Wiese [Wie11], whether there is any instance where all schedules need at least

$(1+\varepsilon)\cdot(\textrm{congestion}+\textrm{dilation})$

steps, for a constant

ε

 > 0. We answer this question affirmatively by making use of a probabilistic construction.

For a polytope

P

, the

Chvátal closure

P

′ ⊆ 

P

is obtained by simultaneously strengthening all feasible inequalities

cx

 ≤ 

β

(with integral

c

) to

$cx \leq \lfloor\beta\rfloor$

. The number of iterations of this procedure that are needed until the integral hull of

P

is reached is called the

Chvátal rank

. If

P

 ⊆ [0,1]

n

, then it is known that

O

(

n

2

log

n

) iterations always suffice (Eisenbrand and Schulz (1999)) and at least

$(1+\frac{1}{e}-o(1))n$

iterations are sometimes needed (Pokutta and Stauffer (2011)), leaving a huge gap between lower and upper bounds.

We prove that there is a polytope contained in the 0/1 cube that has Chvátal rank Ω(

n

2

), closing the gap up to a logarithmic factor. In fact, even a superlinear lower bound was mentioned as an open problem by several authors. Our choice of

P

is the convex hull of a semi-random Knapsack polytope and a single fractional vertex. The main technical ingredient is linking the Chvátal rank to

simultaneous Diophantine approximations

w.r.t. the ∥ · ∥ 

1

-norm of the normal vector defining

P

.

We prove the approximation ratio 8/5 for the metric {

s

,

t

}-path-TSP, and more generally for shortest connected

T

-joins.

The algorithm that achieves this ratio is the simple “Best of Many” version of Christofides’ algorithm (1976), suggested by An, Kleinberg and Shmoys (2012), which consists in determining the best Christofides {

s

,

t

}-tour out of those constructed from a family

$\mathcal{F}_+$

of trees having a convex combination dominated by an optimal solution

x

*

of the Held-Karp relaxation. They give the approximation guarantee

$\frac{\sqrt{5}+1}{2}$

for such an {

s

,

t

}-tour, which is the first improvement after the 5/3 guarantee of Hoogeveen’s Christofides type algorithm (1991). Cheriyan, Friggstad and Gao (2012) extended this result to a 13/8-approximation of shortest connected

T

-joins, for |

T

| ≥ 4.

The ratio 8/5 is proved by simplifying and improving the approach of An, Kleinberg and Shmoys that consists in completing

x

*

/2 in order to dominate the cost of “parity correction” for spanning trees. We partition the edge-set of each spanning tree in

$\mathcal{F}_+$

into an {

s

,

t

}-path (or more generally, into a

T

-join) and its complement, which induces a decomposition of

x

*

. This decomposition can be refined and then efficiently used to complete

x

*

/2 without using linear programming or particular properties of

T

, but by adding to each cut deficient for

x

*

/2 an individually tailored explicitly given vector, inherent in

x

*

.

A simple example shows that the Best of Many Christofides algorithm may not find a shorter {

s

,

t

}-tour than 3/2 times the incidentally common optima of the problem and of its fractional relaxation.

Ivanoys, Karpinski and Saxena (2010) have developed a deterministic polynomial time algorithm for finding scalars

x

1

, …,

x

n

that maximize the rank of the matrix

B

0

 + 

x

1

B

1

 + … + 

x

n

B

n

for given matrices

B

0

,

B

1

, …,

B

n

, where

B

1

, …,

B

n

are of rank one. Their algorithm runs in

O

(

m

4.37

n

) time, where

m

is the larger of the row size and the column size of the input matrices.

In this paper, we present a new deterministic algorithm that runs in

O

((

m

 + 

n

)

2.77

) time, which is faster than the previous one unless

n

is much larger than

m

. Our algorithm makes use of an efficient completion method for mixed matrices by Harvey, Karger and Murota (2005). As an application of our completion algorithm, we devise a deterministic algorithm for the multicast problem with linearly correlated sources.

We also consider a skew-symmetric version: maximize the rank of the matrix

B

0

 + 

x

1

B

1

 + … + 

x

n

B

n

for given skew-symmetric matrices

B

0

,

B

1

, …,

B

n

, where

B

1

, …,

B

n

are of rank two. We design the first deterministic polynomial time algorithm for this problem based on the concept of mixed skew-symmetric matrices and the linear delta-covering algorithm of Geelen, Iwata and Murota (2003).

Configuration-LPs have proved to be successful in the design and analysis of approximation algorithms for a variety of discrete optimization problems. In addition, lower bounds based on configuration-LPs are a tool of choice for many practitioners especially those solving transportation and bin packing problems. In this work we initiate a study of linear programming relaxations with exponential number of variables for unrelated parallel machine scheduling problems with total weighted sum of completion times objective. We design a polynomial time approximation scheme to solve such a relaxation for

R

|

r

ij

| ∑ 

w

j

C

j

and a fully polynomial time approximation scheme to solve a relaxation of

R

|| ∑ 

w

j

C

j

. As a byproduct of our techniques we derive a polynomial time approximation scheme for the one machine scheduling problem with rejection penalties, release dates and the total weighted sum of completion times objective.