Colin Éric

Hang De Verdiére

Zenthao Zhou

Bastian Bahamondes

Carlos Bonet

Antoine Hochart

Ruben Hoeksma

Tim Oosterwijk

Kevin Schewior

Marc Schröder

Andreas Tönnis

Andreas Wiese

Andres Cristi

Andrea Canales

Alvaro Brunel

Carlos Casorrán

Javier Ledezma

María Angélica

Daniel

Vito Karl

Keywords: Linear Programming, Semidefinite programming, Scheduling, Online Selection, Approximation algorithms

I thank Varun Kanade for all the advice and support, for your collaboration and for sharing your insight and knowledge in theoretical computer science. I thank Monaldo Mastrolilli for hosting me in IDSIA twice, where I also worked with Adam Kurpisz, for sharing all your expertise and knowledge about convex hierarchies

General Introduction

The difficulty of solving a combinatorial optimization problem comes in many different ways. Sometimes, the input is totally available but the number of possible solutions is so large that looking for a good one requires a lot of effort. In other situations the problem is the opposite: Finding a good solution is not hard but the input is only partially revealed. Over the years, techniques have been developed in different contexts that help to attack the situations above. Nevertheless, they are usually very adapted to the particular problem at hand, or the instances that are to be solved. Are there unified approaches to find good solutions in these many situations? Figure 1: Dantzig, Fulkerson and Johnson in 1954, introduced the cutting planes approach to find a tour passing through Washington DC and the other states. Since then, it is a unifying and successful tool for tackling large scale problems.

Input is known, problems are hard! In practical situations, usually the instances and restrictions over the search space are complicated, and a first step is to simplify reality and model it. For the last part, a tool that is widely used nowadays and that has become a unifying approach is linear programming. The goal is to find a 1 way in which the solutions of the combinatorial problem can be mapped to solutions satisfying some linear inequalities, and their performance is measured using a linear objective. Once a model has been found, the second step is to solve the linear program. Since the introduction of the simplex method by Dantzig in 1947 [START_REF] Dantzig | Origins of the simplex method[END_REF], obtaining a solution became practical in many contexts, and it was used intensively those years in operations research and economics, to mention a few. This development coincided with the growing of the practical necessities of finding good solutions to large problems, and with a progressive advance in the computational technologies. Today, there is an extremely rich body of methods for solving linear programs very accurately, with a reasonable computational cost, and very fast. It is now part of the toolbox in machine learning, combinatorial optimization, economics and decision making in general. So when the question of solving a linear program is well understood, one goes back to the first step: The model. The picture becomes less clear at this point because the way a model is constructed depends heavily on the point of view adopted by who designed it. That is, very different models can answer the same question, but what is more important, they have direct implications over the second step: Solving. Whereas model A can be solved rapidly, model B can exhibit a poor performance in terms of accuracy and solving time. The situation turns down to be more dramatic when the search space is restricted to integer values, that is integer programming. In general, solving an integer program is an NP-hard problem, so the classic and very successful approach is to relax the search space and look for a fractional solution. How much do we lose in this step? We quantify this in the so-called integrality gap, that is, the ratio between the best integral solution and the best fractional solution.

At the moment of suggesting a model there are two important aspects to consider:

Contents

Contents

The size and the integrality gap. The first question can be measured easily, but the second aspect is far from being easy to estimate. The ideal model is one of reasonable size and very good integrality gap, but in most of the cases one of them should be resigned to attain the other. Many methods have been suggested the last decades to improve the integrality gap of a model and one of the most popular is the cutting planes approach, from the seminal work of Dantzig, Fulkerson and Johnson [START_REF] Dantzig | Solution of a large-scale travelingsalesman problem[END_REF]. There, one looks for better integrality gaps by introducing new constraints that are valid for every integer solution. Chvátal in 1973 [START_REF]Edmonds polytopes and a hierarchy of combinatorial problems[END_REF] showed a particular way of constructing these constraints that eventually provide a full description of the convex hull of the integer solutions. Many state-of-the-art solvers already include these methods at the moment of solving an integer program.

2x 1 +2x 2 Ø 1, x 2 1 = x 1 , x 2 2 = x 2 . 2x 1 +2y {1,2} Ø x 1 , 2x 2 +2y {1,2} Ø x 2 , 2x 2 ≠ 2y {1,2} Ø 1 ≠ x 1 , 2x 1 ≠ 2y {1,2} Ø 1 ≠ x 2 , x 1 + x 2 ≠ y {1,2} AE 1, min{x 1 ,x 2 }Øy {1,2} , x 1 ,x 2 ,y {1,2} Ø 0.
x 1

x 2

Figure 3: The set {(x 1 ,x 2 ) oe{0, 1} 2 :2x 1 +2x 2 Ø 1} can be relaxed using linear programming. This region K 0 includes fractional basic feasible solutions such as (1/2, 0) and (0, 1/2). By adding new variables simulating the possible products between the variables and introducing new constraints, one obtains a larger program, but is easy to solve. Furthermore, the projection K 1 over the original space it is strictly contained in K 0 . This approach was introduced by Sherali & Adams [START_REF] Sherali | A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems[END_REF]. By combining the first, third and fifth constraint at the right one can show that 2x 1 +5x 2 /3 Ø 1 holds, which cuts the point (0, 1/2).

Another way to gradually improve the integrality gap is the lift & project approach. The idea is to introduce many new variables in order to be able of including more complicated constraints that are valid for every integer solution. One obtains a program in a higher dimensional space, and then goes back by projecting to the variable space of the original program. By doing this it is possible to simulate non-linear constraints, at the cost of incrementing the size. Eventually, by repeating this step many times it is possible to reach the convex hull of the integer solutions. The programs obtained from these methods are also based on semidefinite programming, which is a generalization of the linear case and can be solved efficiently. Recently these methods have attracted a lot of interest in the theoretical computer science community, since it provides a candidate for unifying many of the existing optimal algorithms. We refer to the survey of Barak and Steurer for an overview and some open problems [START_REF] Barak | Sum-of-squares proofs and the quest toward optimal algorithms[END_REF].

Both of these methods are guaranteed to improve the integrality gap, but due to computational limitations it is not possible to apply them for many steps. Therefore, the key question is: How fast the integrality gap decreases? We try to answer this question in Part I in the particular case of a scheduling problem, which is among the most fundamental and studied combinatorial problems.

Problems are easy, input is unknown! In contrast to before, there are many combinatorial problems that are relatively simple to solve, but the difficulty relies on the availability of input data. This can be really problematic especially when decisions have to be made over time. We then say that the input is revealed online.

Consider the following situation. A logistics company needs to hire a data scientist to develop new technologies in their operations area. Some candidates are shortlisted to be interviewed, but due to time constraints, the time windows between them are not so short. Assuming that when an offer is made the interviewing process is finished, the question is: Who to offer? This is an online selection problem. sample size probability 100 [START_REF] Vega | Linear programming relaxations of maxcut[END_REF] 40

1 e
Figure 4: There are a 100 candidates. The decision maker interviews s candidates without making any offer, this is the sampling phase. After the sampling phase, the decision maker selects the best candidate seen so far. With probability ¥≠ s 100 ln 1 s 100 2 the selected candidate is the best among the hundred. This probability is maximized at s =37¥ 100/e. Sometimes at the moment of revealing an element it is also revealed a weight or reward, but more often the decision maker ranks the elements seen so far. The second Contents Contents ingredient is the order in which the elements are revealed. When the order is chosen uniformly at random, the problem is widely known as the secretary problem. It is neither clear when the problem was stated for the first time nor who solved it. The problem appeared in the February 1960 column of Scientific American, but Cayley and even Kepler already thought about similar questions. It was Lindley [START_REF] Lindley | Dynamic Programming and Decision Theory[END_REF] in 1961 who seems to be the first in publishing a solution in a scientific journal but posteriorly the results were extended and studied profoundly in the optimization community, optimal control, probability and in the last decade, algorithms.

The key algorithmic question is then how to construct simple and provably good stopping rules. Observe that under full knowledge, which is the offline setting, the optimal solution is just to pick the best element. If the selection constraints are more complicated, say, selecting at most three instead of only one, the offline problem is still very simple. In fact, one can see that if the selection is restricted to what is known as matroid, the optimal solution for the offline setting is given by the greedy algorithm. The Kruskal algorithm for finding minimum spanning trees is just an implementation of the greedy algorithm for a very particular matroid.

The answer to the hiring problem is the following: Interview about the 37% of the candidates without making any offer, and then make an offer to best candidate seen so far. With probability close to 0.37 the decision maker will pick the best candidate among every. The ratio between the best we could have done offline versus what we do online is called the competitiveness of the algorithm. Then the question is the following: Is it possible to find simple algorithms with good competitiveness for the selection problem, under combinatorial constraints, that guarantee every element in the optimal solution to be picked with good probability? We study this question in Part II, when the selection is restricted to matroid constraints.

Contributions of this Thesis

In the first part of this thesis we study the problem of scheduling identical machines to minimize the makespan. In the scheduling literature it is usually referred as P ÎC max . This problem has been studied extensively from an algorithmic point of view. In particular, a polynomial time approximation scheme1 exists for this problem, which is based on rounding the instance to decrease the combinatorics and then running a dynamic program. The question we try to answer is the following: Q 1 : Is it possible to match the best approximation factors by applying lift & project methods over a known relaxation to reduce the integrality gap?

We show that applying these methods over the natural linear program relaxations for this problem does not help to reduce the integrality gap. More specifically, the problem is modeled as an assignment problem for which its integrality gap is known to be 2. We answer the question negatively.

A 1 (≠): Even if we apply lift & project to construct linear or semidefinite programs of exponential size, the integrality gap is not less than 1.0009.

We remark that the constant in the lower bound has not been optimized, and probably can be improved, but it is good enough for the exposition of the result. This answer, although informative, it is a bit unsatisfactory since we know this problem is easy from an approximation point of view. A very particular feature of the case when the machines are identical is that the relaxations we obtain are all symmetric respect to the action of a group: If we permute machines, we obtain other feasible schedule with the same makespan. In practice and also in theory, this is known to be harmful at the moment of optimizing. Then, the approach we consider is the following. Before applying lift & project, we break the machine symmetries of the ground linear program by introducing constraints. We show that in this case we are able to reduce the integrality gap, and matching the best known approximation factors.

A 1 (+): If we apply lift & project after breaking machine symmetries, we can obtain relaxations of polynomial size and with integrality gap arbitrarily close to one.

In the second part of this thesis we study the secretary problem when the selection is constrained to a matroid. Usually, the problem is studied under the existence of a weight associated to every element, and the performance of an algorithm is measured in terms of the expected weight of the algorithm selection. For many matroid families there are algorithms with constant competitiveness, but it remains as an open question whether the same can be attained for any matroid. We introduce a notion of competitiveness that does not assume the existence of weights, but rather assumes the ability to rank the elements seen so far at every time step. The secretary problem was originally stated in this framework, but most of the subsequent work focused on the weighted version. Our goal is to maximize the probability for which any element in the optimal solution is selected by the algorithm, that is a stronger notion of competitiveness.

Q 2 : Can we design algorithms with good competitiveness for the secretary problem for this stronger notion?

We answer this question positively for many matroid families, by showing algorithms that match or beat the best known competitiveness in the weaker weighted notion. Furthermore, we develop a general framework for designing algorithms with constant probability competitiveness. We also design algorithms for general matroids in the the stronger notion.

A 2 : There is a general framework that yields O(1) probability competitiveness for many matroid families.

Contents

Contents

The first chapter of each Part I and II provide a deeper introduction and a formal exposition of the results obtained.

Part I Convex Optimization: Applications to Scheduling

Chapter 1

Introduction

Machine scheduling is a classical family of problems in combinatorial optimization.

In this paper we study the problem of scheduling a set J of n jobs on a set M of identical machines to minimize the makespan, i. e., the maximum completion time of a job, where each job j oe J has a processing time (or size) p j . A job cannot be preempted nor migrated to a different machine, and every job is released at time zero. This problem admits a polynomial-time approximation scheme (PTAS) [3,4,[START_REF] Hochbaum | Approximation algorithms for NP-hard problems[END_REF][START_REF] Hochbaum | Using dual approximation algorithms for scheduling problems theoretical and practical results[END_REF][START_REF] Jansen | An eptas for scheduling jobs on uniform processors: using an milp relaxation with a constant number of integral variables[END_REF], which is the best possible approximation result, unless P = NP, since the problem is strongly NP-hard [START_REF] Garey | Strong" NP-completeness results: motivation, examples, and implications[END_REF]. However, there is no known algorithm based on convex relaxations that meets the results. A straightforward way to model the problem with a integer program is given by assignment linear program which has a variable x ij for each combination of a machine i oe M and a job j oe J, modeling whether job j is assigned to machine i.E v e r y job has to be scheduled in exactly one machine. Instead of considering the makespan value as a variable that should be minimized, we guess its value T and we require that q joeJ x ij p j AE T for each machine i oe M . Therefore, the relaxation of this integer program, denoted by [assign(T )], is given by ÿ ioeM x ij = 1 for all j oe J, ÿ joeJ x ij p j AE T for all i oe M, x ij Ø 0 for all i oe M, for all j oe J.

The Configuration Linear Program

The assignment LP is dominated by the configuration linear program, or configuration LP for short, which is, to the best of our knowledge, the strongest relaxation for the problem studied in the literature [START_REF] Verschae | On the configuration-LP for scheduling on unrelated machines[END_REF]. Given a value T>0, a configuration corresponds to a multiset of processing times such that its total sum does not exceed T , i. e., it is a feasible assignment for a machine when the makespan is equal to T . The multiplicity function m(p, C) indicates the number of times that the processing time p appears in the multiset C. The load of a configuration C is just the total processing time, that is, q poe{p j :joeJ} m(p, C) • p. Given T , let C denote the set of all feasible configurations, that is, with load at most T . Observe that the definition in terms of multisets makes sense since we are working in a setting of identical machines.

For each combination of a machine i oe M and a configuration C oeC , the configuration LP has a variable y iC that models whether machine i is scheduled with jobs according to configuration C. Letting n p denote the number of jobs in J with processing time p, we can write the linear program relaxation, clp(T ), given by We remark that in another common definition [START_REF] Verschae | On the configuration-LP for scheduling on unrelated machines[END_REF], a configuration is a subset, not of processing times but of jobs. We can solve that linear program to an arbitrary accuracy in polynomial time [START_REF] Verschae | On the configuration-LP for scheduling on unrelated machines[END_REF] and similarly our linear program above.

Convex Hierarchies

Chapter 1

Integrality gap. Recall the configuration LP, clp(T ), does not have an objective function and instead we seek to determine the smallest value T for which it is feasible. In this context, given an integer program that models the problem of scheduling identical machines and with T a fixed value of the makespan, we say that K(T ) is a convex relaxation if it is a convex set that contains every integer feasible solution. We define the integrality gap to be the value sup IoeI C max (I)/T ú (I) over all scheduling instances I, where C max (I) is the optimal makespan of the scheduling instance I and T ú (I) is the minimum value T such that K(T ) is feasible.

With the additional constraint that T Ø max joeJ p j , the assignment LP relaxation has an integrality gap of 2. This can be shown using the analysis of the list scheduling algorithm, see e. g., [START_REF] Williamson | The design of approximation algorithms[END_REF]. On the other hand, a lower bound of 2 ≠ 1/|M | can be easily shown for an instance with |M | + 1 jobs of unit size. Naturally, the integrality gap of the configuration LP is as well upper bounded by 2, since it dominates the assignment LP. One of the first results we show is that the configuration LP has an the integrality gap which is at least 1.0009 (Chapter 2). For the more general unrelated machines scheduling problem, the formulation where configurations are jobs sets has an integrality gap equal to 2 [START_REF] Verschae | On the configuration-LP for scheduling on unrelated machines[END_REF].

Convex Hierarchies

An interesting question is whether other convex relaxations have better integrality gaps. Convex hierarchies, parameterized by a number of levels, rounds or steps,a r e systematic approaches to gradually tightening the ground relaxation, at the cost of increased running time in solving the relaxation. As a consequence, they are good candidates for designing approximation algorithms based on rounding a solution obtained from these relaxations. Given a polytope K ™ [0, 1] n , all these approaches produce a family of convex relaxations K 1 ,K 2 ,...,K n satisfying that

K = K 0 ´K1 ´K2 ´•••´K n≠1 ´Kn =con v(K fl{0, 1} n ).
Popular among these methods are the Sherali-Adams (SA) hierarchy [START_REF] Sherali | A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems[END_REF] (Chapter 3) the Lovász-Schrijver hierarchy (LS) and its semidefinite (LS + ) counterpart [START_REF] Lovász | Cones of matrices and set-functions and 0-1 optimization[END_REF], (Chapter 4) and the Lasserre/Sum-Of-Squares (Las) hierarchy [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF][START_REF] Parrilo | Semidefinite programming relaxations for semialgebraic problems[END_REF] (Chapter 5), which is the strongest of the three. The level r relaxations are known to be solvable in time n O(r) , where n is the number of variables, provided some assumptions over the ground polytope. In particular, when r is constant, the complexity of solving the relaxation becomes polynomial on the program size. This is relevant when looking for an approximation algorithm based on this relaxation. For a comparison between them and their algorithmic implications we refer to [START_REF] Chlamtac | Convex relaxations and integrality gaps[END_REF][START_REF] Laurent | A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming[END_REF][START_REF] Rothvoß | The lasserre hierarchy in approximation algorithms[END_REF]. In some settings, for example the Independent Set problem in sparse graphs [START_REF] Bansal | Approximating independent sets in sparse graphs[END_REF], a hierarchy obtained from SA strenghtened with semidefinite constraints at the first level has also been considered. Positive results. For many problems the approximation factors of the best known algorithms match the integrality gap after performing a constant number of rounds of these hierarchies. For example, Alekhnovich, Arora and Tourlakis [2] show that one round of LS + yields the Goemans-Williamson [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF] relaxation for Max-Cut, and the third level of LS + is at least as strong as the ARV relaxation for Sparsest-Cut [6]. In both cases, the base relaxation over which the hierarchy is applied corresponds to the metric defining linear program. Also for Max-Cut, Fernandez de la Vega and Mathieu [START_REF] Vega | Linear programming relaxations of maxcut[END_REF] prove that the integrality gap of the SA hierarchy drops to 1 + Á after f (1/Á) rounds for dense graphs. For general constraint satisfaction problems (CSP) in its approximation version, Chan et al. [START_REF] On | Approximate constraint satisfaction requires large lp relaxations[END_REF] show that polynomial-sized linear programs are as powerful as programs arising from constant rounds of SA. In that sense, this hierarchy captures the best integrality gaps obtained by linear programming in CSP's like Max-Cut and Max-3-Sat. For the Knapsack problem, Chlamtac, Friggstad, and Georgiou [START_REF] Chlamtac | Lift-and-project methods for set cover and knapsack[END_REF] show that 1/Á 3 levels of LS + yield an integrality gap of 1 + Á and prove that it is possible to approximate Set-Cover using the linear relaxations of LS when the objective function is lifted into the constraints. In the scheduling context, for minimizing the makespan on two machines in the setting of unit size jobs and precedence constraints, Svensson solves the problem optimally with only one level of the linear LS hierarchy (published in [START_REF] Rothvoß | The lasserre hierarchy in approximation algorithms[END_REF]Section 3.1], personal communication between Svensson and the author of [START_REF] Rothvoß | The lasserre hierarchy in approximation algorithms[END_REF]). Furthermore, for a constant number of machines, Levey and Rothvoss give a (1 + Á)-approximation algorithm using (log(n)) Θ(log log n) rounds of SA hierarchy [START_REF] Levey | A Lasserre-based (1 + Á)-approximation for Pm|p j = 1, prec|C max[END_REF]. For minimizing weighted completion time on unrelated machines, one round of LS + leads to the current best approximation algorithm [START_REF] Bansal | Lift-and-round to improve weighted completion time on unrelated machines[END_REF]. Thus, hierarchies are a strong tool for approximation algorithms.

Negative results. Nevertheless, there are known limitations on these hierarchies. Lower bounds on the integrality gap of LS + are known for Independent Set [START_REF] Feige | The probable value of the Lovász-Schrijver relaxations for maximum independent set[END_REF], Vertex Cover [5,[START_REF] Charikar | On semidefinite programming relaxations for graph coloring and vertex cover[END_REF][START_REF] Georgiou | Integrality gaps of 2o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy[END_REF][START_REF] Schoenebeck | Tight integrality gaps for Lovász-Schrijver LP relaxations of vertex cover and max cut[END_REF], Max-3-Sat and Hypergraph Vertex Cover [2], and k-Sat [START_REF] Buresh-Oppenheim | Rank bounds and integrality gaps for cutting planes procedures[END_REF]. For the Max-Cut problem, there are lower bounds for the SA [START_REF] Vega | Linear programming relaxations of maxcut[END_REF] and LS + [START_REF] Schoenebeck | Tight integrality gaps for Lovász-Schrijver LP relaxations of vertex cover and max cut[END_REF]. For the Min-

Lower bounds Chapter 1

Sum scheduling problem (i. e., scheduling with job dependent cost functions on one machine) the integrality gap is unbounded even after O( Ô n) rounds of Lasserre [START_REF] Kurpisz | A Lasserre lower bound for the min-sum single machine scheduling problem[END_REF].

In particular, that holds for the problem of minimizing the number of tardy jobs even though that problem is solvable in polynomial time, thus SDP hierarchies sometimes fail to reduce the integrality gap even on easy problems.

Lower bounds

One of the questions we try to answer in this work is the following: Is it possible to obtain a polynomial time (1 + ')-approximation algorithm based on directly applying the SA or the LS + hierarchy over the configuration LP? This would match the best known polynomial time approximation factor known. We answer this question in the negative. We prove that even after Ω(n) rounds of SA or LS + to the configuration LP, where n is the number of jobs in the instance, the integrality gap of the resulting relaxation is still at least 1 + 1/1023. Since the configuration LP dominates the assignment LP, our result also holds if we apply Ω(n) rounds of SA or LS + to the assignment LP.

Theorem 1. Consider the problem of scheduling identical machines to minimize the makespan, P ÎC max . For each n oe N there exists an instance with n jobs such that:

(i) the configuration LP has an integrality gap of at least 1024/1023.

(ii) after applying r =Ω( n) rounds of the SA hierarchy to the configuration LP the obtained relaxation has an integrality gap of at least 1024/1023.

(iii) after applying r =Ω(n) rounds of the LS + hierarchy to the configuration LP the obtained relaxation has an integrality gap of at least 1024/1023. 1Therefore, the SA and the LS + hierarchies do not yield the best possible approximation algorithms when applied over the configuration LP. Namely, suppose there exists r oe N such that the r level of the SA hierarchy has an integrality gap of at most 1 + Á, with Á<1/1023. In particular, that holds as well for the hard instances of Theorem 1 and r =Ω ( n). We remark that for the hierarchies studied in Theorem 1, a number of rounds equal to the number of variables in clp(T ) suffice to bring the integrality gap down to exactly one, although this number is in general exponentially large in the input size. Nevertheless, we also prove in Chapter 3 that a number of rounds equal to number of machines suffices to reduce the integrality gap to one, when the SA hierarchy is applied over the configuration LP. This comes as a consequence of a stronger decomposition lemma, that relies on the structure of the configuration linear program.

We prove Theorem 1 by defining a family of instances {I k } koeN constructed from the Petersen graph (see Figure 2.3). The size of instance I k , given by the number of machines and jobs, is Θ(k) and the number of jobs is Θ(k) as well. In Chapter 2 we provide an explicit construction of the hard instances and we prove that the configuration LP is feasible for T = 1023 while the integral optimum has a makespan of at least 1024. In Chapter 3, we show for each instance I k that we can define a fractional solution that is feasible for the polytope obtained by applying Ω(k) rounds of SA to the configuration LP parametrized by T = 1023. Finally, in Chapter 4 we prove the same for the semidefinite relaxations obtained with the LS + hierarchy, and we study the matrices arising in the lower bound proof.

Upper bound

The assignment and configuration LP's have in common the fact that we can permute the machines, and the solutions obtained remain feasible. The sets satisfying this property are said to be invariant under the action of some permutation group. In the case of these polytopes, the symmetric group of size equal to the number of machines is acting over the feasible solutions. The same holds for the relaxations obtained from applying SA and LS + over the configuration LP. This is a key fact when reducing the dimensionality of the matrices certifying the feasible solutions in Chapter 4. The results shown in Theorem 1 suggest that symmetric relaxations do not seem to be good candidates for obtaining small integrality gaps for the scheduling problem. Therefore, the question we study is the following: Is it possible to obtain a polynomial sized linear or semidefinite relaxation with an integrality gap of (1 + Á) that is not invariant for the machine symmetries? This time, we provide a positive answer. Below we state, informally, the main theorem which is proven in Chapter 5.

Theorem 2. For every Á>0, there exists a non-machine symmetric polynomial sized semidefinite relaxation with an integrality gap of at most (1 + Á), for the problem of scheduling to minimize the makespan.

The theorem is based on introducing a formulation that breaks the symmetries in the assignment LP by adding new constraints. They enforce a very particular structure over any feasible solution of the formulation that should respect a lexicographic order over the machine configurations induced by any feasible integer solution. On top of the relaxation obtained from adding the aforementioned constraints, we apply the Lasserre/SoS hierarchy. In Chapter 5 we provide a full proof of the theorem, and also a direct application of it: A polynomial time approximation scheme based on solving the semidefinite relaxation.

Practice. The presence of symmetries in the formulations is known to be harmful and the literature about how to deal with them is large. Most of them focus on how to add constraints that break the symmetries, or how to modify the divide and conquer branching techniques in order to avoid unnecessary computations by approaches such 1.4. Upper bound Chapter 1 as perturbation of the numeric values defining the program and variables fixing [START_REF] Margot | Exploiting orbits in symmetric ilp[END_REF][START_REF] Margot | Symmetric ilp: Coloring and small integers[END_REF][START_REF] Méndez-Díaz | A branch-and-cut algorithm for graph coloring[END_REF]. Particular interest have attracted partitioning problems such as scheduling, packing, coloring and clustering. One way of removing the symmetries of a formulation is to consider decompositions such as Dantzig-Wolfe, where all the structure of a partition is hidden and the goal is to find how many times such a structure appears on a solution. In fact, the configuration LP can be seen as an intermediate step between the assignment LP and its Dantzig-Wolfe decomposition. This approach has proven to be successful in practice for many situations including the above mentioned problems in transportation, routing and coloring [START_REF] Barnhart | Branch-and-price: Column generation for solving huge integer programs[END_REF][START_REF] Desrochers | A column generation approach to the urban transit crew scheduling problem[END_REF][START_REF] Mehrotra | A column generation approach for graph coloring[END_REF][START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF].

x 1 x 2 x 1 x 2 Figure 1.4:
The polytope in R 2 at the left is invariant under the action of permuting variables, that is, every time (x 1 ,x 2 ) is feasible, then (x 2 ,x 1 ) is also feasible.

Extended formulations. Similar results to Theorem 1 can be found in the context of extended formulations, that is, a convex set on a higher dimensional space that coincides with the original one when projected to the initial variables space. Remarkable are the results of Yannakakis [START_REF] Yannakakis | Expressing combinatorial optimization problems by linear programs[END_REF] that neither the matching polytope nor the TSP polytope have symmetric linear extended formulation of subexponential size. Recently, this results were extended also for non symmetric linear extended formulations by Fiorini et al. [START_REF] Fiorini | Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds[END_REF] in the case of TSP and by Rothvoss [START_REF] Rothvoß | The matching polytope has exponential extension complexity[END_REF] for matching. The same negative result follows if one consider semidefinite formulations, since Braun et al. [START_REF] Braun | The matching problem has no small symmetric sdp[END_REF] showed that any symmetric semidefinite program for matching has exponential size. They also show that every symmetric relaxation of polynomial size n k for asymmetric TSP is not stronger than an O(k) level Lasserre/SoS relaxation.

Symmetry breaking constraints.

The way we obtain improvements in the gap at Theorem 2 is by adding constraints on top of the initial symmetric relaxation, which is the assignment polytope in this case, in order to obtain a program that is not invariant. The result would also follow if we consider initially the configuration LP, since one can show that the Lasserre/SoS hierarchy over the assignment LP at certain level is stronger than the configuration LP, provided some assumptions over the instances. The idea behind all these approaches is to remove parts of the feasible region that provide no extra information in terms of objective value and solution structure. De-pending on the problem and the particular group action, different sets of symmetry breaking inequalities have been considered. For partitioning problems there are ways of enforcing an order over the solutions and then guaranteeing that only one solution per orbit is considered [START_REF] Flener | Symmetry in matrix models[END_REF][START_REF] Flener | Breaking row and column symmetries in matrix models[END_REF][START_REF] Jans | Solving lot-sizing problems on parallel identical machines using symmetry-breaking constraints[END_REF]. Following the same lines, in the particular case of scheduling there is a way of ensuring that exactly one representative per orbit is selected by intersecting the original partitioning polytope with the so called orbitope [START_REF] Kaibel | Packing and partitioning orbitopes[END_REF]. They provide a linear description of the orbitope that is of exponential size, but it can be separated efficiently. For an extensive treatment we refer to the excellent survey of Margot [START_REF] Margot | Symmetry in integer linear programming[END_REF].

Chapter 2

The hard instances

In this chapter we show that the configuration LP described by constraints (1.1) and (1.2) has an integrality gap of at least 1024/1023. To this end, for each k oe N we define an instance I k that is inspired by the Petersen graph G =(V, E) (see Figure 2.1) with vertex set V = {0, 1,...,9}. We first have to introduce a family of multigraphs obtained from G.

For each k oe N, we construct a multigraph G k =( V, E k ) with vertex set equal to V and the set of edges E k is defined as follows: For each edge {u, v}oeE of the Petersen graph G, we have a multiset E({u, v}) with k copies of the edge {u, v}. The set E k is just the multiset obtained from the union of all these multisets, that is, E k = fi {u,v}oeE E({u, v}). In particular we have that G 1 = G, the Petersen graph. The scheduling instances. In the instance I k we have a job j e for every e oe E k , which is the set of edges in the multigraph G k . Thus I k has 15k jobs. Let e oe E k be such that e oe E({u, v}), that is, e is an edge between nodes u and v. The processing time of j e is p je =2 u +2 v . We define the set of machines for I k to be [3k]={1,...,3k}.

Observe that every subset of edges F ™ E k induces a multiset C F of job-sizes as follows: For every {u, v}oeE and p =2 u +2 v , we have m(p, C F )=|F fl E({u, v})|. In words, for every possible processing time, we check how many copies of the corresponding edge in G are in F , and this number is the multiplicity of the processing time in the multiset C F . If the load of C F is at most T , we say that C F is the configuration induced by F . We remark that this mapping is not injective, since different subsets of edges may induce the same processing times multiplicities and therefore the same configuration.

0 +2 4 , 2 0 +2 4 , 2 4 +2 9 , 2 9 + 2 6 , 2 3 +2 8 } and the orange edges induce the configuration {2 0 +2 4 , 2 4 +2 3 , 2 3 +2 8 , 2 9 + 2 7 , 2 2 +2 1 }.
The first has a load of 1402 and the second has a load of 951.

Matching configurations. The Petersen graph G has exactly six perfect matchings -1 ,...,-6 . We have that the sum of the job sizes in a perfect matching -¸is

ÿ eoe-¸pje = 9 ÿ u=0 2 u deg -¸(u)=1 023, since deg -¸(u) = 1
for every node u oe V . Therefore, -¸induces a configuration C with load 1023 in the following way: C ¸= {2 u +2 v : {u, v}oe-¸}, that is, for every edge e oe -¸we have in C ¸one copy of a job with processing time p je defined as above. The configurations set C -= {C 1 ,...,C 6 } are called matching configurations.

It can be checked easily that is not possible to find a partition of the edges in the Petersen graph such that every part is a perfect matching, i. e., there is no 1factorization of the Petersen graph. This property is a key ingredient for proving the lower bounds on the integrality gaps of the different relaxations we consider for the scheduling problem. We extend the definition of 1-factorization to multigraphs in the natural way. In the following lemma we show an infinite sequence of multigraphs in {G k } koeN for which there is no 1-factorization. Proof. Let -6 be the perfect matching of the Petersen graph consisting of the five edges {0, 5}, {1, 6}, {2, 7}, {3, 8} and {4, 9}, called spokes (last matching at Figure 2.3). Suppose there exists a 1-factorization of G k , and let Ê 6 be the number of times that the perfect matching -6 appears in the 1-factorization. In particular, the size of the 1-factorization is 3k, since there are 15k edges in G k and every perfect matching has exactly 5 edges.

Each spoke, which appears in exactly one other perfect matching in {-1 ,...,-5 }, must be contained in exactly k perfect matchings of the 1-factorization. Therefore, for all j oe [5], the perfect matchingj appears k ≠ Ê 6 times in the 1-factorization. Thus, in total the size of the 1-factorization is 5(k ≠ Ê 6 )+Ê 6 =5 k ≠ 4Ê 6 . However, that sum equals 3k, and so Ê 6 = k/2. Since k is odd and Ê 6 an integer, the contradiction follows.

Integrality gap for clp: Proof of Theorem 1(i)

In this section we prove that the integrality gap of the configuration LP is at least 1024/1023. In fact, we prove a stronger statement: For every k oe N, the gap of the configuration LP at instance I k is at least 1024/1023. Given I k , we proceed in two steps: We first prove that the configuration LP with T = 1023 is feasible for I k , and secondly we prove that the makespan of I k is at least 1024. Lemma 2. For every k oe N, the configuration linear program for T =1023is feasible at instance I k .

Proof. We define a fractional solution that is supported only by matching configurations: For every machine i oe [3k] and each ¸oe{ 1, 2,...,6} we set y iC ¸=1 /6. For every machine i oe [3k] and every configuration C oeC\C -we set y iC = 0. The set of machine constraints (1.1) at clp(T ) is clearly satisfied, since for every i oe [3k] we have

ÿ CoeC y iC = 6 ÿ ¸=1 y iC ¸=6• 1/6=1.
For the set of job-size constraints (1.2), recall that for every e = {u, v}oeE and p = 2 u +2 v , in I k we have that n p = k. The Petersen graph is such that there are exactly two perfect matchingsp 1 ,-

ÿ i=1 ÿ CoeC m(p, C)y iC = 3k ÿ i=1 (y iC p 1 + y iC p 2 )=3k • (1/6+1/6) = k,
and so y is feasible.

Lemma 3. For every odd k oe N, the optimal makespan for I k is at least 1024.

Proof. We first show that the optimal makespan is at least 1023. The total size of the jobs in the instance is equal to

ÿ eoeE k p je = 9 ÿ u=0 2 u deg G k (u)=1023• 3k, since deg G k (u)=3
k for every u oe{ 0,...,9}. There are 3k machines, so if we had a schedule with makespan strictly less than 1023 it would imply that the total load is strictly less than 3k • 1023, which is a contradiction. In particular, the optimal integral makespan for I k is at least 1023. Suppose that the optimal makespan is equal to 1023. By the argument above, it implies that every machine is scheduled with a configuration of load equal to 1023. Let C be a configuration with load equal to 1023, and let F ™ E k such that C is the configuration induced by F .

Claim 4. The set

F is a perfect matching in G k .
In particular, C is a matching configuration. Since every job has to be assigned to some machine, the schedule is induced by a partition of the edges in E k where every part is a perfect matching, i. e., a 1-factorization of G k . However, this is not possible, since by Lemma 1 there is no 1-factorization of G k when k is odd. Therefore, we have a contradiction and we conclude that the optimal makespan is at least 1024.

Proof of Claim 4 in Lemma 3. The load of configuration

C is 1023 = 9 ÿ u=0 2 u deg F (u) = deg F (0) + 2 9 ÿ u=1 2 u≠1 deg F (u).
In particular, the last equality implies that deg F (0) is odd. By induction on u it must be that for every u oe{0,...,9}, deg F (u) is odd. Since the sum does not exceed 1023 = q 9 u=0 2 u , it follows that deg F (u)=1f o re v e r yu oe{ 0,...,9} and so F is a perfect matching in G k .

Chapter 3

Sherali-Adams (SA) Hierarchy

Convex hierarchies provide a way of obtaining gradually stronger relaxations for an integer program. In order to design approximation algorithms based on them it is crucial to understand how fast the gap decreases. In this chapter we study relaxations obtained from the Sherali-Adams (SA) hierarchy over the configuration LP, and we prove that the hard instances shown in Chapter 2 remain hard even after a linear number of rounds of the SA hierarchy.

The SA hierarchy is based on linear programming and basically works by adding new variables and constraints to a linear program in a higher dimensional space and then projecting back to the original variables space. We introduce the relaxations obtained by applying the hierarchy over the configuration LP in a self-contained way, that is equivalent to the approach in the original work of Sherali & Adams [START_REF] Sherali | A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems[END_REF]. We revisit and/or introduce the necessary properties for our purposes.

In the configuration LP, clp(T ), the variables set is M ◊C. The level r Sherali-Adams relaxation, SA r (clp(T )), is a polytope in [0, 1] P r+1 (M ◊C) where P r+1 (M ◊C)= {A ™ M ◊C : |A|AEr +1}. It is defined by the following set of constraints:

ÿ CoeC y Hfi{(i,C)} = y H for all i oe M , for all H oeP r (M ◊C), (3.1)
)

y H Ø 0 for all H oeP r+1 (M ◊C), (3.3) y ÿ =1. (3.4)
We denote by SA r proj (clp(T )) the projection in R M ◊C of the polytope above. The properties summarized in the lemma below are common to most of the hierarchies considered in the literature. For the sake of completeness, we show a self-contained proof in the context of the configuration LP. Lemma 5. Let r oe N. For every scheduling instance and every T>0, the following holds:

(i) clp(T ) fl{0, 1} M ◊C ™ SA r proj (clp(T )).
(ii) SA r+1 proj (clp(T )) ™ SA r proj (clp(T )).

(iii) Let y oe SA r (clp(T )).I fK oeP r+1 (M ◊C) and H ™ K, then y K AE y H .

The first property shows that SA provides relaxations of the integer solutions of the configuration LP. The second property guarantees that at every step we obtain a relaxation at least as strong than the previous one. Finally, the third property reveals some consistency on the relaxation values. In order to gain intuition, it is useful to think off the value y K as the probability that every variable in K is set to one.

Proof of Lemma 5. Consider a scheduling instance and T>0.

(i) Let z oe clp(T ) fl{0, 1} M ◊C . For every non-empty H oeP r+1 (M ◊C)w es e t y H = r (i,C)oeH z iC , and y ÿ = 1. Clearly, the set of constraints in (3.3) and (3.4) are satisfied. Fix a set H oeP r+1 (M ◊C). For every i oe M we have that

ÿ CoeC y Hfi{(i,C)} ≠ y H = y H A ÿ CoeC z iC ≠ 1 B .
Since z oe clp(T ) it follows that q CoeC z iC ≠ 1 = 0 and therefore the machine constraints in (3.1) are all satisfied. Analogously, for every p oe{p j : j oe J},

ÿ ioeM ÿ CoeC m(p, C)y Hfi{(i,C)} ≠ n p y H = y H A ÿ ioeM ÿ CoeC m(p, C)z iC ≠ n p B ,
and since z oe clp(T ) we have q ioeM q CoeC m(p, C)z iC ≠ n p = 0. Therefore, the job-size constraints (3.2) are satisfied.

(ii) Let y oe SA r+1 (clp(T )). By definition of the relaxation at level r +1, y satisfies every constraint at level r and therefore the restriction of y to P r+1 (M ◊C) is feasible for SA r (clp(T )). Since every singleton in M ◊C belongs to P r+1 (M ◊C), the lemma follows.

(iii) It is enough to prove it when K = H fi{(i, R)} for some machine i oe M and some configuration R oeC. Since y Ø 0, the machine constraints (3.1) imply that

y H = ÿ CoeC y Hfi{(i,C)} Ø y Hfi{(i,R)} = y K .

Machine Decomposition Lemma

Given a polytope, the minimum number of rounds that are necessary to guarantee the convergence to the convex hull of the integer solutions is known as rank of the hierarchy [7,[START_REF] Buresh-Oppenheim | Rank bounds and integrality gaps for cutting planes procedures[END_REF][START_REF] Cheung | Computation of the lasserre ranks of some polytopes[END_REF][START_REF] Laurent | A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming[END_REF]. In general, the rank of a polytope in [0, 1] E in the Sherali-Adams hierarchy is upper bounded by |E| (see e. g. [START_REF] Sherali | A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems[END_REF]). In this case, |E| = |M ◊C| = m|C|, which is exponentially large on the input size. Instead we get an upper bound on the rank of the configuration LP which is linear in the input size.

Machine Decomposition Lemma

Chapter 3

Theorem 3. For every scheduling instance with m machines and every T>0,

SA m proj (clp(T )) = conv 1 clp(T ) fl{0, 1} M ◊C 2 .
The theorem above is a direct consequence of a lemma we state next. It relies heavily on the structure of the configuration LP. It can also be proved in terms of the stronger Lasserre/SoS hierarchy by means of the Decomposition Theorem [START_REF] Karlin | Integrality gaps of linear and semidefinite programming relaxations for knapsack[END_REF], but we show that the relaxations obtained from the Sherali-Adams hierarchy are strong enough to get the desired bound on the rank. Lemma 6. Let r oe N and S ™ M be a subset of machines with r Ø|S|. Then,

SA r proj (clp(T )) ™ conv 1 SA r≠|S| proj (clp(T )) fl{0, 1} S◊C 2 .
In words, the lemma says that we can decompose a solution at level r into a convex combination of solutions at level r ≠|S| and all of them are integral at the variables for the machines in S. When the number of machines is fixed, i. e., not part of the input, we obtain the following direct corollary from Theorem 6. Given r oe N, we prove Lemma 6 by induction on the cardinality of S.B e f o r e proceeding with the proof we need to introduce a technical lemma about the relaxations obtained from Sherali-Adams over the configuration LP. Let y oe SA r (clp(T )) and consider a single machine i oe M .I fy {(i,C)} oe (0, 1) for some configuration C,w e say that y is fractional at machine i, otherwise we say that y is integral at machine i. For every C oeC such that y {(i,C)} oe (0, 1), consider the vector defined by

y(i, C) H = y Hfi{(i,C)} y {(i,C)}
for every H oeP r (M ◊C). Observe that constraints (3.1) guarantee that

q CoeC y {(i,C)} = 1. Furthermore, y = ÿ CoeC: y {(i,C)} oe(0,1) y {(i,C)} y(i, C),
and therefore y is a convex combination of the vectors in {y(i, C):C oeC,y {(i,C)} oe (0, 1)}. The vector y(i, C) is said to be the conditioning of y at (i, C). The following lemma is the key for the inductive step. Lemma 8. Suppose that y is fractional at machine i oe M . Then, for every C oeC such that y {(i,C)} oe (0, 1), we have y(i, C) oe SA r≠1 (clp(T )) and y(i, C) is integral at machine i.

Proof. Observe that y(i, C) {(i,C)} = y {(i,C)}fi{(i,C)} /y {(i,C)} = 1. The feasibility of y(i, C) in clp(T ) implies that y(i, C) is integral at machine i. Now we have to verify that y(i, C) satisfies the constraint at the level r ≠ 1. Let H oeP r≠1 (M ◊C) and consider a machine ¸oe M . We have that |H fi{(i, C)}| AE r, so from the feasibility of y at level r we obtain that

ÿ RoeC y(i, C) Hfi{(¸,R)} = 1 y {(i,C)} ÿ RoeC y Hfi{(¸,R)}fi{(i,C)} = y Hfi{(i,C)} y {(i,C)} = y(i, C) H ,
and thus the machine constraints (3.1) are satisfied. Consider a job size p oe{p j : j oe J}. Analogously as before, from the feasibility of y at level r we have that

ÿ ¸oeM ÿ RoeC m(p, R)y(i, C) Hfi{(¸,R)} = 1 y {(i,C)} ÿ ¸oeM ÿ RoeC m(p, R)y Hfi{(¸,R)}fi{(i,C)} = n p y Hfi{(i,C)} y {(i,C)} = n p y(i, C) H ,
and then the job-size constraints (3.2) are satisfied. The non-negativity of y(i, C) is clear and y(i, C) ÿ = y ÿfi{(i,C)} /y {(i,C)} = 1. That finishes the proof.

In particular, this implies Lemma 6 when S = {i} and since it does not depend on i, it holds true for every S ™ M of cardinality one. Observe that if y was integral at machine i then the lemma follows by the nested property at Lemma 5(ii). Another important property of the conditioning is the following: If the vector y was integral at some machine ¸, then after conditioning the vector obtained remains integral at machine ¸. To check this, suppose that y {(¸,S)} = 1. It is enough to check that y(i, C) {(¸,R)} =0f o re v e r yR " = S, since the machine constraints (3.1) imply then y(i, C) {(¸,S)} = 1. By Lemma 5(iii), we have that

y(i, C) {(¸,R)} = y {(¸,R)}fi{(i,C)} y {(i,C)} AE y {(¸,R)} y {(i,C)} =0.
Proof of Lemma 6. In the following assume r Ø 2. Let S ™ M of cardinality at least 2 and y oe SA r (clp(T )). Consider the set S = S \{¸} for some ¸oe S. By induction, there exists a family of vectors {y ◊ } ◊oeΘ ™ SA r≠| S| (clp(T )) = SA r≠|S|+1 (clp(T )) such that y can obtained as a convex combination of them, and for every ◊ oe Θ the vector y ◊ is integral at every machine in S.

In the following we prove that for every ◊ oe Θ, the vector y ◊ restricted to P r≠|S|+1 (M ◊C) can be obtained as a convex combination of vectors in SA r≠|S| (clp(T )) and they are all integral at every machine in S fi{¸} = S. For that end we make use of our technical Lemma 8. As explained before, if y ◊ is integral at machine ¸then we are done. Suppose then that y ◊ is fractional at machine ¸and consider the family of vectors {y ◊ (¸, C):C oeC,y ◊ {(¸,C)} oe (0, 1)} as defined before. By Lemma 8, they are all in SA (r≠|S|+1)≠1 (clp(T )) = SA r≠|S| (clp(T )) and they are all integral at machine ¸. Since the vector y ◊ was integral at S, the vectors obtained from conditioning remain integral there and therefore they are all integral at S, which concludes the proof.

Integrality gap for SA: Proof of Theorem 1(ii)

We show that for the family of instances {I k } koeN defined in Section 2.1, if we apply O(k) rounds of the Sherali-Adams hierachy to the configuration LP for T = 1023, then the resulting relaxation is feasible. Thus, after Ω(k) rounds of SA the configuration LP still has an integrality gap of at least 1024/1023 for an instance with Θ(k) jobs and machines.

We can observe that the configuration LP computes a set of edges in a complete bipartite graph with vertex sets M and C. The edges are selected such that each node in M is incident to at most one selected edge. More specifically, consider the complete directed bipartite graph with vertex sets M and C, which is identified with M ◊C. We say that

F ™ M ◊C is an M -matching if |{C oeC:( i, C) oe F }| = deg F (i) AE 1. We say that i oe M is incident to F if deg F (i) = 1.
The notation extends if the configurations set is not C but a subset of it.

M

C y oe clp(T ) Figure 3.1: Feasible schedule given by an integral solution of the configuration LP. Example with five machines, three of them in the same configuration. The degree of every machine node is exactly one, as specified by the constraints (1.1).

In the following we consider the family of instances {I k : k oe N,k is odd} as in Section 2.1 and T =1023. F oran ysetS, let P(S) be the power set of S. We define a solution to SA r (clp(T )) for T = 1023. To this end, we need to provide a value y A for each set A oeP r+1 (M ◊C). These values are given by the following function: Let " : P(M ◊C -) ae R be such that

"(A)= 1 (3k) |A| Ÿ joe[6] (k/2) deg A (C j )
if A is an M -matching, and zero otherwise, where (x) 0 = 1 and (x) a = x(x≠1) •••(x≠ a + 1) if a Ø 1 is integer positive. This is called the lower factorial function.T o get some understanding about how the " works, it could be useful to think on a probabilistic interpretation that is formalized in the lemma below: Suppose we know that a set A is chosen (i.e., we condition on this), then the conditional probability that a pair (i, C j ) is chosen equals (k/2 ≠ deg A (C j ))/(3k ≠|A|) when A fi{(i, C j )} is an M -matching.

Lemma 9.

Let A ™ M ◊C -be an M -matching of size at most 3k ≠ 1.I fi oe M is not incident to A, then for every j oe [6],

"(A fi{(i, C j )})="(A) k/2 ≠ deg A (C j ) 3k ≠|A| .
Proof. Given that i is not incident to A, we have |Afi{(i, C j )}| = |A|+1. Furthermore, for ¸" = j we have that deg

Afi{(i,C j )} (C ¸) = deg A (C ¸) and deg Afi{(i,C j )} (C j ) = deg A (C j )+ 1.
We are ready now to define our solution to SA r (clp(T )). It is the vector y " oe R P r+1 (M ◊C) defined such that y " A = "(A) if A is an M -matching in M ◊C -, and zero otherwise.

Lemma 10. For every odd k, y " is a feasible solution in SA r (clp(T )) for the instance I k when r = Âk/2Ê and T =1023.

We note that in the proof above, the projection of y " onto the space of the configuration LP is exactly the fractional solution from Lemma 2. The proof of Theorem 1(ii) now follows directly from the lemma above.

Proof of Theorem 1(ii).

Let k be such that n =1 5 k + ¸where k is the greatest odd integer such that 15k AE n. The theorem follows by considering the instance I k as defined before, T = 1023 and r = Âk/2Ê.

Proof of Lemma 10. The non-negativity follows by checking that the lower factorial in the definition of " remains non-negative for r = Âk/2Ê. It is also clear from the definition that y " ÿ = "(ÿ)=1. We next prove that y " satisfies the machine constraints (3.1) in SA r (clp). If i is a machine incident to H, then all terms in the left-hand summation are 0 except for the unique pair (i, C) that belongs to H, so the sum equals y " H .I fi is not incident to H, then by Lemma 9 we have

ÿ CoeC y " Hfi{(i,C)} = "(H) 3k ≠|H| 6 ÿ j=1 (k/2 ≠ deg H (C j )) = "(H)=y " H , since 6 • k/2=3k and q 6
j=1 deg H (C j )=|H|. Finally we prove that y " satisfies the set of constraints (3.2) for every processing time. Fix p and H. Since y " is supported by six configurations, we have

ÿ ioeM ÿ CoeC m(p, C)y " Hfi{(i,C)} = ÿ ioeM 6 ÿ j=1 m(p, C j )"(H fi{(i, C j )}).
There are exactly two configurations

C p 1 ,C p 2 oeC -such that m(p, C p 1 )=m(p, C p 2 )=1
, and for the others it is zero, so

6 ÿ j=1 m(p, C j )"(H fi{(i, C j )})="(H fi{(i, C p 1 )})+"(H fi{(i, C p 2 )}). Let fi M (H)={i oe M : deg H (i)=1
} be the subset of machines incident to H.W e split the sum over i oe M into two parts, i oe fi M (H) and i/ oe fi M (H). For the first part,

ÿ ioefi M (H) ("(H fi{(i, C p 1 )})+"(H fi{(i, C p 2 )})) = "(H)(deg H (C p 1 ) + deg H (C p 2 ))
since "(H fi{(i, C p 1 )}) is either "(H) or 0 depending on whether (i, C p 1 ) oe H, and the same holds for C p 2 . For the second part, using Lemma 9 we have that for ¸oe{1, 2},

ÿ i/ oefi M (H) "(H fi{(i, C p ¸)})= "(H) 3k ≠|H| ÿ i/ oefi M (H) (k/2 ≠ deg H (C p ¸)) = "(H)(k/2 ≠ deg H (C p ¸)), since |H \ fi M (H)| =3 k ≠|H|.
Thanks to cancellations, we get precisely what we want,

ÿ ioeM ÿ CoeC m(p, C)y " Hfi{(i,C)} = ÿ ¸oe{1,2} "(H)(deg H (C p ¸)+k/2 ≠ deg H (C p ¸)) = k • "(H)=n p y " H .
Chapter 4

Lovász-Schrijver (LS + )H i e r a r c h y

In contrast to the last chapter, we introduce the Lovász-Schrijver hierarchy in a general context. This is due to the simplicity behind the construction of the relaxations. In what follows, if y =( a, x) oe R ◊ R d , we denote y ÿ = a and

y i = x i for all i oe [d]. Consider the operator N + on the family of convex cones in R ◊ R d defined as follows. Let R ™ R ◊ R d be a convex cone. Then, y oe N + (R) if and only if there exists a symmetric matrix Y ™ R (d+1)◊(d+1) such that (i) y = Ye ÿ = diag(Y ), (ii) for all i oe [d], Ye i ,Y(e ÿ ≠ e i ) oe R, (iii) Y is positive semidefinite,
where e i denotes the vector with a one in the i-th entry and zero elsewhere. A matrix Y satisfying the conditions above is sometimes called in the literature the protection matrix of y. The following property comes directly from the definition of the operator.

Proposition 11. Let R be a convex cone. Then, N + (R) is a convex cone and N + (R) ™ R. Proof. Let y, z oe N + (R) and ⁄, µ oe R + . It is enough to show that ⁄y + µz oe N + (R).
Let Y and Z be protection matrices for y and z respectively. Then, ⁄Y + µZ is a protection matrix for ⁄y + µz. Conditions (i) and (ii) come from the linearity of diag and the matrix product. Since the set of symmetric positive semidefinite matrices is a convex cone, the condition (iii) follows as well. Now we prove the second property. Let y oe N + (R). In particular, Ye 1 ,Y(e ÿ ≠e 1 ) oe R. Since R is a convex cone, it follows that Ye 1 + Y (e ÿ ≠ e 1 )=Ye ÿ = y by condition (i), and therefore y oe R.

Given a polytope

P ™ [0, 1] d , let Q = {(a, x) oe R + ◊P : x/a oe P }™R + ◊R d be the lifted convex cone of P . The level r relaxation of the LS + hierarchy, N r + (Q) ™ R◊R d , is defined recursively as follows: N 0 + (Q)=Q and N r + (Q)=N + (N r≠1 + (Q))
. Proposition 11 guarantees the recursive definition is well defined ant it defines a nested family. Furthermore, the family is guaranteed to converge to the cone spanned by the integer vectors at Q at level d [START_REF] Lovász | Cones of matrices and set-functions and 0-1 optimization[END_REF]Theorem 1.4].

Integrality gap of LS + : Proof of Theorem 1(iii)

To prove the integrality gap for LS + we follow an inductive argument. We start from the configuration LP, clp(T ), and we denote by Q k the lifted convex cone of clp(T ) for instance I k and T = 1023. For simplicity, we sometimes use the notation iC for the ordered pair (i, C), as it is usually done for directed graphs.

Let A be an M -matching in M ◊C -, as defined in Section 3.2. The partial schedule y(A) oe R M ◊C is the vector such that for every i oe M and j oe{1, 2,...,6}, y(A) iC j = "(A fi{(i, C j )})/"(A), and zero otherwise. Below is the key Lemma that implies the main theorem. We postpone its proof to the end of the next section.

Lemma 12. Let k be an odd integer and r AEÂk/2Ê. Then, for every M -matching A of cardinality Âk/2Ê≠r in M ◊C -, we have

y(A) oe N r + (Q k ).

Proof of Theorem 1(iii).

Let k be such that n =15k + ¸where k is the greatest odd integer such that 15k AE n. Consider instance I k defined in Section 2.1, T = 1023 and r = Âk/2Ê. By Lemma 31,f o rA = ÿ we obtain y(ÿ

) oe N r + (Q k ). C 2 C 1 C 1 machine 1 machine 2 machine 3 machine 4
. . . In the following we provide two lemmas that describe structural properties of every partial schedule. The first of them justifies the intuition behind their name: If A is an M -matching, the corresponding partial schedule is integral for every machine incident to A. Therefore, all these machines are scheduled integrally and the whole solution can be seen as partial schedule for the instance.

Lemma 13.

Let A be an M -matching in M ◊C -. Then, y(A) is integral for every machine incident to A. [6] \{j}, the set A fi{(i, C ¸)} is not an M -matching and thus y(A) iC ¸=0 .

Proof. If C/ oeC -then y(A) iC = 0 by definition. If (i, C j ) oe A then y(A) iC j = "(A fi{(i, C j )})/"(A)="(A)/"(A)=1. F or¸oe

Integrality gap of LS

+ : Proof of Theorem 1(iii) Chapter 4
The second lemma below provides the base case for the induction in the proof of Lemma 31 and complements the lemma above: The partial schedules are indeed feasible solutions for the configuration LP. Lemma 14. Let A be an M -matching in M ◊C -of cardinality at most Âk/2Ê. Then, y(A) oe clp(T ).

Proof. We note that y(A) iC = y " Afi{(i,C)} /y " A , and then the feasibility of y(A) in clp(T ) is implied by the feasibility of y " in SA r (clp(T )), for r = Âk/2Ê.

The protection matrices.

Given A an M -matching of M ◊C -and the respective partial schedule y(A), let Y (A) be the real symmetric matrix with rows and columns indexed in {ÿ} fi (M ◊C), such that its principal submatrix indexed by {ÿ} fi (M ◊C -) equals

A 1 y(A) € y(A) Z(A) B , where Z(A) iC j ,¸C h = "(A fi{(i, C j ), (¸, C h )})/"(A).
All the other entries of the matrix Y (A) are equal to zero. The matrix Y (A) provides the protection matrix we need in the proof of the key Lemma. Condition (i) in the definition of the protection matrix is guaranteed by construction. To check that condition (ii) is satisfied we require the following lemma.

Lemma 15.

Let A be an M -matching in M ◊C -and i a non-incident machine to A. Then,

q 6 j=1 Y (A)e iC j = Y (A)e ÿ .
Finally, condition (iii) is the more technical condition to be checked. It requires the use of algebraic tools and a series of operations to reduce the dimensionality of the problem. We postpone the proof of Theorem 4 to Section 4.2. We then prove Lemma 15 and posteriorly we are ready to prove the key Lemma. Lemma 15. Let S be the index of a row of Y (A). If S/ oe {ÿ} fi (M ◊C -) then that row is identically zero, so the equality is satisfied. Otherwise,

Theorem 4. For every M -matching

A in M ◊C -such that |A|AEÂk/2Ê, the matrix Y (A) is positive semidefinite. Proof of
e € S 6 ÿ j=1 Y (A)e iC j = 1 "(A) 6 ÿ j=1 "(A fi{(i, C j )}fiS).
If A fi S is not an M -matching then "(A fi S fi{i, C j }) = 0 for all i and j oe [6], and e € S Y (A)e ÿ = "(A fi S) = 0, so the equality is satisfied.

If A fi S is an M -matching, then 1 "(A) 6 ÿ j=1 "(A fi{(i, C j )}fiS)= "(A fi S) "(A) 6 ÿ j=1 "(A fi S fi{(i, C j )}) "(A fi S) = e € S Y (A)e ÿ 6 ÿ j=1 y " AfiSfi{(i,C j )} y " AfiS = e € S Y (A)e ÿ ,
since y " is a feasible solution for the SA hierarchy and threfore the summation above is equal to 1 due to the machine constraints (3.1).

Proof of Lemma 31. We proceed by induction in r.F o r r = 0 this is implied by Lemma 14, so now suppose that it holds for r = t.L e ty(A) be a partial schedule of A of cardinality Âk/2Ê≠t ≠ 1. We prove that the matrix Y (A) is a protection matrix for y(A). It is symmetric by definition, and

Y (A)e ÿ =( 1 , diag(Y (A))) = (1,y(A)), so condition (i) is satisfied. Thanks to Theorem 4 the matrix Y (A) is positive semidefinite, that is condition (iii).
It remains to check that condition (ii) is fulfilled. Let (i, C) be such that y(A) iC oe (0, 1). In particular, by Lemma 13 we have (i, C) / oe A and C oeC -. We claim that Y (A)e iC /y(A) iC is equal to (1,y(A fi{(i, C)})). If S indexes a row not in M ◊C -then the respective entry in both vectors is zero, so the equality is satisfied. Otherwise,

e € S Y (A)e iC y(A) iC = "(A fi{(i, C)}fiS) "(A fi{(i, C)}) = y(A fi{(i, C)}) S .
The cardinality of the M -matching A fi{(i, C)} is equal to |A| +1=Âk/2Ê≠t, and therefore by induction we have that

Y (A)e iC /y(A) iC =(1,y(A fi{(i, C)})) oe N t + (Q k ). Now we prove that the vectors Y (A)(e ÿ ≠ e iC )/(1 ≠ y(A) iC ) are feasible for N t + (Q k )
. By Lemma 15 we have that for every ¸oe{1, 2,...,6},

Y (A)(e ÿ ≠ e iC ¸) 1 ≠ y(A) iC ¸= ÿ joe[6]\{¸} A y(A) iC j q joe[6]\{¸} y(A) iC j B y(A fi{(i, C j )}),
and then Y (A)(e ÿ ≠e iC ¸)/(1 ≠y(A) iC ¸) is a convex combination of the partial schedules {y(A fi{(i, C j )}):j oe [6] \{¸}} µ N t + (Q k ), concluding the induction.

The protection matrices are PSD

In this section we provide a full proof of Theorem 4. To prove that Y (A) is a positive semidefinite matrix we perform several transformations of the original matrix that preserve the property of being positive semidefinite or not. We start with a short summary of the proof.

Proof scheme. First, we remove all those zero columns and rows. Then, Y (A) is positive semidefinite if and only if its principal submatrix indexed by {ÿ} fi (M ◊ C -) is positive semidefinite. We construct the matrix Cov(A) by taking the Schur's Complement of Y (A) with respect to the entry (ÿ, ÿ).

The resulting matrix is positive semidefinite if and only if Y (A) is positive semidefinite. After removing null rows and columns in Cov(A) we obtain a new matrix, Cov + (A), which can be written using tensor products as

I ¢ Q +(J ≠ I) ¢ W , with Q, W oe R 6◊6 , W = -Q
for someoe (≠1, 0) and I,J being the identity and the allones matrix, respectively. By applying a lemma about block matrices in [START_REF] Gvozdenovic | The operator  for the chromatic number of a graph[END_REF], Y (A) is positive semidefinite if and only if W is positive semidefinite.

Finally, the matrix W is equal to D u ≠ uu € for some u oe R 6 and D u is a diagonal matrix such that diag(D u )=u. By applying Jensen's inequality it follows that W is positive semidefinite.

Take the Schur's Complement of (ÿ, ÿ)

Remove all the zero rows and columns

Use the block symmetry to reduce dimensionality We now continue with the full argument. The first basic operation we can perform over the matrix is to remove null rows and columns. In the case of our protection matrices, there are many rows and columns that are equal to zero by construction.

Lemma 16. A symmetric matrix X oe R E◊E is positive semidefinite if and only if the principal submatrix of non-null columns and rows is positive semidefinite.

Proof. Let X oe R F ◊F be the matrix obtained by removing the null rows and columns of x. Then,

z € Xz = q i,joeE X ij z i z j = q i,joeF X ij z i z j = z € F Xz F , where z F oe R F is the restriction of Z to the variables in F . It follows that z € Xz Ø 0 if and only if z € F Xz F Ø 0.
Therefore, in order to prove that a matrix is positive semidefinite we can remove in advance those null rows and columns. In the following lemma we describe a reduction based on a congruent transformation of a matrix known as Schur's complement. Given the symmetric matrix

X = A NB B € C B with N invertible, the Schur's complement of N in X is the matrix S = C ≠B € N ≠1 B.

Lemma 17. If N is positive definite, then X is positive semidefinite if and only if S is positive semidefinite.

A proof of this fact can be found in [54, Theorem 7.7.9 on page 496]. We apply the two previous transformations to Y (A) as described in the following lemma.

Lemma 18. Let A be an M -matching in M ◊C -. Then, the matrix Y (A) is positive semidefinite if and only if Z(A) ≠ y(A)y(A)

€ is positive semidefinite.

Proof. Thanks to Lemma 16 the matrix Y (A) is positive semidefinite if and only if its principal submatrix indexed by {ÿ} fi (M ◊C -) is positive semidefinite, since every other row and column are zero. The Schur's complement of the entry Y (A) ÿ,ÿ

=1 corresponds to Z(A)≠y(A)y(A) € . A direct application of Lemma 17 implies that Y (A) is positive semidefinite if and only if Z(A) ≠ y(A)y(A)

€ is positive semidefinite.

Further removals. We denote by Cov(A) the matrix Z(A)≠y(A)y(A) € , the covariance matrix of y(A).

In the proof of Lemma 18 we removed first all those null rows and columns in Y (A). In fact, in the new matrix Cov(A) there are null rows and columns that can be removed of the matrix, so we can perform this operation again. Recall that fi M (A) is the set of machines incident to A, and let Cov + (A) be the principal submatrix of Cov(A) obtained by removing every row and column indexed by E(fi M (A)) = {(i, C j ):i oe fi M (A),j oe{1, 2,...,6}}.

Lemma 19. Let A be an M -matching in M ◊C -. Then, Y (A) is positive semidefinite if and only if Cov

+ (A) is positive semidefinite.
Proof. We prove that for every (i, C j ) oe E(fi M (A)), Cov(A)e iC j = 0. By expanding,

e € ¸Ck Cov(A)e iC j = 1 "(A) "(A fi{(¸, C k ), (i, C j )}) ≠ y(A) iC j y(A) ¸Ck .
By Lemma 13, if i is a machine incident to A we have y(A) iC j =1 {(i,C j )oeA} , and by the definition of the function " we have that it is supported over M -matchings only.

Then,

"(A fi{(¸, C k ), (i, C j )})="(A fi (¸, C k )})1 {(i,C j )oeA}
, and

e € ¸Ck Cov(A)e iC j = A 1 "(A) "(A fi{(¸, C k )}) ≠ y(A) ¸Ck B 1 {(i,C j )oeA} =0,
because of the definition of the partial schedule y(A). The Lemma follows by a direct application of Lemma 16.

Note that if machine i is not incident to A, the values {y(A) iC j : j oe [6]} do not depend on the machine, but only on A. This motivates the definition of the vector ‹(A) oe R 6 such that

‹(A) j = k/2 ≠ deg A (C j ) 3k ≠|A| ,
for every j oe{1, 2,...,6}.I fy(A) is a partial schedule, for every machine incident to A the entries y iC j are in {0, 1}, which is in total 3|A| entries. This is why Cov + (A) has a very particular structure: If we order the rows and columns according to machines, a block structure appears. To properly define this we require some notation. Let U oe R p◊q and T oe R r◊s . Then, the tensor product between U and T , U ¢ T , is the matrix

Q c c a U 11 T. . .U 1q T . . . . . . . . . U p1 T. . .U pq T R d d b oe R pr◊qs .
Proposition 20. Let A, B, C, D four matrices such that the products AC and BD are well defined. Then, the following holds:

(i) (A ¢ B)(C ¢ D)=AC ¢ BD. (ii) (A ¢ B) € = A € ¢ B € .

The protection matrices are PSD

Chapter 4

A proof of (i) can be found at [53, Lemma 4.2.10 on page 244] and (ii) is direct from the definition. The fractional part of y(A) corresponds to 1 ¢ ‹(A), where 1 is the vector in R 3k≠|A| with every entry equal to 1. Furthermore, the value Z(A) iC j ,¸C ¸= "(A) j¸i s independent of the machines when i, ¸are not incident to A,

"(A) j¸= Y _ _ _ _ _ _ ] _ _ _ _ _ _ [ (k/2 ≠ deg A (j))(k/2 ≠ deg A (¸)) (3k ≠|A|)(3k ≠|A|≠1) if j " = ¸, (k/2 ≠ deg A (j))(k/2 ≠ deg A (j) ≠ 1) (3k ≠|A|)(3k ≠|A|≠1) if j = ¸.
Then, we can fully express the matrix Cov + (A) in terms of tensor products involving "(A) and ‹(A)

I ¢ D ‹ (A)+(J ≠ I) ¢ "(A) ≠ (1 ¢ ‹(A))(1 ¢ ‹(A)) € , ( 4.1)
where I is the 3k ≠|A| dimensional identity matrix, J is the 3k ≠|A| dimensional all-ones matrix and

D ‹ (A) oe R 6◊6 is such that D ‹ (A) jj = ‹(A) j for j oe{ 1,...,6}, and D ‹ (A) jh = 0 when j " = h.
The key consequence is that we can reduce the task of proving that Y (A) is positive semidefinite to prove the same for matrices of constant dimension.

Block matrices. We say that a matrix X oe R rn◊rn belongs to the (r, n)-block symmetry set, Sym n r , if there exist matrices D, E oe R r◊r such that

X = I ¢ D +(J ≠ I) ¢ E. For example, when n =3, X = Q c a DEE EDE EED R d b .
The following lemma characterizes the set of positive semidefinite matrices in Sym n r .

Lemma 21 ([49]).

Let X = I ¢ D +(J ≠ I) ¢ E oe Sym n r . Then, X is positive semidefinite if and only if i) D ≠ E is positive semidefinite and ii) D +(n ≠ 1)E is positive semidefinite.
As a consequence, we reduce the dimensionality of the problem to r. In particular, Cov + (A) belongs to Sym and it is equal to

I ¢ ∆(A) ≠ (J ≠ I) ¢ 1 3k ≠|A|≠1 ∆(A),
where

∆(A)=D ‹ (A) ≠ ‹(A)‹(A) € .
Proof. We check first that Cov(A) + oe Sym 3k≠|A| 6

. By Proposition 20, we have

(1 ¢ ‹(A))(1 ¢ ‹(A)) € =(1 ¢ ‹(A)) 1 1 € ¢ ‹(A) € 2 = J ¢ ‹(A)‹(A) € .
Replacing this in the expression in 4.1 we get

Cov + (A)=I ¢ D ‹ (A)+(J ≠ I) ¢ "(A) ≠ J ¢ ‹(A)‹(A) € = I ¢ 1 D ‹ (A) ≠ ‹(A)‹(A) € 2 +(J ≠ I) ¢ 1 "(A) ≠ ‹(A)‹(A) € 2 = I ¢ ∆(A)+(J ≠ I) ¢ 1 "(A) ≠ ‹(A)‹(A) € 2 , so it remains to check that "(A) ≠ ‹(A)‹(A) € = ≠1/(3k ≠|A|≠1) • ∆(A). Consider two configurations C j " = C ¸.
Then, the non-diagonal entry (j, ¸) is equal to

"(A) j¸≠ ‹(A) j ‹(A) ¸= (k/2 ≠ deg A (j))(k/2 ≠ deg A (¸)) (3k ≠|A|)(3k ≠|A|≠1) ≠ ‹(A) j ‹(A) = A 3k ≠|A| 3k ≠|A|≠1 ≠ 1 B ‹(A) j ‹(A) ¸= ≠ 1 3k ≠|A|≠1 ∆(A) j¸.
For a diagonal element, we have

"(A) jj ≠ ‹(A) 2 j = (k/2 ≠ deg A (j))(k/2 ≠ deg A (j) ≠ 1) (3k ≠|A|)(3k ≠|A|≠1) ≠ ‹(A) 2 j = 3k ≠|A| 3k ≠|A|≠1 A ‹(A) 2 j ≠ 1 3k ≠|A| ‹(A) j B ≠ ‹(A) 2 j = ≠ 1 3k ≠|A|≠1 (‹(A) j ≠ ‹(A) 2 j )=≠ 1 3k ≠|A|≠1 ∆(A) jj .
In addition with Lemma 21 we have the ingredients to prove that Cov + (A) is a positive semidefinite matrix when |A|AEÂk/2Ê.

if i) ∆(A) ≠ 1 3k≠|A|≠1 ∆(A)= 3k≠|A| 3k≠|A|≠1 ∆(A) is positive semidefinite, and ii) ∆(A) ≠ (3k ≠ |A|≠1) • 1 3k≠|A|≠1 ∆(A) = 0 is positive semidefinite.
The last condition is trivially satisfied, and then Cov + (A) is positive semidefinite if and only if ∆(A) is positive semidefinite. Given any vector x oe R 6 , we have

x € ∆(A)x = 6 ÿ j=1 ‹(A) j x 2 j ≠ Q a 6 ÿ j=1 ‹(A) j x j R b 2 .
The vector ‹(A) oe R 6 is non-negative if |A|AEÂk/2Ê. As it satisfies that ΋(A)Î 1 =1, by applying Jensen's inequality with the function "(w)=w 2 the latter expression is non-negative for every x oe R 6 . Then, Cov + (A) is positive semidefinite, and thanks to Lemma 19 we conclude that Y (A) is positive semidefinite.

Chapter 5 Break symmetries to approximate

A natural source of symmetry in our problem comes from the fact that the machines are identical: Given a schedule, we obtain other schedules with the same makespan by permuting the assignment over the machines. A second source of symmetry in the problem arises from permuting jobs with the same processing time.

The symmetric nature of the combinatorial problem does not directly imply that a formulation is symmetric, but most of the time the natural formulations reflect the symmetries as well. This is the case for the two formulations considered so far in this work, the assignment LP and the configuration LP. In what follows we introduce the necessary algebraic tools for this chapter and formalize all these notions.

Group invariant sets

Given a set of variables D, we denote by GL(R D ) the set of invertible matrices in R D◊D . For a group G, we say that Φ :

G ae GL(R D ) is a matrix representation over R D if Φ is a G-homomorphism, that is, for every g, h oe G we have Φ(g)Φ(h)=Φ(gh). A polytope K ™ R D is
said to be G-invariant if for every g oe G and x oe K, Φ(g)x oe K. We say that G induces an action over K, by the function fl :

G ◊ K ae K such that fl(g, x)=Φ(g)x.
A group of particular interest is the symmetric group of order d, denoted by S d .I t corresponds to the set of permutations over {1,...,d} and the composition as product. This group has a matrix representation P over R d given by the permutation matrices: For every ¸, k oe{1,...,d}, let P ( ‡) ¸k = 1 if and only if ‡(¸)=k. It is not hard to check that for every scheduling instance and every T>0, the assignment polytope is S m -invariant, where the set of machines is M = {1,...,m}. In this case, the variables are indexed by the set M ◊ J and the representation of S m over R M ◊J is constructed as follows: Given ‡ oe S m , define Φ( ‡)=P ( ‡) ¢ I, where I is the identity matrix in R J◊J . The fact that Φ is a matrix representation follows using the properties in Proposition 20:F o re v e r y ‡, fi oe S m ,

Φ( ‡)Φ(fi)=(P ( ‡) ¢ I)(P (fi) ¢ I)=P ( ‡)P (fi) ¢ I 2 = P ( ‡fi) ¢ I =Φ( ‡fi).
Let ‡ oe S m and x oe assign(T ). For every j oe J, we have

ÿ ioeM (Φ( ‡)x) ij = ÿ ioeM x ‡(i)j = ÿ ioeM x ij =1,
since ‡ is a permutation of M . Therefore, every job constraint remains the same when permuting machines. Now given i oe{1,...,m}, we have

ÿ joeJ (Φ( ‡)x) ij p j = ÿ joeJ x ‡(i)j p j AE T,
since the last corresponds to the machine constraint for ‡(i). Observe that having every right hand side in the machine constraint equal to T is relevant to check the invariance. If we had different machine availabilities then is not clear that the program remains invariant using the same representation. Then we should allow the group to act also over the coefficients in the linear functions defining the polytope. We can also observe that S m is acting over the configuration LP. The representation of the permutation group is constructed in a very similar way, as well as checking that clp(T ) is S m -invariant. Scheduling identical machines belongs to a larger class of partitioning problems. The common feature of all these problems is to have a set of elements that are to be partitioned in subsets, each of them meeting some constraints. In this case, we look for a partition of the jobs, where every part satisfies a packing constraint.

Symmetry breaking inequalities

Recall that in the configuration LP we look for an assignment of machines to the set of configurations C. For example, in the hard instances obtained from the Petersen graph in Chapter 2 (see Figure 2.1) the number of configurations for T = 1023 is equal to six, so every feasible schedule should have many machines scheduled according to the same configuration. In what follows, we introduce a set of constraints that guarantee every integer solution in the polytope to obey a specific order on the configurations over the machines. Recall that the set of machine is the set M = {1,...,m}. Therefore, if we knew that a machine ¸is scheduled according to a given configuration C, it should be that every machine smaller (larger) than ¸is scheduled respecting the order on the configurations set. This is a way of breaking the machine symmetries since we are restricting the set of possible assignments.

We need some notation before introducing the symmetry breaking constraints. Suppose we have a partitioning J of the job set J into s parts, J = {J 1 ,...,J s }. In principle, the partition is arbitrary. An example of such a partition is given in the following way. Suppose the job sizes are ordered from largest to smallest, that is p 1 >p 2 > ••• >p s where s = |{p j : j oe J}| is the number of different job sizes. Then, we could define the partition such that J q = {j oe J : p j = p q } for every q oe [s], and we call it the job-sizes partition.

In this context, a configuration C is a multiset of elements in {1,...,s}. Recall that for every q oe{ 1,...,s}, the multiplicity of q in C, m(q, C), is the number of times that p q appears repeated in C. For example, if s = 3 and C = {1, 1, 1, 2}, we have m(1,C)=3 ,m(2,C) = 1 and m(3,C) = 0. We denote by C the set of all configurations. Observe that it coincides with the configuration notion introduced in Chapter 1 if we consider the job-sizes partition.

We say that a configuration C is lexicographically larger than S, and we denote C> lex S, if there exists q oe [s] such that m(¸, C)=m(¸, S) for all ¸<qand m(q, C) > m(q, S). Following the example with s = 3, the configuration

C = {1, 1, 1, 2, 2} is lexicographically larger than S = {1, 1, 1, 2, 3} since m(1,C)=m(1,S) = 3 and m(2,C)=2>m(2,S)=1.
Given a positive integer number B, consider the polytope assign(B, T) given by assign(T )

fl m≠1 ‹ i=1 Y ] [ x oe R M ◊J : s ÿ q=1 B s≠q ÿ joeJq 1 x ij ≠ x (i+1)j 2 Ø 0 Z \ .
Sometimes, to avoid confusion we use the notation assign(J, B, T ) to emphasize that we are considering the polytope for the jobs set J. We also remark that the symmetry breaking constraints depend on the partitioning of J. Given a subset of jobs K µ J such that q joeK p j AE T , we denote by conf(K) the configuration such that for every q oe{1,...,s}, m(q, conf(K)) = |KflJ q |. We then say that conf(K) is the configuration induced by K and we denote by C the set of all possible configurations induced in this way. Observe that > lex defines a total order over C.

In the following we show that for sufficiently large, but polynomially sized B,every integer solution in the polytope obeys the lexicographic order on configurations over the machines. More specifically, given a feasible integer solution x oe assign(T ), for every machine i oe M let C i (x) oeCbe the configuration defined by the number of jobs for each possible part that are scheduled in i according to x, that is, for every q oe{1,...,s}, m(q, C i (x)) = q joeJq x ij . Theorem 5. There exists B = O(|J| 2 ) such that for every integer solution x oe assign(B, T), C i (x) Ø lex C i+1 (x) for every machine i oe M \{m}.

In general, the polytope above is not S m -invariant, but it is a valid formulation for the problem of finding a schedule with makespan at most T . More specifically, we show that if there is a schedule with makespan at most T , then there is an integer solution in assign(B, T). Lemma 23. Suppose there is an integer solution in assign(T ). Then, there exists B = O(|J| 2 ) for which there is an integer solution in assign(B, T).

We prove the theorem statements above by introducing an intermediate result connecting the lexicographic order over the configurations and the symmetry breaking constraints shown above. Given B oe N, let L B : CaeR be the function such that for every configuration C oeC,

L B (C)= s ÿ q=1 B s≠q m(q, C).
Recall that the lexicographic order over the configurations induces a total order over C. We show that exists a polynomially sized value of B for which L B is a strictly increasing function, that is, if C< lex S then L B (C) < L B (S). Using this result we then prove Theorem 5.

Lemma 24. Let B>2s max qoe[s]

|J q |. Then, L B is strictly increasing.

Proof of Theorem 5. Fix a machine i oe M \{m}. Since x is an integer solution in assign(B, T), we have C i (x), C i+1 (x) oeC. The symmetry breaking constraints implies that

0 AE s ÿ q=1 B s≠q (m(q, C i (x)) ≠ m(q, C i+1 (x))) = L B (C i (x)) ≠L B (C i+1 (x)). Applying Lemma 24 for B =1+2s max qoe[s] |J q | = O(|J| 2 ) it holds that L B is strictly increasing and therefore C i (x) Ø lex C i+1 (x).
Proof of Lemma 23. Consider an integer solution x oe assign(T ). Since the lexicographic relation defines a total order over C, there exists a permutation ‡ oe S m such that C ‡(i) (x) Ø lex C ‡(i+1) (x)f o re v e r yi oe M \{m}. Consider the new schedule x obtained by permuting the solution according to ‡, that is, xij = x ‡(i)j for every (i, j) oe M ◊ J. Then, for every i oe M \{m} it follows that

s ÿ q=1 B s≠q ÿ joeJq 1 xij ≠ x(i+1)j 2 = s ÿ q=1 B s≠q 1 m(q, C ‡(i) (x)) ≠ m(q, C ‡(i+1) (x)) 2 = L B (C ‡(i) (x)) ≠L B (C ‡(i+1) (x)) Ø 0,
where the last inequality holds by Lemma 24. We conclude that x oe assign(B, T).

The Lasserre/SoS (Las) Hierarchy

Chapter 5

We recall that having B of polynomial input size is relevant at the moment of solving the linear program assign(B, T). In particular, the input size is O(|J| 2 • log(B s )) = O(poly(|J|)), and so in can be solved in time O(poly(|J|)) using, for example, the Karmakar algorithm or the Ellipsoid method [START_REF] Schrijver | Theory of linear and integer programming[END_REF]Chapter 15]. In what follows, we use a superscript over the configurations to indicate its lexicographic order, that is,

C 1 >C 2 >C 3 > ••• >C |C| .
Proof of Lemma 24. Consider two configurations C, S oeC such that C> lex S.L e tq be the smallest in {1,...,s} integer such that the multiplicities of the configurations are different, that is, m(¸, C)=m(¸, S)f o re v e r y¸<q. For the sake of contradiction suppose that m(q, C) <m (q, S). In particular, every term up to max{0, q ≠ 1} in the summation defining L B (C) ≠L B (S) is equal to zero. By upper bounding the summation from min{s, q +1} we obtain that

s ÿ q=min{s,q+1} B s≠q (m(q, C) ≠ m(q, S)) AE s ÿ q=min{s,q+1} B s≠q (|m(q, C)| + |m(q, S)|) AE s ÿ q=min{s,q+1} B s≠q • 2|J q | < A 2s max qoe[s] |J q | B B s≠q≠1 AE B • B s≠q≠1 ,
and since m(q, S) ≠ m(q, C) Ø 1 it follows that s ÿ q=q B s≠q (m(q, C) ≠ m(q, S)) <B s≠q + B s≠q (m(q, C) ≠ m(q, S)) <B s≠q (1 + m(q, C) ≠ m(q, S)) < 0, yielding to the contradiction.

The Lasserre/SoS (Las) Hierarchy

The Lasserre/SoS hierarchy is the strongest lift & project operator among the ones considered in this work, that is Sherali-Adams (SA) and Lóvasz-Schrijver (LS + ). Before introducing the relaxations obtained from the hierarchy, we require some notation about moment matrices, that play a role in what follows. Then we introduce the hierarchy in a self-contained way. Given a set E be a set and r oe N, recall that P r (E)={A ™ E : |A|AEr}.F o rav e c t o rz oe R P 2r (E) , the r-moment matrix, M r (z) oe R Pr(E)◊Pr(E) , is such that for every U, V oeP r (E), M r (z) U,V = z U fiV . Observe that this matrix is symmetric. We consider an operation ı called the shift product between a vector z oe R Pr(E) and a vector a oe R P 1 (E) such that for all U oeP r (E),

(aız) U = ÿ eoeE a e x U fi{e} ≠ a ÿ x U ,
recalling that a e = a {e} for simplicity when e is a singleton. Given a scheduling instance and T>0, for every i oe M let pack i oe R P 1 (M ◊J) be such that pack i ÿ = T , pack i ¸j = ≠p j if ¸= i and zero otherwise. Similarly, for every i oe M \{ m} let break i oe R P 1 (M ◊J) be such that

break i ¸j = Y _ _ ] _ _ [ B s≠q
if ¸= i and j oe J q , for all q oe{1,...,s}, ≠B s≠q if ¸= i + 1 and j oe J q , for all q oe{1,...,s}, 0 otherwise.

The level r Lasserre/SoS relaxation, Las r (assign(B, T)), is an SDP in [0, 1] P 2r+2 (M ◊J) ,

ÿ ioeM
x Ifi{(i,j)} ≠ x I = 0 for all j oe J, for all I oeP 2r+1 (M ◊ J), (

M r (pack i ıx) ≤ 0 for all i oe M, (

M r (break i ıx) ≤ 0 for all i oe M \{m}, (5.3) M r+1 (x) ≤ 0, (5.4) x ÿ =1.

(5.5)

Balanced partitionings

Observe that Las 0 (assign(B, T)) is at least as strong as assign(B, T). In this section we study the integrality gap of the SDP relaxations obtained from the Lasserre/SoS hierarchy. More specifically, we show that after a small number of rounds that depends on the configurations set C, and therefore on the partitioning J , the integrality gap can be arbitrarily close to one. Recall that whereas the total number of jobs can be large, the number of configurations could be small and therefore we obtain better bounds. We say a partitioning J is --balanced, with -Ø 1, if for every K, H ™ J such that conf(K) = conf(H),

ÿ joeK p j AE - ÿ joeH p j .
Other parameter that plays a key role is the maximum number of jobs that can be scheduled in the same machine with makespan at most T , that is,

⁄ = max Y ] [ |K| : ÿ joeK p j AE T Z \ .
For example, if we knew that p j Ø T/3forev eryj oe J, then ⁄ AE 3. The following is the main result of this chapter: Given a balanced partitioning of J and its induced configurations C, there is a level of the hierarchy for which its feasibility implies the existence of an integral solution with a makespan close to T . Provided that B is chosen accordingly to Lemma 5, it gives us a schedule respecting the lexicographic order of configurations over the machines.

An approximation scheme for Scheduling

Chapter 5 Theorem 6. Consider a scheduling instance, T>0 and an --balanced partitioning of the set J. Suppose the ⁄|C| = • (C) level of the Lasserre/SoS hierarchy over assign(B, T) is feasible, that is,

Las • (C) (assign(B, T)) " = ÿ.
Then, there exists a schedule, x lex oe assign(B, -T)fl{0, 1} M ◊J , that is, with makespan at most -T . Furthermore, it can be found in time

|J| O(• (C)) .
The value • (C)=⁄|C| can be improved, but this is good enough for this exposition. If we go back to the hard instances shown in Chapter 2, we observe that for T =1023 there is a constant number of configurations for all the instances {I k } koeN if we consider the job-sizes partition, since there are only 15 different job sizes. Furthermore, since the smallest job size in the instances is 33, we have that ⁄ AE 1023/33 = 31. Recall that for T = 1023 there is no feasible schedule for the instance and the job-sizes partition is 1-balanced. Therefore, for every k oe N, there is an O(1) level Lasserre relaxation for T = 1023 which is equal to the empty set.

An important observation is that we assume the number of machines m to be greater than • (C), since otherwise the theorem follows by a direct application of Theorem 3 in Chapter 3. The proof of this theorem follows in a slightly similar way to that of the Machine Decomposition Lemma (see Chapter 3, Lemma 6). There, the argument was based on an induction over the number of machines that are to be integral. We leave the full proof of Theorem 6 to Section 5.6, and in the following section we show how to obtain a polynomial time approximation scheme as corollary of the main theorem.

An approximation scheme for Scheduling

An idea that has been frequently exploited for designing approximation schemes in scheduling and packing problems is to split the instances into long jobs and short jobs. Then, each sub-instance is solved or approximated by using suitable techniques, and merged afterwards in order to provide a solution for the original problem. Rounding the numeric values of the instances plays a key role in this approaches since it allows to reduce the underlying combinatorics. In particular, it allows exhaustive enumeration in some cases.

We provide an approximation scheme that uses the idea of splitting the instance into long and short jobs, but we do not round the numeric values. In what follows, given Á>0, we say that a job j oe J is long if p j Ø ÁT , and it is short otherwise. The subset of long jobs is denoted by J long and the short jobs are J short = J \ J long .W e consider a partitioning that simulates the rounding by grouping jobs with a similar processing time. More specifically, for every q oe{1,...,(1 ≠ Á)/Á 2 }, let

J q = ; j oe J long : 3 1 Á + q 4 Á 2 T>p j Ø 3 1 Á + q ≠ 1 4 Á 2 T < ,
and we call this the Á-partitioning of the long jobs. We show next that this partitioning is arbitrarily close to being 1-balanced, and therefore we can try to schedule long jobs using the main theorem.

Lemma 25. For every Á>0, the Á-partitioning is (1 + Á)-balanced.

Proof. Consider K, H ™ J such that conf(K) = conf(H)=C for the Á-partitioning J .

In particular, for every q oe{1,...,|J |} we have that |K fl J q | = m(q, C)=|H fl J q |, and so there exists a bijection Ï q : K fl J q ae H fl J q . Furthermore, for any pair of jobs j, ¸oe J q it holds

p j p ¸AE 1 1 Á + q 2 Á 2 T 1 1 Á + q ≠ 1 2 Á 2 T AE 1 Á +1 1 Á =1+Á, since the function ( 1 Á + q)/( 1 Á + q ≠ 1
) is strictly decreasing in [1, +OE). Therefore, for every q oe{ 1,...,|J |} it holds that

q joeKflJq p j AE (1 + Á) q joeKflJq p Ïq(j) =( 1+ Á)
q joeHflJq p j , and we conclude that

ÿ joeK p j = |J | ÿ q=1 ÿ joeKflJq p j AE (1 + Á) |J | ÿ q=1 ÿ joeHflJq p j =(1+Á) ÿ joeH p j .
Given Á>0, consider assign(B, T) obtained from the partitioning above and B chosen according to Lemma 24. Then, using a binary search like procedure we look for the smallest T such that the level • (C) relaxation of the Lasserre/SoS hierarchy is feasible for the long jobs. Invoking Theorem 6 we then obtain a schedule for the long jobs. The short jobs are scheduled then using the classic list scheduling algorithm [START_REF] Williamson | The design of approximation algorithms[END_REF].

Algorithm 1

Input: A scheduling instance and T Ø 1/m q joeJ p j . Output: A schedule with makespan at most (1 + Á)T if there exists a schedule for J long with makespan at most T ; infeasible otherwise.

1: For all (i, j) oe M ◊ J, initialize x ij Ω 0. 2: Consider the (Á/2)-partitioning of J long and B =1+4 2≠Á Á 2 |J long |. 3: if Las • (C) (assign(J long ,B,T)) " = ÿ then 4:
construct the Lex-schedule x lex of J long ; for all (i, j) oe M ◊ J long , x ij Ω x lex ij .

5:

while J short " = ÿ do 6:

Pick k oe J short , and let i oe M such that i oe argmin{¸oe M :

q joeJ p j x ¸j }, 7:
update x ik Ω 1 and J short Ω J short \{k}.

8:

Return x. 9: else return infeasible. Theorem 7. If Las • (C) (assign(J long ,B,T)) " = ÿ, then Algorithm 2 returns a schedule with makespan at most (1 + Á)T .

Proof. Thanks to Theorem 6, if Las • (C) (assign(J long ,B,T)) " = ÿ, then x lex is an integral schedule for J long with makespan at most T . In this case, jobs in J short are assigned according to the list scheduling algorithm, for which we include the analysis only for completeness. Let k oe J short and let i oe M such that x ik = 1. Since T> 1/m q joeJ\{k} p j , it follows that T> q joeJ p j x ij since this value is minimized at i oe M . Therefore, the load of machine i after scheduling job k is upper bounded by

p k + ÿ joeJ:x ij =1 p j < Á 2 T + 3 1+ Á 2 4 T =(1+Á)T.
The approximation scheme works as follows. We perform a binary search procedure to find the smallest integer value of T such that Las • (C) (assign(B, T)) " = ÿ. To do this it is enough to consider the lower bound 1/m q joeJ p j on the optimal makespan, and the upper bound Á1/m q joeJ p j Ë + max joeJ p j . For such value of T , thanks to Theorem 7 we obtain a schedule with makespan at most (1 + Á)T . In particular, Las • (C) (assign(J long ,B,C max )) " = ÿ and therefore the makespan of this schedule is at most

(1 + Á)T AE (1 + Á)C max .
Regarding the running time, observe that the smallest job size in J long is (Á/2)T , so we have ⁄ AE 2/Á. The size of C can also be upper bounded by (1 + 2/Á) 4/Á 2 , since not more than 2/Á jobs can be allocated to single machine and the size of the partition is less than 4/Á 2 . Since the running time of the algorithm is dominated by finding a feasible solution at level

• (C) < 2 Á (1 + 2 Á ) 4Á ≠2
of the Lasserre/SoS relaxation, the algorithm runs in polynomial time.

Proof of Theorem 6

Preliminaries. Before proceeding with the proof we need to introduce some properties that are satisfied by the relaxations obtained from the Lasserre/SoS hierarchy. Similarly to the SA and LS + hierarchies, we also have convergence in this case to the integer hull. In the following, we show a structural lemma that shows this property as a corollary, but more crucially, a property that in general is not satisfied by weaker hierarchies, known as the Decomposition Theorem [START_REF] Karlin | Integrality gaps of linear and semidefinite programming relaxations for knapsack[END_REF]. We make an exposition that is self-contained and we include the proof of these results in the context of the assignment polytope. The following properties are very simple and they will be useful throughout the section. Proposition 26. Let x oe Las r (assign(B, T)). Then, the following holds:

i) For every I oeP r+1 (M ◊ J), x I oe [0, 1]. ii) If L oeP r+1 (M ◊ J) and I ™ L, then x L AE x I .
Proof. To check i) it is enough to consider the principal submatrix of M r+1 (x) given by the entries ÿ and I. Since it is positive semidefinite as well, the determinant is non-negative, that is x I (1 ≠ x I ) Ø 0 and then x I oe [0, 1]. To check ii) it is enough to consider the principal submatrix of M r+1 (x) given by the entries I and L. This is positive semidefinite, and so its determinant is non-negative. Since

x IfiL = x L it holds that x L (x I ≠ x L ) Ø 0, thus x L AE x I .
Given x oe Las r (assign(B, T)), the extension of x,ext(x), is the vector with entries in P(M ◊ J) such that ext(x) I = 0 if |I| > 2r + 2 and ext(x) I = x I otherwise. Given a machine i oe M and a subset of jobs K ™ J, let x(i, K) be a vector with entries in P 2(r≠|K|)+2 (M ◊ J) such that Observe that if H " = ÿ, then the last term of the summation is equal to zero. Therefore, the summation above is equal to ext(x) Ifi({i}◊ÿ) = x I .

x(i, K) I =
An important observation is that the equality above says that x ÿ = q K™J x(i, K) ÿ and x ÿ = 1, therefore

x = ÿ K™J x(i, K)= ÿ K™J:x(i,K) ÿ >0 x(i, K) ÿ • A x(i, K) x(i, K) ÿ B , so x is a convex combination of the vectors {x C (i, K):K ™ J and x(i, K) ÿ > 0} where x C (i, K)=x(i, K)/x(i, K) ÿ .
An important observation is that the vector x C (i, K) is integral for machine i:I fj oe K, it follows that

x(i, K) ij = ÿ H™J:K™H (≠1) |H\K| ext(x) {(i,j)}fi({i}◊H) = ÿ H™J:K™H (≠1) |H\K| ext(x) ÿfi({i}◊H) = x(i, K) ÿ ,

Proof of Theorem 6

Chapter 5 and therefore x C (i, K) ij = 1. Now, given j/ oe K, we split the summation between those sets that contain K fi{j} and those that do not. Therefore,

x(i, K) ij = ÿ H™J:K™H (≠1) |H\K| ext(x) {(i,j)}fi({i}◊H) = ÿ H™J\{j}:K™H ((≠1) |H\K| +(≠1) |H\K|+1 )ext(x) {i}◊(Hfi{j}) =0.
In the following we state the Decomposition Theorem [START_REF] Karlin | Integrality gaps of linear and semidefinite programming relaxations for knapsack[END_REF] adapted to our purposes, which is a structural property of the Lasserre/SoS hierarchy that makes it stronger than others. We include its proof for the sake of completeness, although it follows the same lines than [START_REF] Karlin | Integrality gaps of linear and semidefinite programming relaxations for knapsack[END_REF] and it could be skipped. Theorem 8. Let x oe Las r (assign(B, T)) for some r Ø ⁄. Then, for every machine i oe M and K ™ J such that x(i, K) ÿ > 0, we have x C (i, K) oe Las r≠⁄ (assign(B, T)). Furthermore, x C (i, K) ij =1for every j oe K and zero otherwise.

Proof of Theorem 8. It remains to show that x C (i, K) oe Las r≠⁄ (assign(B, T)). In fact, we show a stronger result: For every i oe M and K ™ J, if x(i, K) ÿ > 0 then x C (i, K) oe Las r≠|K| (assign(B, T)). In particular, the constraints (5.2) at level r =0 imply that K induces a configuration, C i (x C (i, K)) oeC, and therefore |K|AE⁄.

The constraint (5.5) is clearly satisfied. We now check that constraint (5.4) is satisfied, that is, M r≠|K|+1 (x C (i, K)) ≤ 0. Since M r+1 (x) ≤ 0, there exist a family of vectors {-I : I oeP r+1 (M ◊ J)} such that for every U, V oeP r+1 (M ◊ J), x U fiV = È-U ,-V Í. Consider the vector -C (i, K) with entries in P r≠|K|+1 (M ◊ J) such that

-C (i, K) I = 1 Ò x(i, K) ÿ ÿ H™J:K™H (≠1) |H\K| -Ifi({i}◊H) .
We show that for every U, V oeP r≠|K|+1 , x C (i, K) U fiV = È-C (i, K) U ,-C (i, K) V Í and that implies constraint (5.4) is satisfied.

x(i, K) ÿ •È-C (i, K) U ,-C (i, K) V Í = ÿ H™J:K™H ÿ G™J:K™G (≠1) |H\K|+|G\K| È-U fi({i}◊H) ,-V fi({i}◊G) Í = ÿ H™J:K™H (≠1) |H\K| ÿ G™J:K™G (≠1) |G\K| x U fiV fi({i}◊H)fi({i}◊G) .
Observe that |U |AEr ≠|K| + 1 and |V |AEr ≠|K| + 1, and therefore every term in the summation above is well defined. Consider H " = K and and element h oe H \ K.

Then, the second summation is equal to

ÿ G™J:Kfi{h}™G ((≠1) |G\K| +(≠1) |G\K|+1 )x U fiV fi({i}◊H)fiG =0,
and therefore in the summation above it only remains the term for H = K, that is,

ÿ G:K™G (≠1) |G\K| x U fiV fi({i}◊K)fi({i}◊G) = ÿ G:K™G (≠1) |G\K| x U fiV fi({i}◊G) = x(i, K) U fiV ,
since GfiK = G. To check the constraints (5.1), we have that given I oeP 2r+1 (M ◊J),

ÿ ¸oeM x(i, K) Ifi{(¸,j)} = ÿ ¸oeM ÿ H™J:K™H (≠1) |H\K| ext(x) Ifi{(¸,j)}fi({i}◊H) = ÿ H™J:K™H (≠1) |H\K| ÿ ¸oeM ext(x) Ifi{(¸,j)}fi({i}◊H) = ÿ H™J:K™H (≠1) |H\K| ext(x) Ifi({i}◊H) = x(i, K) I ,
since ext(x) satisfies the constraint (5.5)f o rI as well. Finally, it remains to check constraints (5.2) and (5.3). Let fl be any vector in {pack i , break i : i oe M \{m}} fi {pack m }. Since M r (flıx) ≤ 0, there exists a family of vectors {-I : I oeP r (M ◊ J)} such that for every U, V oeP r (M ◊ J), (flıx) U fiV = È-U ,-V Í.L e t-C (i, K) be the vector with entries in P r≠|K| (M ◊ J) such that

-C (i, K) I = 1 Ò x(i, K) ÿ ÿ H™J:K™H (≠1) |H\K| -Ifi({i}◊H) .
We show next that for every U, V oeP r≠|K| ,(flıx

C (i, K)) U fiV = È-C (i, K) U ,-C (i, K) V Í
and that implies constraint (5.4) is satisfied. First, observe that

x(i, K) ÿ •È-C (i, K) U ,-C (i, K) V Í = ÿ H:K™H (≠1) |H\K| ÿ G:K™G (≠1) |G\K| (flıx) U fiV fi({i}◊H)fi({i}◊G) .
We have that |U |AEr ≠| K| and |V |AEr ≠| K|, and therefore every term in the summation above is well defined. As we showed before, in the summation above it only remains the term for H = K. Therefore,

ÿ G:K™G (≠1) |G\K| (flıx) U fiV fi({i}◊(KfiG)) = ÿ G:K™G (≠1) |G\K| (flıx) U fiV fi({i}◊G) =(flıx(i, K)) U fiV ,
and we conclude using that flıx(i,

K)=x(i, K) ÿ • (flıx C (i, K)).
Other relevant property is that if the vector x was integral at some machine, then it remains integral for a vector in the convex combination of the decomposition. Proposition 28. Suppose that x oe Las r (assign(B, T)) with r Ø ⁄, and it is integral at machine h. Let K ™ J with x C (i, K) ÿ > 0. Then, x C (i, K) hj = x hj oe{0, 1} for all j oe J.

Proof. Let j oe J such that x hj = 0. Observe every term in the summation defining x C (i, K) hj contains {(h, j)}, and then by Proposition 26 they are all zero. It follows that x C (i, K) hj = 0. On the other hand, if x hj = 1, since q ¸oeM x ¸j = 1 it follows that x ¸j =forev ery¸" = h. By using the argument above and since x C (i, K) oe assign(B, T) by Theorem 8, it follows that x C (i, K) ¸j =0forev ery¸" = h and therefore x C (i,

K) hj = 1 ≠ q ¸oeM x C (i, K) ¸j =1.
Constructing the schedule. The proof of Theorem 6 follows in a constructive way. We iteratively call the Decomposition Theorem 8 and obtain, in that way, many machines that are integral. If we start from a high enough level of the hierarchy, we get at the end a solution that is feasible for assign(B, T), and therefore, the configurations of the integral machines have to obey the lexicographic order. We then show how to extend the schedule to the rest of the machines using those configurations and prove this schedule to be feasible.

The algorithm consist of two phases. In Phase 1, we use the solution obtained from high enough level of the hierarchy to find the last machine which is fractionally scheduled according to configuration C 1 using the Decomposition Theorem, and pick such a vector obtained from the convex combination. We then proceed by finding the last machine scheduled fractionally according to C 2 , and so on. We end up with a solution that is integral for all these machines, and it respects the lexicographic order over the configurations. In Phase 2, we construct the schedule for the rest of the machines and jobs that have not been assigned yet. We call the schedule obtained in this way the lexicographic schedule, x lex . Below we provide the pseudocode of the construction, and then we prove it outputs a feasible schedule.

Algorithm 2

Input: A solution x oe Las • (C) (assign(B, T)). Output: A schedule x lex with makespan at most T .

1: For all (i, j) oe M ◊ J, initialize x lex ij Ω 0, ¸Ω 0 and y 0 Ω x.

2:

Û Phase 1: Inducing integrality of certain machines. Let M ¸= {i oe M : exists K ™ J with y ¸(i, K) ÿ > 0 and conf(K)=C ¸}.

5:

if M ¸" = ÿ then 6:

let i ¸= max M ¸and K ¸™ J such that conf(K ¸)=C ¸and y ¸(i ¸,K ¸)ÿ > 0, 7:
for every j oe K ¸let x lex i ¸j Ω 1, 8:

y ¸+1 Ω y Ç (i ¸,K ¸).

9:

else i ¸= OE 10: Reset ¸Ω 1, i 0 =0.

11:

Û Phase 2: Extending the above solution greedily. 12: for ¸=1to|C| do 13: if i ¸< OE then 14: for max{i q :0AE q<,i q < OE} <i<i ¸do 15:

let K i ™ J \{j oe J : exists i oe M with x lex ij =1} where conf(K i )=C ¸;
16:

for every j oe K i , let x lex ij Ω 1. 17: Return x lex . Lemma 29. Let x oe Las r (assign(B, T)) for r Ø ⁄, and i, h oe M with i<h. Suppose that x is integral for machine h. Then, for every I such that x(i, I) ÿ > 0, we have conf(I) Ø lex C h (x).

Proof. Let I ™ J with x C (i, I) ÿ > 0. By Theorem 8 we have that x C (i, I) oe

Chapter 6 Introduction

In the classical secretary problem (see, e.g., [START_REF] Ferguson | Who Solved the Secretary Problem?[END_REF] for a survey) an employer wants to select exactly one out of n secretaries arriving in random order. After each arrival, the employer learns the relative merits of the new candidate (i.e., he can compare the candidate with previous ones but no numerical quantity is revealed), and must reject or accept immediately. Lindley [START_REF] Lindley | Dynamic Programming and Decision Theory[END_REF] and Dynkin [START_REF] Dynkin | The optimum choice of the instant for stopping a Markov process[END_REF] show that the strategy of sampling 1/e ¥ 0.37 fraction of the candidates and then selecting the first record has a probability of at least 1/e ¥ 0.37 of selecting the best candidate and that no algorithm can beat this constant. During the last decade, generalizations of this problem have attracted the attention of researchers, specially due to applications in online auctions and online mechanism design.

Arguably one the most natural extension is the generalized secretary problem by Babaioff et al. [START_REF] Babaioff | Matroids, secretary problems, and online mechanisms[END_REF]. In their setting, a set R of candidates of known size is presented to an algorithm on uniform random order. On arrival, each element r reveals its hidden weight w(r) and the algorithm must irrevocably decide whether to select it or not while preserving the independence of the set of selected elements on a given independence system1 (R, I). The objective is to maximize the total weight of the selected independent set. Mainly motivated by applications and by the richness of their structural properties, Babaioff et al. focuses on the case in which (R, I) is a matroid, 2 , where this problem takes the name of Matroid Secretary Problem (MSP). In the following, anutility-competitive algorithm is one that returns an independent set whose expected weight is at least 1/-times the weight of an optimum independent set.

Babaioff et al. posts the well-known, and still open, Matroid Secretary Conjecture which in its weak form states that there must be a constant competitive algorithm for the MSP on any matroid, and on its strong form, claims that the constant is e. They also provide a Threshold Price Algorithm (TPA) achieving an O(log fl) utilitycompetitive ratio on matroids of rank fl. Better algorithms have improved this ratio to O( Ô log fl) by Chakraborty and Lachish [START_REF] Chakraborty | Improved Competitive Ratio for the Matroid Secretary Problem[END_REF] and later to the current best ratio of O(log log fl) by Lachish [START_REF] Lachish | (log log Rank) Competitive Ratio for the Matroid Secretary Problem[END_REF] and independently by Feldman et al. [START_REF] Feldman | A Simple O (log log(rank)) -Competitive Algorithm for the Matroid Secretary Problem[END_REF].

The generalized secretary problem has also been studied on non-matroidal systems such as knapsack [START_REF] Babaioff | A knapsack secretary problem with applications[END_REF], online matchings on graphs and hypergraphs [START_REF] Dimitrov | Competitive Weighted Matching in Transversal Matroids[END_REF][START_REF] Kesselheim | An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions[END_REF][START_REF] Korula | Algorithms for Secretary Problems on Graphs and Hypergraphs[END_REF] and LP packings [START_REF] Kesselheim | Primal beats dual on online packing LPs in the random-order model[END_REF]. Babaioff et al. [START_REF] Babaioff | Matroids, secretary problems, and online mechanisms[END_REF] show that for general independence systems every algorithm on n elements must be Ω(log n/ log log n) utility-competitive and Rubinstein [START_REF] Rubinstein | Beyond matroids: secretary problem and prophet inequality with general constraints[END_REF] provides an O(log n log fl) competitive algorithm. Many works consider alternative objective functions, such as minimum sum of ranks [1], time discounted variants [9], convex costs under knapsack type restrictions [START_REF] Barman | Secretary problems with convex costs[END_REF] and submodular objectives [START_REF] Bateni | Submodular secretary problem and extensions[END_REF][START_REF] Feldman | Improved competitive ratios for submodular secretary problems (extended abstract)[END_REF][START_REF] Feldman | The submodular secretary problem goes linear[END_REF]. Another rich line of research focuses on relaxing the random order condition and the power of the adversary setting the weights. There are O(1) competitive algorithms for the MSP on the random order and assignment model [START_REF] Soto | Matroid Secretary Problem in the Random-Assignment Model[END_REF], on the adversarial order random assignment model [START_REF] Oveis Gharan | On Variants of the Matroid Secretary Problem[END_REF][START_REF] Soto | Matroid Secretary Problem in the Random-Assignment Model[END_REF] and on the free order model [START_REF] Jaillet | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case[END_REF]. Non-uniform arrival orders have also been considered [START_REF] Kesselheim | Secretary Problems with Non-Uniform Arrival Order[END_REF]. Related to this line of research is the design of order-oblivious algorithms, which can sample a constant fraction of the elements but afterwards, the arrival order may be arbitrary; and results related to prophet inequality settings on which the weight of each element is a random variable with known distribution but the arrival order is adversarial, see [8,[START_REF] Dütting | Polymatroid prophet inequalities[END_REF][START_REF] Kleinberg | Matroid prophet inequalities[END_REF][START_REF] Rubinstein | Combinatorial prophet inequalities[END_REF].

Ordinal MSP versus Utility MSP

A common requirement for the mentioned algorithms for the MSP on general matroids is that they require to use numerical weights: they all treat elements with similar weights more or less equivalently. In contrast, in the definition of the classical secretary problem, the decisions made by an algorithm only rely on the ordinal preferences between candidates. This is a very natural condition as for many applications it is difficult to determine (for instance, via an interview) a numerical weight representing each candidate, but it is often simple to compare any two of them. For this reason we restrict our study to the ordinal MSP in which the decision maker can only compare seen elements. This is, it can check which element is higher in an underlying hidden total order º. In particular, the algorithm cannot really compute the weight of a set.

However, matroids have the following extremely nice feature: it is possible to find a maximum weight independent set using only ordinal information by greedily constructing an independent set using the order º. The set OPT found this way is the unique lexicographically 3 maximum independent of the matroid. So it is quite natural to ask what can be done without numerical weights in the secretary setting. In order to measure the performance of an algorithm we introduce three notions of competitiveness for the ordinal MSP. We say that an algorithm isordinal-competitive if for every nonnegative weight function compatible with the total order, the expected weight of the output independent set ALG is at least 1/-the weight of OPT. It isintersection-competitive if the expected fraction of elements in OPT that is in-cluded into ALG is at least 1/-, and it isprobability-competitive if for every element r oe OPT, the probability that r is included into ALG is at least 1/-. It is not hard to see that anyordinal-competitive algorithm is alsocompetitive in the classical (utility) sense and also that anyprobability-competitive algorithm is alsocompetitive in every other setting. All the mentioned algorithms [START_REF] Babaioff | Matroids, secretary problems, and online mechanisms[END_REF][START_REF] Chakraborty | Improved Competitive Ratio for the Matroid Secretary Problem[END_REF][START_REF] Feldman | A Simple O (log log(rank)) -Competitive Algorithm for the Matroid Secretary Problem[END_REF][START_REF] Lachish | (log log Rank) Competitive Ratio for the Matroid Secretary Problem[END_REF]f o r the standard or utility MSP do not work in the ordinal model, and so the existence of an --utility competitive algorithm does not imply the existence of anprobability/intersection/ordinal competitive algorithm. To the authors' knowledge the only known algorithms for ordinal MSP on general matroids (apart from the trivial O(fl) probability-competitive that selects the top independent singleton using a classical secretary algorithm) are Bateni et al.'s O(log 2 fl) ordinal-competitive algorithm [START_REF] Bateni | Submodular secretary problem and extensions[END_REF] (which also works for submodular objective functions) and Soto's variant of TPA [START_REF] Soto | Matroid Secretary Problem in the Random-Assignment Model[END_REF] which is O(log fl) ordinal-competitive.

Hoefer and Kodric [START_REF] Hoefer | Combinatorial Secretary Problems with Ordinal Information[END_REF] study the ordinal secretary problem obtaining constant ordinal-competitive algorithms for bipartite matching, general packing LP and independent sets with bounded local independence number. They also show that Feldman and Zenklusen's reduction [START_REF] Feldman | The submodular secretary problem goes linear[END_REF] from submodular to linear MSP works in the ordinal model.

MSP on specific matroids. An extensive amount of work has been done on the last decade on the MSP on specific matroid classes including unitary [START_REF] Beckmann | Dynamic programming and the secretary problem[END_REF][START_REF] Bruss | Sum the odds to one and stop[END_REF][START_REF] Dynkin | The optimum choice of the instant for stopping a Markov process[END_REF][START_REF] Gilbert | Recognizing the Maximum of a Sequence[END_REF][START_REF] Lindley | Dynamic Programming and Decision Theory[END_REF], uniform [START_REF] Babaioff | A knapsack secretary problem with applications[END_REF][START_REF] Kleinberg | A Multiple-Choice Secretary Algorithm with Applications to Online Auctions[END_REF], transversal [START_REF] Babaioff | Matroids, secretary problems, and online mechanisms[END_REF][START_REF] Dimitrov | Competitive Weighted Matching in Transversal Matroids[END_REF][START_REF] Korula | Algorithms for Secretary Problems on Graphs and Hypergraphs[END_REF], graphic [9,[START_REF] Babaioff | Matroids, secretary problems, and online mechanisms[END_REF][START_REF] Korula | Algorithms for Secretary Problems on Graphs and Hypergraphs[END_REF], cographic [START_REF] Soto | Matroid Secretary Problem in the Random-Assignment Model[END_REF], regular and MFMC [START_REF] Dinitz | Matroid Secretary for Regular and Decomposable Matroids[END_REF], k-column sparse [START_REF] Soto | Matroid Secretary Problem in the Random-Assignment Model[END_REF] and laminar matroids [START_REF] Im | Secretary Problems: Laminar Matroid and Interval Scheduling[END_REF][START_REF] Jaillet | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case[END_REF][START_REF] Ma | The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems[END_REF]. Even though the algorithms are stated for the utility MSP, many of the proofs work directly on either the ordinal MSP under ordinal or even probability competitiveness. We include in Table 6.1 a summary of all known results together with the improved bounds obtained in this paper.

Our results and techniques

We first formalize our new competitiveness notions for ordinal MSP and study their interrelations. We say that a performance notion is stronger than another if any algorithm that iscompetitive for the former is alsocompetitive for the latter. Under this definition, we show that probability is stronger than ordinal and intersection, and that ordinal is stronger than utility.

We first focus on developing a powerful technique to define strong algorithms for the MSP on many classes of matroids. Informally (see the exact definition in Chapter 7), we say that an algorithm has forbidden set of size k if it samples without selecting s ≥ Bin(n, p) elements and the following condition holds. Suppose that an element r ú of OPT arrives in a position t>sand let R t be the set of elements that arrived on or before time t. For each time step i between s + 1 and t ≠ 1 there is a random set F i of at most k forbidden elements such that if for every i, the element arriving at time i is not forbidden (i " oe F i ) then r ú is sure to be selected. The following is the key lemma that shows why algorithms with small forbidden sets are useful for the MSP.

Lemma 31 (Key Lemma). By setting the right sampling probability p = p(k), every algorithm with forbidden sets of size k is -(k) probability-competitive, where

(p(k),-(k)) = Y ] [ (1/e, e) if k =1, (k ≠ 1 k≠1 ,k k k≠1 ) if k Ø 2.
Obtaining algorithms with small forbidden sets is simple for many matroid classes. In fact, it is easy to see that the variant of the standard classical secretary algorithm which samples s ≥ Bin(n, p) elements and then selects the first element better than the best sampled element, has forbidden sets of size 1. Suppose that the maximum element r ú arrives at time t>sand denote by x the second best element among those that have arrived up to time t.I fx does not arrive at any time between s + 1 and t ≠ 1 then for sure, x will be used as threshold and thus r ú will be selected. In the above notation, all forbidden sets F i are equal to the singleton {x}. Using the key lemma, by setting p =1/e, this algorithm is e competitive.

We provide new algorithms that beat the state of the art guarantees for transversal, graphic, k-sparse and laminar matroids. We also provide new algorithms for other classes of matroids such as matching matroids, certain matroidal graph packings (which generalize matching matroids), hypergraphic matroids, k-framed matroids (which generalize k-sparse matroids), semiplanar gammoids and low exchangeability gammoids. As an interesting side result, we revisit Kleinberg's 1 + O(fl ≠1/2 ) ordinalcompetitive algorithm. We show that its probability-competitiveness is bounded away from 1 and propose an algorithm that achieves a probability-competitive ratio of 1+O( Ò log fl/fl). Our new results for specific classes of matroids are summarized in Table 6.1, which, for completeness includes all matroid classes ever studied on the MSP, even those for which we couldn't improve the state of the art. In the references within the table u, o and p stand for utility, ordinal and probability competitiveness respectively.

Kesselheim et al.'s algorithm for online bipartite matching [START_REF] Kesselheim | An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions[END_REF] uses a technique very similar to that in the previous lemma to compute the expected weight contribution of the k-th arriving vertex, which is enough to prove asymptotically e + O(1/n) utility-competitiveness for online bipartite matchings. In fact, for transversal matroids, this yields to an e + O(1/n) ordinal-competitive algorithm. But their analysis does not imply any guarantee on the probability notion. In the next section we show by using a different analysis, that their algorithm has forbidden sets of size 1 and so it is actually e probability-competitive (always, not just asymptotically).

We obtain as well results for the ordinal MSP on general matroids. For the weak intersection notion one can show that exists a ln(2/e) intersection-competitive algorithm for the MSP using a greedy variant. More interestingly, we show that in the ordinal notion we can match the factor attained for the weaker utility variant. For the stronger probability notion we do not attain the same competitiveness ratio.

Theorem 9. There exist an O(log log fl) ordinal-competitive algorithm and an O(log fl) probability competitive algorithm for the MSP.

Even though Theorem 17 is attained by a very simple algorithm, we note that standard ideas such as thresholding do not work for the intersection notion since elements outside OPT that are higher than actual elements from OPT do not contribute to the objective. The algorithms mentioned in Theorem 9 are based on the recent O(log log fl) utility-competitive algorithm by Feldman et al. [START_REF] Feldman | A Simple O (log log(rank)) -Competitive Algorithm for the Matroid Secretary Problem[END_REF]. Their algorithm samples a fraction of the elements so as to classify most of the non-sampled ones into h = O(log fl) weight classes consisting off elements whose weights are off by at most a factor of 2. They implement a clever random strategy to group consecutive weight classes together into buckets, each one containing roughly the same random number of weight classes. On each bucket they define a single random matroid with the property that if one picks an independent set from each one of these matroids, their union is independent in the original one. Their algorithm then selects a greedy independent set on each bucket matroid and outputs their union. Due to the random bucketing, the expected number of elements selected on each weight class is at least Ω(1/ log h) times the number of elements that OPT selects from the same class. This means that the global algorithm is actually O(log h)=O(log log fl) utility-competitive.

In the ordinal setting we cannot implement this idea in the same way, since basically we do not have any weights. However, we can still partition the elements of the matroid into ordered layers. The idea is to select a collection of thresholds obtained from the optimum of a sample, and use them as separators to induce the layers. This motivates the definition of the Layered-MSP (see Section 10.1). For both ordinal and probability competitiveness we provide a reduction from the Layered-MSP to the ordinal MSP. For the ordinal notion, we select as thresholds a geometrically decreasing (in value order) subset of the sample optimum, so we can partition the matroid into h = O(log fl) layers. For the probability notion we use all the elements of the sample optimum as thresholds. The crucial result in this part is that our reduction allows to go from any g(h) competitive algorithm for the Layered-MSP to a g(O(1 + log h)) ordinal-competitive algorithm, and to a g(O(h)) probability-competitive algorithm. In particular, by applying Feldman et al.'s algorithm, interpreting these layers as weight classes, we get an O(log log fl) ordinal-competitive algorithm and an O(log fl) probability-competitive algorithm for the original matroid.

Organization

In Section 6.4 we recall some definitions, fix some notation and formally describe the performance guarantees for the ordinal MSP, studying their relations. In Chapter 7 we prove our key lemma for algorithms with small forbidden sets. We then in Chapter 8 show how devise simple algorithms for all the matroid classes mentioned using the forbidden sets technique. The competitiveness ratios are summarized in Table 6.1.I n Chapter 9 we show an asymptotically 1 probability-competitive algorithm for uniform matroids. Finally, in Chapter 10 we describe our new algorithms for general matroids by proving Theorem 9 and we study the relations between the different competitiveness notions.

General framework

for probabilitycompetitiveness (Chapter 7)

Preliminaries

Recall that given a ground set R,amatroid (R, I) is an ordered pair where I™P(R) is non-empty and it satisfies the following two conditions: Every family satisfying condition (M1) is called an independence system. The condition (M2) is known as the augmentation axiom. A set in I that is a maximal independent set for the inclusion is called a base. To make notation lighter, we use + and ≠ for the union and difference of a set with a single element respectively. That is, Q + r ≠ e =(Q fi{r}) \{e}. By the augmentation axiom is clear that every base has the same cardinality and this number is called the rank of a matroid. There is an stronger statement than (M2) which is called the strong basis exchange: For every pair of bases X, Y oeIand for all x oe X \ Y , there exist y oe Y \ X such that X ≠ x + y oeI and Y ≠ y + x oeI. That is, there exists a way of swaping x with an element y that preserves the independence of both sets.

Example 1. Given a set R and k oe N, such that |R|Øk, consider I = {F ™ R : |R|AEk}, that is, every subset of cardinality at most k. This is called the k-uniform matroid of R and its bases are the subsets of R with cardinality exactly equal to k.

Example 2. Given a graph G =(V, E), consider I to be the set of all subsets of edges X ™ E such that (V, X) is a forest. The pair (E, I) is called the graphic matroid of G, and its bases are the maximal forests in G. In particular, when G is connected, the bases are the subsets of edges forming a spanning tree of G.

Example 3. Given a matrix A oe R L◊R , consider I to be the set of subsets X ™ R such that the columns indexed by X are linearly independent in R L . The pair (R, I) is called the linear matroid of A. In particular, every graphic matroid can be represented by considering the linear matroid obtained from the adjacency matrix of G. We will go back later in this part to this notion of matroid representation.

The matroids we consider are ordered, i. e., there is a. strict total order º over the ground set R = {r 1 ,...,r n } and we denote it by M =(R, I, º). We call º the value order and say that r 1 is the highest valued element, r 2 is the second one, and so on, then r 1 º r 2 º•••ºr n . The elements of I are ordered according to the lexicographic order induced by º.

There are many combinatorial problems that can be modeled as an ordered matroid, and the following is a classic example. Given a graph G, suppose we have a total order over the edges and we look for the lexicographically maximum spanning tree. This problem can be solved by running the greedy Kruskal's algorithm. Usually the problem is posed considering weights over the edges instead of an order. In that case, one looks for a spanning tree of maximum weight, which is not necessarily unique. We say that a nonnegative weight function w : E ae R + is compatible with the value order if the following holds: For every i, j oe [n], if r i º r j then w(r i ) Ø w(r j ).

••• r 1 º r 2 º r 3 º r 4 ••• r m≠1 º r m Figure 6.2:
The optimal lexicographic base (red elements) can be found by the greedy algorithm feeded with elements from highest to smallest in the order. An element is selected as long as it preserves the independence.

In terms of matroids, the problem above is to find the lexicographically optimum base of the graphic matroid of G, and naturally, the same question can be formulated for a general matroid. The greedy algorithm solves this problem: From the highest to smallest element, select an element and add it to the current solution if this union is an independent set. By matroid properties, for every subset Q ™ R, there is a unique lexicographically optimum base OPT(Q) obtained by applying the greedy algorithm in the order º, over the set Q. Note that for every compatible weight function the set OPT = OPT(E) is a maximum weight independent set. We reserve the use of superscripts k oe N on a set Q to denote the subset of the highest min{k, |Q|} valued elements of Q. In particular R k and OPT k denote the set of the top k elements of the matroid and of OPT respectively. We also reserve n and fl to denote the number of elements of R and its rank respectively.

The definition of rank extends for subsets of R, that is, the rank of Q ™ R is the cardinality of its bases, fl(Q) = max{|I| : I oeI ,I™ Q}, and the span of Q is span(Q)={r oe R : fl(Q + r)=fl(Q)}. In matroids, OPT has the property of improving any subset in the following sense.

Lemma 32. Let Q ™ R. Then, OPT fl Q ™ OPT(Q).
Proof of Lemma 32. Let r = r k be an element of OPT fl Q. Since r k is selected by the Greedy algorithm we have that r " oe span(R k≠1 ). But then r " oe span(R k≠1 fl Q) and so it is also selected by the Greedy algorithm applied only on the set Q. Therefore, r oe OPT(Q).

In the (utility/ordinal) MSP, the elements of a (nonnegatively weighted/ordered matroid) are presented in uniform random order to an online algorithm that does not know a priori the (weights/value order) of unrevealed elements. At any moment, the algorithm can (view the weight of/compare in the total order) any pair of revealed element. When a new element r is presented, the algorithm must decide whether to add r to the solution and this decision is permanent. The algorithm must guarantee

In the second measure we consider, we want to make sure that every element of the optimum is part of the output with large probability. We say that an algorithm is -Ø 1 probability-competitive if for every e oe OPT, Pr(e oe ALG) Ø 1/-. (6.3) Finally, in the third measure we want to maximize the number of elements in the optimum that the algorithm outputs. We say an algorithm is

-Ø 1 intersection- competitive if E[|OPT fl ALG|] Ø|OPT|/-. (6.4)
Relation between variants. The ordinal and probability measures are in fact stronger than the standard utility notion. That is, anyordinal/probability-competitive algorithm yields to anutility-competitive algorithm. Furthermore, the probability is the strongest of them all.

Lemma 34. If an algorithm isordinal-competitive then it isutility-competitive.

If an algorithm isprobability-competitive then it is alsoordinal, utility and intersection-competitive.

Proof of Lemma 34. If an algorithm isordinal-competitive then by definition it is utility-competitive. Now consider anprobability-competitive algorithm returning a set ALG. For any k oe

[n], we have E[|ALG fl R k |] Ø E[|ALG fl OPT fl R k |]= q roeOPTflR k Pr(r oe ALG) Ø |OPTflR k | -
. which means that the algorithm isordinalcompetitive, and therefore, it is alsoutility-competitive. To see that the algorithm is alsointersection-competitive we note that We provide in Chapter 10 a comparison between the different competitiveness measures. An algorithm for the utility variant, which recall is able to use the elements' weights, may not be adapted to the ordinal MSP, since in this model it can not use any weight information. In other words, the existence of anutility-competitive for a matroid (or matroid class) does not imply the existence of an --competitive algorithm for any of the other three measures. It is worth noting that the intersection-competitive Chapter 7

Protect to be competitive

In this chapter we introduce and describe a technique we call forbidden sets, that allows us to analyze algorithms for the ordinal MSP. Thanks to this technique we devise algorithms for many matroid classes previously studied in the context of MSP and to other matroids that have not been studied in this context. Furthermore, our results improve upon the best known competitive ratios for almost all studied matroid classes, and we study them in details in Chapter 8. Recall that |R| = n, and for t oe [n], r t is the random element arriving at time t, and R t is the random set of elements arriving at or before time t. and X ™ Y ≠ r ú , one can define a set F(X, Y, r ú ) ™ X of at most k forbidden elements of X such that the following condition holds. Let t Ø s + 1 be a fixed time. If r t oe OPT(R t ) and for every j oe{ s +1,...,t≠ 1}, r j " oe F(R j ,R t ,r t ) then r t is selected by the algorithm.

To better understand the k-forbidden property suppose that a fixed element r ú oe OPT arrives at step t Ø s + 1, that is r t = r ú . Note that the set R t≠1 of elements arriving before r t is a random subset of size t ≠ 1o fR ≠ r t , and no matter the choice of R t≠1 , r ú is always part of OPT(R t )=O P T ( R t≠1 + r t ). Inductively, for j = t ≠ 1 down to j = 1, once R j is specified, r j is a uniform random element of R j , and R j≠1 is defined as R j ≠ r j . Moreover, this choice is independent of the previous random experiments (i.e., the choices of {r j+1 ,...,r t≠1 ,R t≠1 }). The k-forbidden property (3.) says that if for every j oe{ s +1,...,t ≠ 1} element r j is not a forbidden element in F(R j ,R t ,r t ) then r ú is guaranteed to be selected by the algorithm. Designing algorithms with small forbidden sets is the key to achieve constant competitiveness as our key Lemma (that we restate below) shows.

Lemma 36 (Key Lemma). By setting the right sampling probability p = p(k), every algorithm with forbidden sets of size k is -(k) probability-competitive, where

(p(k),-(k)) = Y ] [ (1/e, e) if k =1, (k ≠ 1 k≠1 ,k k k≠1 ) if k Ø 2.
Proof. Fix an element r ú from OPT and condition on the realization of s ≥ Bin(n, p), on the time t on which r ú = r t arrives and on the set

Y = R t -
oe R j \F(R j ,Y,r ú )) = t≠1 Ÿ j=s+1 Pr(r j oe R j \F(R j ,Y,r ú )) Ø t≠1 Ÿ j=s+1 A j ≠ k j B + ,
where x + = max{0,x}. The equality above holds because of the independence of the random experiments defining iteratively r t≠1 , r t≠2 , down to r s+1 as mentioned before the statement of this lemma. By removing the initial conditioning we get

Pr(r ú oe ALG) Ø E s≥Bin(n,p) 1 n n ÿ t=s+1 t≠1 Ÿ j=s+1 A 1 ≠ k j B + . (7.1)
To compute the right hand side we use the following auxiliary process. Suppose that n people participate in a game. Each player x arrives at a time • (x) chosen uniformly at random from the interval [0, 1]. Each person arriving after time p selects a subset of k partners from the set of people arriving before them, without knowing their actual arrival times (if less than k people have arrived before her, then all of them are chosen as partners). A player wins if she arrives after time p and every one of her partners arrived before time p. Since the arrival times are equally distributed and the event that two people arrive at the same time has zero probability the arrival order is uniform among all possible permutations. Furthermore, the number of people arriving before time p distributes as Bin(n, p). Using these facts, the probability that a given person x wins is exactly the right hand side of (7.1). But we can also compute this probability using its arrival time • (x)a s

⁄ 1 p Pr( all partners of x arrived before time p | • (x)=• ) d• Ø ⁄ 1 p (p/• ) k d•,
which holds since the arrival time of each partner of x is a uniform random variable in [0,•], and conditioned on • , each partner arrives before time p with probability p/• . Since x may have less than k partners, we don't necessarily have equality. We conclude that for every r ú oe OPT,

Pr(r ú oe ALG) Ø ⁄ 1 p (p/• ) k d• = Y _ ] _ [ ≠p ln(p), if k =1, p ≠ p k k ≠ 1 , if k Ø 2.
Chapter 7

By optimizing the value of p as a function of k, we obtain that the probability of r ú oe ALG is 1/-(k), with -(k) as in the statement of the lemma and the probability achieving it is p = p(k).

The idea of analyzing an algorithm as a series of stochastically independent experiments which defines the reverse arrival sequence appears very early in the history of the secretary problem. One can prove that the algorithm for the classical secretary problem, that samples s ≥ Bin(n, p( 1)) elements and then selects the first element better than all the sampled ones, is e probability-competitive. In fact, it has forbidden sets of size 1. In our notation, for each (X, Y, r ú ) with r ú the maximum element of Y and X ™ Y ≠ r ú , define the forbidden set F(X, Y, r ú ) as the singleton OPT(X). The 1-forbidden condition states that if the element r t arriving at time t is a record, that is, r t oe OPT(R t ), and if for every time j oe{s +1,...,t≠ 1}, r j " oe OPT(R j ) (i.e., the j-th arriving element is not a record), then r t will be chosen by the algorithm. Since all forbidden sets have size at most 1, setting the sampling probability to be p(1) = 1/e guarantees the probability-competitive ratio of -( 1 Independence witness. It turns out that for many matroid classes there is a combinatorial object that acts as certificate for testing independence. That is, a set X is independent on a given matroid if and only if each element r oe X can be mapped to an object (e.g., an edge covering r, a path ending in r, a subgraph covering r, etc.) r such that the set X = {r : r oe X} satisfies a combinatorial property (e.g., a matching covering X, a collection of edge/node disjoint paths connecting X with some source, a collection of disjoint subgraphs covering X). We call X a witness for the independence of X.As e tX may have multiple witnesses, but we will always assume that there is a canonical witness, witness(X), that can be computed by the algorithm and furthermore, the choice of the witness cannot depend on the set of elements seen so far nor on its arrival order. The fact that the witnesses do not depend on the arrival order makes them amenable to the analysis by the reverse arrival sequence analysis above, which in turn, will help us to devise algorithms with constant-size forbidden sets.

Chapter 8

Matroids with small forbidden sets

In this chapter we show how to apply the forbidden sets technique to devise algorithms for different matroid families. The goal is to find algorithms having small forbidden sets. In particular, if an algorithm has constant size forbidden sets then this immediately implies that it is O(1) probability-competitive. We show this in many cases, such as transversal, graphic and laminar matroids. Other matroid families are considered, and we obtain probability-competitive algorithms for all of them, beating the best known ratios even for the weaker utility variant.

Transversal matroids and Gammoids

Let G =( L fi R, F ) be a bipartite graph with independent set L and R, where the elements of R are called the terminals of G. The transversal matroid T [G] associated to G is the matroid with ground set R whose independent sets are those X ™ R that can be covered by a matching in G. We call G the transversal presentation of T [G]. Let G =(V, E) be a digraph and two subsets S, R ™ V called sources and terminals respectively, not necessarily disjoint. The gammoid,Γ ( G, S, R), is the matroid over R, where X ™ R is independent if X is linked to S, that is, if there are node-disjoint directed paths from S and ending on each element of X. We say that (G, S, R) is the gammoid presentation of the matroid. Note that transversal matroids can be seen as gammoids by declaring all the non-terminals as sources and directing the arcs in the transversal presentation from sources to terminals.

In the Transversal MSP, a transversal presentation G for an unknown ordered matroid M = T [G] is either revealed at the beginning of the process, or it is revealed online in the following way. Initially, the algorithm only knows the number of terminals. The terminals in R arrive in random order and whenever r oe R arrives, it reveals its ordinal value information and the set of its neighbors in G, which is a subset of L. In the gammoid MSP, a gammoid presentation (G, S, R) for an unknown gammoid is either revealed at the beginning or it is revealed online as elements from R arrive: When a terminal r oe R arrives, all possible S-r paths are revealed. At that time, the algorithm has access to the subgraph G t ™ G only containing the arcs belonging to every possible S-R t path and can test whether a vertex is in S or not.

Exchangeability parameter for gammoids. Let us define a parameter to control the competitiveness of our algorithm for the gammoid MSP. Let X be an independent set and let Q be a path linking a terminal r oe R \ X outside X to S. The exchangeability µ of the presentation (G, S, R) is the maximum number of paths that Q intersects in a collection of S-X paths. The intuition behind is the following: in order to include Q into the collection of paths while keeping disjointness we have to remove or exchange at least µ paths from the collection. For instance, if we define the diameter d of the gammoid presentation as the maximum number of nodes in any source-terminal path, then µ is at most d. If furthermore the terminals are sinks, that is out-degree 0, then µ is at most d ≠ 1, since paths ending at different terminals cannot intersect on a terminal.

Remark 37. This is the case for transversal matroids: their diameter in the gammoid presentation is 2 and their exchangeability is 1. For our results, we assume the algorithm also knows an upper bound µ for the exchangeability parameter, and in this case we call the problem µ-gammoid MSP or bounded exchangeability gammoid MSP.

Most of the known algorithms for transversal MSP [START_REF] Babaioff | Matroids, secretary problems, and online mechanisms[END_REF][START_REF] Dimitrov | Competitive Weighted Matching in Transversal Matroids[END_REF][START_REF] Korula | Algorithms for Secretary Problems on Graphs and Hypergraphs[END_REF] work with ordinal information. The best algorithm so far, by Kesselheim et al. [START_REF] Kesselheim | An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions[END_REF] achieves an asymptotically optimal utility-competitive ratio of e + O(1/n) for the more general (non-matroidal) vertex-at-a-time bipartite online matching problem, in which edges incident to the same arriving vertex may have different weights and the objective is to select a matching of maximum total weight. For the specific case of transversal matroid this algorithm can be implemented in the ordinal model, meaning that is e + O(1/n) ordinal-competitive. Interestingly, for the broader bipartite matchings case, Kesselheim's algorithm does not work in the ordinal model, but the previous algorithm by Korula and Pál [START_REF] Korula | Algorithms for Secretary Problems on Graphs and Hypergraphs[END_REF] does, achieving 8 ordinal-competitiveness. A recent The µ-gammoid MSP problem is a special case of the (non-matroidal) hypergraph vertex-at-a-time matching (HVM) with edges of size at most µ + 1 studied by Korula and Pál [START_REF] Korula | Algorithms for Secretary Problems on Graphs and Hypergraphs[END_REF] and later by Kesselheim et al.'s [START_REF] Kesselheim | An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions[END_REF] online hypermatching problem (see the discussion in those papers for precise definitions). They achieve O(µ 2 ) and eµ utility-competitiveness respectively. Below we propose an algorithm for the µgammoid MSP that has forbidden sets of size µ. Provided we know µ upfront we get an -(µ) probability-competitive algorithm. Note that for µ Ø 2, -(µ)=µ 1+1/(µ≠1) <eµ, so our guarantee strictly improves on that of previous algorithms for HVM and hypermatching, on the special case of µ-gammoids.

Our algorithms. We use the convention that for every vertex v covered by some matching M , M (v) denotes the vertex matched with v in M . Furthermore, for every independent set X ™ R, we select canonically a witness matching M X := witness(X) that covers X. In the case of gammoids, for any set P of node-disjoint paths linking some set X to S, and for every v oe X, P(v) denotes the unique path in P linking v to S. We also say that P covers a vertex u if u is in the union of the vertices of all paths in P. Furthermore, for every independent set X ™ R, we canonically select a fixed collection of node-disjoint S-X directed paths P X := witness(X) linking X to S, and we assume that this choice does not depend on the entire graph but only on the minimum subgraph containing all arcs in every S-X path. We also recall that on step i, R i = {r 1 ,...,r i } denotes the set of revealed terminals and G i denotes the subgraph of the presentation currently revealed.

Algorithm 3 for transversal matroids.

Input: Presentation of a transversal matroid T [G] whose terminals arrive in random order.

ÛM and ALG are the currently chosen matching and terminal vertices respectively.

1: ALG Ωÿ, s Ω Bin(n, p), M Ωÿ 2: for i = s +1 to n do 3: if r i oe OPT(R i ) and ¸i := M OPT(R i ) (r i ) is not covered by M then 4: ALG Ω ALG + r i , M Ω M fi{¸ir i } 5: Return ALG.
Algorithm 4 for µ-bounded gammoids.

Input: Presentation of a gammoid Γ := Γ(G, S, R) whose terminals arrive in random order.

ÛP and ALG are the currently chosen collection of node-disjoint paths and terminals selected respectively. 1: ALG Ωÿ, s Ω Bin(n, p), PΩÿ . 2: for i = s +1 to n do 3:

if r i oe OPT(R i ) and no vertex in the path P OPT(R i ) (r i )i sc o v e r e db yP then

4: ALG Ω ALG + r i , P Ω P fi {P OPT(R i ) (r i )} 5: Return ALG.
The algorithms above can compute OPT(R i ) without knowing the terminal weights, by just using the greedy algorithm. This requires that one is able to check independence algorithmically in each case. Indeed, for the transversal MSP algorithm, a set X ™ R i is independent if and only if the maximum cardinality matching on G i [N G (X) fi X] has size |X|. In the case of gammoids, one can check if X ™ R i is independent, by a standard reduction to a flow problem on G i . Theorem 10. Algorithm 4 has forbidden sets of size equal to the exchangeability µ of the gammoid presentation. If µ is known, we can set p = p(µ) to get an -(µ)= µ 1+1/(µ≠1) probability-competitive algorithm.

Proof. By construction, the set P contains node-disjoint paths covering ALG at every time step, hence the algorithm is correct. The sampling condition is also satisfied by design. Let r ú oe OPT(Y ) where Y is a fixed set of terminals of size t Ø s +1, and suppose that R t = Y and r t = r ú . Note that r t is selected by the algorithm if all vertices in the path P OPT(Rt) (r t ) are not covered by the collection P prior to that iteration. In other words, by defining the forbidden sets to be F(X, Y, r ú )={v oe OPT(X): P OPT(X) (v) intersects P OPT(Y ) (r ú )},

Matroidal Graph Packings

Chapter 8 the element r t is selected if r j " oe F(R j ,R t ,r t ) for all j oe{ s +1 ,...,t ≠ 1}.B y definition, each forbidden set has size at most µ. Algorithm 3 is essentially Algorithm 4 applied over the gammoid presentation of the transversal matroid T [G]. Together with Remark 37, it follows the result for the transversal MSP.

Theorem 11. Algorithm 3 has forbidden sets of size 1, and therefore, by choosing p =1/e, it is an (optimal) e probability-competitive for transversal matroids.

We remark that every constant utility-competitive algorithm so far known for transversal MSP requires to learn a bipartite presentation online. It is an open problem to find constant competitive algorithms for transversal matroids that only access the matroid via an independence oracle.

Matroidal Graph Packings

Let H be a finite set of graphs. An H-packing of a host graph

G =(V, E) is a collection Q = {H i } i=1...k of node-disjoint subgraphs of G such that each H oeQis isomorphic to some graph in H. A vertex in G is said to be covered by Q if it
belongs to some graph of Q.L e tR ™ V be a set of vertices called terminals and consider the independence system M(R, G, H)o v e rR whose independent sets are all X ™ R for which there is an H-packing covering X in G. We say that H is matroidal if M(V (G),G,H) defines a matroid for every graph G. Note that in this case, if M(R, G, H) is the restriction of M(V (G),G,H) to a subset R, then it is also a matroid. We call every such M(R, G, H) a graph packing matroid. V,E). In the matching matroid M(V, G, {K 2 }), the set {a, g, d} is independent since it is covered by the matching {{a, g}, {g, b}, {c, d}}.

Matroidal families. For an extensive treatment see Loebl and Poljak [START_REF] Loebl | On matroids induced by packing subgraphs[END_REF], Janata [START_REF] Janata | Matroids induced by packing subgraphs[END_REF] and the references therein. In the following examples, K n denotes the complete graph on n vertices and S n denotes the star with n legs. If H = {K 1 } then M(V, G, H) is the free matroid over V where all sets are independent. If H = {K 2 } then M(V, G, H) is the matching matroid of G, whose independent sets are all vertex sets that can be covered by a matching. If for some k the family H = {S 1 ,S 2 ,...,S k } is a sequential set of stars, then M(V, G, H) is matroidal. It is, in fact, the matroid union of many matching matroids. The family M(V, G, H) is also matroidal if H = {K 2 ,H} where H is either a factor-critical graph or a 1-propeller. 1 For most known matroidal classes there are polynomial time algorithms available to check independence. This is the case for all classes above. Observe that transversal matroids are instances of matching matroids restricted to one side of the bipartition of the host graph.

As we did for gammoids, we also define an exchangeability parameter µ to control the competitiveness of our algorithm. Consider an H-packing Q of G, and a subgraph H ™ G from the class H covering a terminal r oe R that is not covered by Q. The exchangeability µ of M(R, G, H) is the maximum number of terminals over all such Q and H that would become uncovered if we removed all graphs from Q that intersect H, namely,

µ := max Y ] [ ÿ H Õ oeQ : V (H)flV (H Õ )" =ÿ |V (H Õ ) fl R| : H covers a terminal not covered by Q Z \ .
This parameter may be complicated to compute but there is a simple upper bound: let h be the maximum number of vertices of a graph from H. Then the worst possible situation occurs when Q contains only graphs of size h, and H is also a graph of size h intersecting every graph in Q on exactly one vertex (different from r). In this case, all graphs from Q must be removed, so the number of newly uncovered vertices becomes h • (h ≠ 1). This means that µ AE h(h ≠ 1).

In the H-Packing MSP, the algorithm receives a collection H of graphs. A host graph G =( V, E) with terminals R ™ V is either revealed at the beginning or it is revealed online as elements from R arrive: when a terminal r oe R arrives, all possible edges that belong to a graph H ™ G with r oe V (H) with H oeH(via isomorphism) are revealed. More precisely, let R t denote the set of terminals revealed up to time t. At that time the algorithm has access to the subgraph G t ™ G induced by all vertices belonging to every possible subgraph H ™ G, with H oeHthat intersects R t . The algorithm can also test whether a vertex is a terminal or not. We also assume that an upper bound µ for the exchangeability parameter is available, and in this case we call the problem bounded H-packing MSP. Analogously to previous sections, for every independent X we select a canonical packing Q X := witness(X) that does not depend on the arrival order.

In the description of the algorithm we use the convention that for every H-packing Q of a set X, and for every v oe V covered by Q, Q(v) denotes the unique graph in Q covering v. We also recall that on step i, R i = {r 1 ,...,r i } denotes the set of revealed terminals and G i denotes the subgraph of the presentation currently revealed.

Algorithm 5 for µ bounded H-packing matroids.

Input: A matroidal family H and a host graph G =( V, E) whose terminals R ™ V arrive in random order. Û Q and ALG are the currently chosen H-packing and terminals selected respectively. 1: ALG Ωÿ, s Ω Bin(n, p), QΩÿ.

2: for i = s +1 to n do 3: if r i oe OPT(R i ) and r i is already covered by Q. then 4: ALG Ω ALG + r i . 5: else if r i oe OPT(R i ) and Q fi {Q OPT(R i ) (r i )} is an H-packing. then 6: ALG Ω ALG + r i , Q Ω Q fi {Q OPT(R i ) (r i )}. 7: Return ALG.
The algorithm can compute OPT(R i ) without knowing the terminal weights, by applying the greedy algorithm for M(R, G, H). Theorem 12. Algorithm 5 has forbidden sets of size equal to the exchangeability µ of the H-presentation. If µ is known beforehand, we can set p = p(µ) to obtain an -(µ)=µ 1+1/(µ≠1) probability-competitive algorithm for µ-bounded graph packing matroids.

Proof. Correctness and the sampling condition for forbidden sets are satisfied by design. Now let r ú oe OPT(Y ) where Y is a fixed set of terminals of size t Ø s + 1, and suppose that R t = Y and r t = r ú . Terminal r t is selected by the algorithm if either Q already covers it on arrival, or if all vertices in the graph Q OPT(Rt) (r t ) were not covered by graphs in Q prior to that iteration. In any case by defining as forbidden sets

F(X, Y, r ú )={v oe OPT(X): V (Q OPT(X) (v)) intersects V (Q OPT(Y ) (r ú )) \{r ú }},
we have that r t is selected if r j " oe F(R j ,R t ,r t ) for all j oe{ s +1,...,t ≠ 1}.B y definition, each forbidden set has size at most µ.

We remark that the competitiveness achievable by an algorithm heavily depends on the way the matroid is presented. For instance, consider a matching matroid M with host graph G =( V, E). Note that the exchangeability of this matroid is µ AE 2(2 ≠ 1) = 2. If the graph is presented online then we can use the previous algorithm to obtain an -(2) = 4 probability-competitive algorithm. If on the other hand the graph is presented upfront, then we can use the fact that every matching matroid is transversal [START_REF] Edmonds | Transversals and matroid partition[END_REF] to construct a transversal presentation of M and then apply our e probability-competitive algorithm using that presentation.

Graphic and Hypergraphic Matroids

The graphic matroid M[G]=(R, I) associated to a graph G =(V, R) is the one whose independent sets are all the subsets of edges X ™ R such that (V, X) is a forest. The hypergraphic matroid M[G] associated to a hypergraph G =(V, R), whose edges may be incident to any number of vertices, is the matroid over R whose independent sets X ™ R are those, for which one can canonically choose for every r oe X an edge denoted by edge(r,

X )=u(r)v(r) in K V =(V, 1 V 2 2
) with both endpoints in r in such a way that all edge(r, X ), for r oe X are different, and the collection edge(X)= {edge(r, X ): r oe X} is a forest [START_REF] Loréa | Hypergraphes et matroïdes[END_REF]. If all the edges of the hypergraph have size 1 or 2 we are back in the graphic case.

One can check that the hypergraphic matroid In the graphic MSP/hypergraphic MSP we assume that the underlying graph or hypergraph G of a matroid M[G] is either revealed at the beginning or revealed online in the natural way: we learn edges as they arrive. Let X ™ R be an independent set. By orienting each connected component of the forest edge(X) from an arbitrary root, we obtain a canonical orientation arc(X) of edge(X) (for convenience, we denote by arc(e, X) the oriented version of edge(e, X)) with indegree deg ≠ arc(X) (v) AE 1f o re v e r y vertex v. The converse is almost true in the following sense. If A is a set of arcs (maybe including loops) such that deg ≠ A (v) AE 1 for every vertex then the underlying graph is not necessarily a forest in K V , but a pseudoforest: every connected component contains at most 1 cycle, which is directed. In fact, the edge sets of pseudoforest of a given graph J are exactly the independent set of the so called bicircular matroid of J. This matroid is transversal with presentation H, where V (H)=V (J) fi E(J) and ve oe E(H) if and only if e is incident to v. This is the starting point for our algorithm for graphic matroids.

M[G]=( R, I) is the matroid induced from the graphic matroid M[K V ] via the bipartite graph (R fi 1 V 2 2 , Ẽ) with ef oe Ẽ if f ™ e. In other words, X is independent in the hypergraphic matroid M[G] if edge(X) is independent in the graphic matroid M[K V ]. Moreover, if G is already a graph,
The algorithm. The plan is to only consider edges that belong to the current optimum. Furthermore, if we select an edge, then we orient it and include it into an arc set A with the property that each vertex has maximum in-degree 1. Instead of using a random orientation (as in the algorithms by Korula and Pál [START_REF] Korula | Algorithms for Secretary Problems on Graphs and Hypergraphs[END_REF] or Soto [START_REF] Soto | Matroid Secretary Problem in the Random-Assignment Model[END_REF]), at every step we use the canonical orientation of the current optimum forest. In order to avoid closing a cycle we also impose that an arc (u, v) can not be added to

A if deg ≠ A (u) = 1 or deg ≠ A (v) = 1.
The same algorithm works on hypergraphic matroids if we replace each independent set X on the hypergraphic matroid by its associated forest edge(X). We also recall that on step i, R i = {r 1 ,...,r i } denotes the set of revealed edges. The algorithm is fully described below.

Algorithm 6 for graphic or hypergraphic matroids.

Input: A hypergraphic matroid M[G] with underlying hypergraph G =(V, R), whose edges
arrive in random order. Û ALG and A are the currently selected independent set and the orientation of its associated forest. 1: ALG Ωÿ, s Ω Bin(n, p), A Ωÿ.

2: for i = s +1 to n do 3: if r i oe OPT(R i ) then 4: Let a i =(u i ,v i ) be the canonical orientation of edge(r i , OPT(R i )). 5: if deg ≠ A (u i )=0=deg ≠ A (v i ) then 6: ALG Ω ALG + r i , A Ω A + a i 7: Return ALG.
Theorem 13. Algorithm 6 has forbidden sets of size 2. By setting p = p(2) = 1/2, we get an -(2) = 4 probability-competitive algorithm for both graphic and hypergraphic matroids.

Proof. We first prove that the edge set  obtained from A by removing its orientation is acyclic. Suppose by contradiction that at the end of some step i, A contains for the first time a set C such that its unoriented version Ĉ is an undirected cycle. Since this is the first time a cycle appears, r i must be selected and a i =(u i ,v i ) must be contained in C. Since a i is included in A, we know that after its inclusion, deg

≠ A (v i ) = deg ≠ C (v i )=1 (before its inclusion, the indegree of v i was 0) and that deg ≠ A (u i ) = deg ≠ C (u i ) = 0. But since Ĉ is a cycle the outdegree of u i is deg + C (u i )=2≠ deg ≠ C (u i ) = 2.
But then, there must be another vertex x in C with indegree 2. This cannot happen because at every moment the indegree of each vertex is at most 1.

The proof above guarantees correctness of the algorithm: for the graphic case, we have  = ALG and for the hypergraphic case, each edge r i of ALG is mapped to edge(r i , OPT(R i )) oe  which form a forest. In both cases we conclude ALG is independent.

Since the sampling condition is satisfied by design, we only need to prove the 2-forbidden condition. Let r ú oe OPT(Y ) where Y is an arbitrary set of t Ø s +1 edges, and suppose that R t = Y and r t = r ú . The algorithm would then define an arc a t =(u t ,v t ) and will proceed to add r t to ALG provided that no arc a j =(u j ,v j ) considered before has head v j equal to u t or v t . In other words, by defining

F(X, Y, r ú )= Ó f oe OPT(X): arc(f,OPT(X)) is not oriented towards any endpoint of edge(r ú ,OPT(Y ))
Ô then r t is selected if r j " oe F(R j ,R t ,r t ) for all j oe{ s +1 ,...,t ≠ 1}.M o r e o v e r , since each arc set arc(OPT(X)) = {arc(f, OPT(X)) : f oe OPT(X)} has maximum indegree 1, there are at most 2 arcs in arc(OPT(X)) oriented towards an endpoint of edge(r ú , OPT(Y )). So each forbidden set has size at most 2.

Column Sparse Representable Matroids

An interesting way to generalize graphic matroids is via their matrix representation. We say that a matroid M is represented by a m ◊ n matrix M with coefficients in a field F if we can bijectively map the elements of its ground set to the columns of M in such a way that the independent sets of M are in correspondence with the sets of columns that are linearly independent in F m . Graphic matroids are representable by their adjacency matrix interpreted in GF (2). In fact they can be represented in any field. Matroids that have this property are called regular. Note that each graphic matroid is representable by a very sparse matroid: each column has only 2 non-zero elements.

Following [START_REF] Soto | Matroid Secretary Problem in the Random-Assignment Model[END_REF] we say that a matroid is k column sparse representable if it admits a representation whose columns have at most k nonzero entries each. These matroids include many known classes such as graphic matroids (k = 2), rigidity matroids [START_REF] Whiteley | Some matroids from discrete applied geometry[END_REF] on dimension d (k =2 d) and more generally matroids arising from rigidity theory from d-uniform hypergraphs. These matroids are called (k, ¸)-sparse matroids (where 0 AE ¸AE kd ≠ 1), and they are, using our notation, kd column sparse [START_REF] Streinu | Natural realizations of sparsity matroids[END_REF]. Interesting cases include generic bar-joint framework rigidity in the plane [START_REF] Laman | On graphs and rigidity of plane skeletal structures[END_REF], which are characterized by (2, 3)-sparse matroids in dimension d = 2 (they are 4 column sparse) and generic body-bar framework rigidity in R d which are characterized by (

1 d+1 2 2 , 1 d+1 2 2
)-sparse matroids [START_REF] Tay | Rigidity of multi-graphs. I. Linking rigid bodies in n-space[END_REF] (they are d Let M be a matroid with k sparse representation M and let X be an independent set of columns. It is easy to show (see e.g., [START_REF] Soto | Matroid Secretary Problem in the Random-Assignment Model[END_REF]) that we can select one nonzero coordinate from each column in X such that no two selected entries lie on the same row. In other words, each independent set in M is also independent in the transversal matroid whose bipartite representations has as color classes the rows and columns of M and where a column i is connected to a row j if entry M ij is nonzero. Even though the converse is not true, we can use the intuition obtained from graphic matroids to extend the algorithm to k column sparse representable matroids with only few changes. Instead of doing that, we are going to further generalize this class of matroids in a different direction.

Multiframed matroids. A matroid M is called a frame matroid [START_REF] Zaslavsky | Frame Matroids and Biased Graphs[END_REF] if it can be extended to a second matroid M Õ (i.e. M is a restriction of M Õ ) which possesses a frame B, that is, a base such that every element of M is spanned by at most 2 elements of B. For instance, take a graphic matroid M[G] and consider the graph

H = 3 V (G)+v 0 ,E(G) fi{v 0 v : v oe V (G)} 4
where v 0 is a new vertex. Then, M[H] is an extension of M[G] containing the star centered at v 0 as basis B := " H (v 0 )={v 0 v : v oe V (G)}. Since every edge uv in G is spanned by the set {v 0 u, v 0 v} of (at most) 2 elements, we conclude that B is a frame for M[G]. We define a new class of matroids, called multiframed or k-framed matroids, in a natural way. A matroid M =(R, I) is a k-framed matroid if it admits an extension M B =( R Õ , I) having a k-frame B, i.e., a base such that each element of M is spanned by at most k elements of B. Without loss of generality we assume that B fl R = ÿ (by adding parallel elements) and R Õ = B fi R. In other words, M B is obtained by adjoining the k-frame B to the original matroid M. Observe that if M is represented by a k column sparse matrix M , then the matrix [I|M ] obtained by adjoining an identity (in the field F) represents an extension M B of M where the columns of I form a base B such that each column in M is spanned by at most k elements from B (exactly those elements associated to the k nonzero rows of the column). This means that k-framed matroids generalize k column sparse matroids. This generalization is strict since there are frame matroids that are non-representable.

We define the k-framed MSP as the variant of the MSP in which the k-framed matroid M, and its extension M B is either fully known beforehand or we simply have access to B and an independence oracle for M B (in the case of k column sparse matroid it is enough to receive the columns of the representation in an online fashion).

We need some notation. For every r in the ground set R, we define the set C(B, r)={y oe B : B + r ≠ y is independent} which is also the minimal subset of B spanning r. It is easy to see that C(B, r)+r is the unique circuit in B + r,o f t e n called the fundamental circuit of r with respect to the base B in M B . Define also for each y oe B, the set K(B, y)={r oe R : B + r ≠ y is independent}. It is easy to see that K(B, y)+y is the unique cocircuit inside R + y in the matroid M B ,o f t e n called the fundamental cocircuit of y with respect to the base B. Observe that by definition, r oe K(B, y) if and only if y oe C(B, r). Furthermore, by definition of k-framed matroids, C(B, r) has at most k elements. Before presenting the algorithm we need the following result.

Lemma 38. Let X be an independent set of a k-framed matroid M with k-frame B.

There is a (canonical) injection fi X : X ae B such that B + x ≠ fi X (x) is independent for all x oe X.

Proof. Extend X to a base X Õ of M Õ . By the strong basis exchange axiom there is a bijection fi : X Õ ae B such that B + x ≠ fi(x) is a base for all x oe X Õ . The restriction of fi to X yields the desired injection.

Algorithm 7 for k-framed matroids.

Input: A k-frame matroid M, with independence oracle access to M B and to B.T h e elements of M arrive in random order. Û ALG is the set currently selected and B Õ is the set of elements of the frame B that have been marked. Proof. Suppose that the algorithm is not correct, and let Z = {r i(1) ,r i(2) ,...,r i(¸) } be a circuit in ALG with s +1AE i(1) AE i(2) AE•••AEi(¸). When r i(1) arrived, y := fi OPT(R i( 1) ) (r i( 1) ) oe C(B, r i( 1) ) was marked. Furthermore, our algorithm guarantees that for every element r i oe ALG with i>i (1), y " oe C(B, r i ). In particular, y oe C(B, r i(j) ) if and only if j = 1, or equivalently, K(B, y) fl Z = {r i(1) }. But this implies that the circuit Z and the cocircuit K := K(B, y)+y intersect only in one element, which cannot happen in a matroid. Therefore, the algorithm is correct.

if r i oe OPT(R i ) and C(B, r i ) fl B Õ = ÿ then 4: ALG Ω ALG + r i , B Õ Ω B Õ + fi OP T (R i ) (r i ) 5: Return ALG.
Since the sampling condition is satisfied by design, we only need to prove the k-forbidden condition. Let r ú oe OPT(Y ) where Y is an arbitrary set of t Ø s +1 elements, and suppose that R t = Y and r t = r ú . The algorithm accepts r ú if and only if no element of C(B, r t ) was marked before. Let y oe C(B, r t ) be an arbitrary element. A sufficient condition for y not being marked at step j is that fi OPT(R j ) (r j ) " = y. Therefore, if we define the forbidden sets

F(X, Y, r ú )={f oe OPT(X): fi OPT(X) (f ) oe C(B, r ú )}
it is clear that r t is selected if r j " oe F(R j ,R t ,r ú ) for all j oe{s+1,...,t≠1}.M o r e o v e r , since fi OPT(X) is injective we conclude that |F(X, Y, r ú )|AE|C(B, r ú )|AEk.

Laminar Matroids and Semiplanar Gammoids

In this section we define special classes of gammoids amenable for our techniques. An arc-capacitated gammoid (ACG) M[N ] is defined by a directed network N = (G, o,R,c) where G =(V, E) is a digraph, o oe V is a single source, R ™ V \{o} is a collection of terminals and c : E ae Z + is a strictly positive integer capacity function on the arcs of G. The ground set of M[N ] is R and every set J ™ R is independent if and only if there exist an o-R flow on N satisfying the capacity constraints on the arcs and where each j oe J receives one unit of flow. Without loss of generality we assume that every terminal is reachable from o via a directed path. It is easy to see that ACGs are equivalent to gammoids without loops, but they are more closely related to transportation or distribution applications.

A semiplanar gammoid is an ACG whose digraph G admits a semiplanar drawing, which is a planar drawing where all terminals are on the x-axis, the source node is on the positive y-axis, and the rest of the graph (arcs and nodes) are strictly above the x-axis, in a way that they do not touch the infinite ray starting upwards from the source node. It is easy to see that G admits a semiplanar drawing if and only if it is planar and all the terminals and the source are contained in the same face (which could be a cycle, a tree or more generally, a pseudoforest).

Laminar Matroids. An important example of semiplanar gammoids are laminar matroids. A collection L of non-empty subsets of a finite set of terminals R is called laminar if for every L, H oeL , L fl H oe{ L, H, ÿ}. The laminar matroid M[R, L,c], where L is a laminar family over R and c : LaeZ + is a positive integer capacity function on the sets of L, is the matroid with ground set R and whose independent sets are those X ™ R for which the number of elements that X contains in any set of the laminar family does not exceed its capacity, i.e. |X fl L|AEc(L). Observe that, since c is positive, every singleton is independent. Furthermore, without loss of generality we assume that R oeL(with c(R) equal to the rank of the matroid) and that all singletons are in L (with c({r})=1foreac hr oe R). Adding those sets does not destroy laminarity. The Hasse diagram of the containment order of L forms a tree T Õ where every set in L is a child of the smallest set in L that strictly contains it. Note that the leaves of T Õ are in bijection with the terminals, and that the root (unique maximum) v R represents R. Consider the directed graph G obtained by adding an auxiliary vertex o to T Õ connected to v R and orienting the tree away from o. If we put o on the upper semiaxis, draw G with all arcs pointing downwards, and assign capacities to each arc equal to the capacity of the laminar set associated to the arc's head, then we obtain a semiplanar representation of M[R, L,c]. Furthermore, the terminals in R appear in the x-axis in the left-to-right order induced by the drawing of the tree.

Semiplanar drawings and neighbours.

In what follows we fix a semiplanar drawing G of a semiplanar gammoid M[N ]. We identify R with the set [n] by labeling the terminals from left to right as they appear in the x-axis. For convenience in the rest of the presentation, we add to G two auxiliary nodes on the x-axis, 0 and n + 1, where 0 is located to the left of 1, and n + 1 is located to the right of n, together with the arcs o0 and o(n + 1). Observe that by our assumptions on the drawing, it is possible to add those arcs without destroying semiplanarity.

For any set J ™ [n] and any y oe J fi{0,n+1}, we denote by Left J (y) the closest element to y in J fi{0} that is located strictly to its left (understanding Left J (0) = 0). Similarly, we denote by Right J (y) the first element in J fi{n +1} located to the right of y (understanding Right J (n +1)=n +1). F or y oe [n] \ J, we call Left J+y (y) and Right J+y (y) its left and right neighbors in J (note that they maybe equal to 0 or n +1 and thus are not necessarily elements of J).

Ancestors, tree-order and representatives. In the future we will map each terminal outside an independent set J to one or more of its neighbors in J. For the case in which G is a tree (i.e., for laminar matroids) we want to consistently assign each element to just one of them. We do this as follows. For every pair of nodes x, y in G, let xGy be the unique undirected x-y path in G. We say that x is an ancestor of y (and y is a descendant of x) if oGy contains oGx; in that case we denote x ˆy (and y ı x). Note that (V, ı) is a partial order, and in fact, it is a join-semilattice where x ' y is the lowest common ancestor of x and y. Note that by our drawing choice, for any i oe [j, j Õ ] ™ [0,n+ 1] we have i ı j ' j Õ . In particular, if [j,

j Õ ] ™ [k, k Õ ] ™ [0,n+1] then j ' j Õ ı k ' k Õ .
For every nonempty set J ™ [n], and for every terminal y oe [n], we define its representantive fi J (y) in J such that

fi J (y)= Y _ _ ] _ _ [ y if y oe J, Left J+y (y)
if y oe [n] \ J and y ' Left J+y (y) @ y ' Right J+y (y), Right J+y (y) if y oe [n] \ J and y ' Left J+y (y) ˆy ' Right J+y (y). This element is well defined since for all y oe [n] \ J,b o t hy ' Left J+y (y) and y ' Right J+y (y) belong to oGy and so one is an ancestor of the other. Observe that fi J (y) is never equal to 0 (because then o =0' y @ Right J+y (y) ' y which is a contradiction as o is the root), nor n+1 (because then o =(n+1)'y ı Left J+y (y)'y ı v R @ o). In particular, fi J (y) oe{ Left J+y (y),y,Right J+y (y)}flJ. A graphical way to understand the definition of the representative of an element y outside J is the following: let j and j Õ be the left and right neighbors of y in J respectively and call oGj and oGj Õ the left and right paths respectively. The representative of y is its left neighbor (respectively, its right neighbor) if and only if by starting from y and walking up on G against its orientation, the first path hit is the left path (respectively the right path). In case of a tie, the representative is the right neighbor (see Figure 8.7). We claim also that for every j oe J, the set of elements to its right having j as representative is an interval of the form [j, k] with k<Right J (j). Indeed, this is true if Right J (j)=n + 1. Suppose now that j Õ := Right J (j) AE n, and that the claim does not hold. Then, there must be two consecutive terminals i, i +1 oe [j, j Õ ] with fi J (i +1)=j and fi J (i)=j Õ . But then, we get the following contradiction:

(i +1)' j Õ ı i ' j Õ ı i ' j ı (i +1)' j @ (i +1)' j Õ
where the first inequality holds since [i +1,j Õ ] ™ [i, j Õ ], the second, by the definition of fi J (i), the third since [j, i] ™ [j, i + 1] and the fourth by definition of fi J (i + 1). Since every element in (j, j Õ ) either has j or j Õ as representative, we conclude, in fact, that the entire set fi ≠1 J (j) of elements with j as representative is an interval of terminals enclosing j but strictly contained in [Left J (j), Right J (j)]. In other words (fi J (j)) joeJ is a partition of [n] into |J| intervals.

The algorithms.

In what follows we describe our algorithms for semiplanar gammoids and laminar matroids. Apart from some special case occurring when the sample is empty, our algorithms are extremely simple. Each one computes the optimal solution OPT(R s ) of the sample and leave their elements unmarked. When a terminal r i that is part of the current optimum arrives, it checks if the (closest neighbors / representative) of r i in OPT(R s ) (are / is) unmarked. If so, it marks (them / it) and selects r i as part of the solution. The previous result applied to laminar matroids already beat the best guarantees known for that class (9.6 [79] and 3 Ô 3e [START_REF] Jaillet | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case[END_REF][START_REF] Jaillet | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case (Full version)[END_REF]). But we can do better for laminar matroids since for those, there is a unique path from the source to each terminal. We observe that this algorithm is very similar to the 3 Ô 3e competitive algorithm of Jaillet et al. [START_REF] Jaillet | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case[END_REF][START_REF] Jaillet | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case (Full version)[END_REF]. Note that the partition of the terminals given by fi OPT(Rs) induces a unitary partition matroid P Õ . After the sample, Algorithm 9 simply selects on each part, the first arriving element that is part of the current optimum. It can be shown that the partition matroid P Õ we define is the same as the one defined in [START_REF] Jaillet | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case (Full version)[END_REF]Section 3.2]. The main algorithmic difference is that in [START_REF] Jaillet | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case (Full version)[END_REF], the authors use the algorithm for the classic secretary problem to select one terminal on each part that has constant probability of being the largest element. Instead, we select the first arriving element on each part that is part of the optimum at the time of arrival. This small change makes the competitive ratio of our algorithm e times smaller than theirs, but the analysis is more involved. To prove Theorems 15 and 16 we need to develop some extra tools.

For every nonempty independent set J ™ [n] in the semiplanar gammoid M[N ]we chose an arbitrary but fixed integral o-J flow f J satisfying the arc capacity constraints and saturating J. Define the unit capacity network N 1 (J)=( G 1 (J), o,R,1), where G 1 (J) is obtained from G by splitting each arc uv with f J (uv) Ø 2 into f J (uv) parallel arcs (we keep all arcs uv with f J (uv) oe{0, 1}, we also keep the arcs o0 and o(n +1)). We do this in such a way that G 1 (J) is still semiplanar. The matroid M[N 1 (J)] is the unit capacity semiplanar gammoid associated to J.

Observe that every path in G 1 (J) corresponds canonically to an unsplitted path in G going through the same nodes. Furthermore, every arc-disjoint collection P of o-R paths in G 1 (J) can be regarded, by unsplitting parallel arcs, as an o-R flow f on G such that each arc e oe E(G), satisfies f (e) AE f J (e) AE c(e). Therefore, we have the following important lemma.

Lemma 39. Any independent set in

M[N 1 (J)] is also independent in the original matroid M[N ].
We say that two paths P and Q in the drawing of a graph cross if P enters Q on the left, shares zero or more arcs with Q and then exits Q on the right, or viceversa. A collection of paths is mutually noncrossing if no pair of them cross. 2 The o-J flow f J in the network N can be mapped to an o-J flow f 1 J in N 1 (J) in a natural way. By applying flow-decomposition on f 1 J we get a collection {P k } koeJ of arc-disjoint paths. Define also P 0 and P n+1 as the paths consisting of a single arc o0 and o(n +1) respectively. By a standard planar uncrossing argument, we can assume that all paths in {P k } koeJfi{0,n+1} are mutually noncrossing (but they can still share internal nodes, in fact all paths P k with k oe J contain o and v R , see Figure 8.8). For j oe J + 0, call j Õ = Right J+0 (j) and define the collection of arcs A j ™ E(G 1 (J)) as those that are drawn in the closed planar region R j bounded by P j , P j Õ and the x-axis. Since paths {P k } koeJfi{0,n+1} form a topological star whose tips are in the x-axis we conclude that {R k } koeJ+0 is a division of the region bounded by P 0 , P n+1 and the x-axis, and thus {A k } koeJ+0 is a covering of all arcs in G 1 (J). In fact, if 1 AE j Õ " = n + 1, then every arc of P j Õ belongs to pieces A j and A j Õ , while each arc in G 1 (J) \{P k } koeJ belongs to a single piece of the covering. Furthermore, the only terminals contained in region R j are those in [j, j Õ ]. Lemma 40. Let y oe [n] \ J, and j =L e f t J+y (y), j Õ = Right J+y y be its neighbors in J. Then there is a directed o-y path D J (y) in G 1 (J) whose arc set is completely contained in A j . Furthermore, D J (y) can be chosen so that it arcs-intersects at most one path P in (P k ) koeJ . In the semiplanar case, P must be one of P j and P j Õ , and in the laminar case, P = P fi J (¸) .

Proof. Note that y oe [j, j Õ ] is in the planar region R j . Since y is reachable from o in G, there is a path Q from o to y in G 1 (J). Let v be the last vertex in Q contained in the vertices of P j and P j Õ (v maybe in one or both paths), say v is in P oe{P j ,P j Õ }.

By concatenating the initial piece of P from o to v and the final piece of Q from v to y we get a path D J (y) that is completely contained in A j and that intersects the arcs of at most one path in {P j ,P j Õ }.

Consider the same situation in the laminar case. All arcs in P j , P j Õ and Q are splitted versions of arcs in oGj, oGj Õ and oGy respectively. The vertex v defined above satisfies v = y ' j ' j Õ .I fy ' j @ y ' j Õ then v = y ' j, fi J (y)=j and we can construct D J (y) avoiding all arcs in P j Õ by selecting P = P j in the previous argument. Analogously, if y ' j Õ ı y ' j then v = y ' j Õ , fi J (y)=j Õ , and we can choose D J (¸)t o avoid P j by setting P = P j Õ . (P2) M[N ] is laminar and for every x, y oe I, fi J (x) " = fi J (y).

If either (P1) or (P2) holds then

I is independent in M[N 1 (J)]
Proof. Suppose that (P 1) is satisfied. Then for every pair of distinct x, y oe I, the paths D J (x) and D J (y) constructed in Lemma 40 must lie on non-consecutive (and hence disjoint) regions in {R k } koeJ+0 . Therefore the paths {D J (z)} zoeI are mutually arc-disjoint from which we conclude that I is an independent set in M[N 1 (J)].

Suppose now that (P 2) is satisfied. Let x<ybe distinct terminals in I. We claim that the paths D J (x) and D J (y) are arc disjoint. If x and y belong to different regions then the only possibility for them to share an arc is that x is in R j , y oeR j Õ with j Õ = Right J (j), and both share arcs in P j Õ . But then, by Lemma 40, fi J (x)=fi J (y)=j Õ which is a contradiction.

If x and y are in the same region R j , then x, y oe [j, j Õ ] with j =L e f t J+x (x)= Left J+y (y) and j Õ = Right J+x (x) = Right J+y (y) oe J +(n + 1). Since the function fi J partitions [n] into intervals and x<y, we must have fi J (x)=j, fi J (y)=j Õ . Suppose now that D J (x) and D J (y) had an arc a in common and let w be its head. Since D J (x) and D J (y) are split versions of oGx and oGy we get that w ˆx ' y. Since w and x ' j are both in oGx, one is an ancestor of the other. Note that w cannot be an ancestor of x ' j since above the latter D J (x) coincides with P j which is arc-disjoint from D J (y) by Lemma 40 (and a is a common arc). It follows that x ' j A w ˆx ' y ˆy, and thus, x ' j ˆy ' j. But since fi J (y)=j Õ we have y ' j ˆy ' j Õ and we conclude that x ' j ˆy ' j Õ ˆjÕ . From the last expression we get x ' j ˆx ' j Õ which contradicts the fact that fi J (x)=j.

We have thus shown that all paths (D J (z)) zoeI are arc-disjoint, thence I is independent in M[N 1 (J)]. Now we are ready to define the forbidden sets of sizes at most 4 and 3 respectively for Algorithms 8 and 9.F o r ( X, r ú ) with r ú oe

[n], X ™ [n] \{ r ú } define the set F 4 (X, r ú ) given by {Left X (Left X+r ú (r ú )), Left X+r ú (r ú ), Right X+r ú (r ú ), Right X (Right X+r ú (r ú ))}, and I 4 (X, r ú )=[Left X (Left X+r ú (r ú )), Right X (Right X+r ú (r ú ))].
The set F 4 (X, r ú ) contains the 2 closest terminals to the left of r ú in X and the 2 closest terminals to its right. I 4 (X, r ú ) is the enclosing interval containing F 4 (X, r ú ). Similarly, for the case of laminar matroids, define

F 3 (X, r ú )={Left X (fi X (r ú )),fi X (r ú ), Right X (fi X (r ú ))} I 3 (X, r ú )=[Left X (fi X (r ú )), Right X (fi X (r ú ))].
where F 3 (X, r ú ) consists of the representative of r ú in X and its two neighbors, and I 3 (X, r ú ) is its enclosing interval. We need one last technical lemma to analize the algorithms performance. Lemma 42. Let X and r ú as above, and let x oe X.

(a) If x oeF 4 (X, r ú ) then I 4 (X, r ú ) ™ I 4 (X ≠ x, r ú ).

(b) If x " oe F 4 (X, r ú ) then F 4 (X, r ú )=F 4 (X ≠ x, r ú ) and I 4 (X, r ú )=I 4 (X ≠ x, r ú ).
If the matroid is laminar, the following properties also hold (ii) If x = a " = b and r ú oe [b, c], then b and c are still the closest neighbors of r ú in X ≠ x, and in particular, the representative in X ≠ x is the same as that in X, i.e., fi X≠x (r ú )=b. Note that since we removed a,L e f t X≠x (b)=a ≠ and so,

(c) If x oeF 3 (X, r ú ) then I 3 (X, r ú ) ™ I 3 (X ≠ x, r ú ). (d) If x " oe F 3 (X, r ú ) then F 3 (X, r ú )=F 3 (X ≠ x, r ú ) and I 3 (X, r ú )=I 3 (X ≠ x, r ú ).
i) If x oe{ a, b} then F 4 (X ≠ x, r ú )=( F 4 (X, r ú ) ≠ x)+a ≠ and so I 4 (X, r ú )= [a, d] ™ [a ≠ ,d]=I 4 (X ≠ x, r ú ). (ii) If x oe{ c, d} then F 4 (X ≠ x, r ú )=( F 4 (X, r ú ) ≠ x)+d + and so I 4 (X, r ú )= [a, d] ™ [a, d + ]=I 4 (X ≠ x, r ú ).
I 3 (X, r ú )=[a, c] ™ [a ≠ ,c]=I 3 (X ≠ x, r ú ) (

Part (d):

Since x " oe F 3 (X, r ú ) the neighbors of r ú in X ≠x are the same as those in X, it follows that fi X≠x (r ú )=fi X (r ú )=b,L e f t X≠x (b)=a, Right X≠x (b)=c. Therefore F 3 (X ≠ x, r ú )=F 3 (X, r ú ) and I 3 (X ≠ x, r ú )=I 3 (X, r ú ). Now we are ready to prove the guarantees for Algorithms 8 and 9.

Proofs of Theorems 15 and 16. For both algorithms, if s = 0 then |ALG| = 1 and so it is independent. In the following assume that s Ø 1. Line 6 in the algorithms guarantees that the set ALG satisfies the conditions of Lemma 41, hence ALG is independent in M[N 1 (J)], and by Lemma 39, ALG is independent in the original matroid. This proves correctness. Since the sampling condition holds by construction, we only need to check the forbidden property. For the rest of the proof, define F(X, r ú )=F i (X, r ú ), I(X, r ú )=I i (X, r ú ) where i = 4 on the semiplanar case, and i = 3 for the laminar case. We will show that the sets F(X, Y, r ú ) := F(X, r ú ) fl [n] are forbidden sets of size at most 4 for Algorithm 8 and of size 3 for Algorithm 9. Let r ú oe OPT(Y ) where Y is an arbitrary set of t Ø s + 1 elements, and suppose that R t = Y and r t = r ú . Assume now that the condition for every i oe{s +1,...,t≠ 1},r i " oe F(OPT(R i ),r t ), (ı) holds. We have to show that r t = r ú is chosen by the algorithm.

Claim. The intervals I(OPT(R i ),r ú ) are non-decreasing in i, namely, for all i AE t≠2,

I(OPT(R i ),r ú ) ™ I(OPT(R i+1 ),r ú ). Indeed, let i AE t ≠ 2. If OPT(R i )=O P T ( R i+1
) then the claim is trivial, so assume otherwise. In particular, we have r i+1 oe OPT(R i+1 ) \ OPT(R i ). To simplify notation, let A =O P T ( R i+1 ) and A Õ = A ≠ r i+1 . By condition (ı), r i+1 " oe F(A, r ú ), and then by Lemma 42 using X = A,

F(A, r ú )=F(A Õ ,r ú ) and I(A, r ú )=I(A Õ ,r ú ). (8.1)
By the matroid exchange axiom we have two cases: either OPT(R i )=A Õ or OPT(R i )=A Õ +r for some r " = r i+1 . In the first case we have by (8.1) that I(OPT(R i ),r ú )=I(A Õ ,r ú )=I(A, r ú )=I(OPT(R i+1 ),r ú ), which ends the proof, and so we focus on the the second case. If r oeF(A Õ +r, r), then by (8.1) and Lemma 42 applied to X = A Õ +r, we have I(OPT(R i ),r ú )=I(A Õ +r, r ú ) ™ I(A Õ ,r ú )= I(A, r ú )=I(OPT(R i+1 ),r ú ). On the other hand, if r " oe F(A Õ +r, r), then, again by Lemma 42 and and (8.1) we have I(OPT(R i ),r ú )=I(A Õ +r, r ú )=I(A Õ ,r ú )= I(A, r ú )=I(OPT(R i+1 ),r ú ). This concludes the proof of the claim.

We show how to finish the proof using the claim. Suppose that r i is selected by the algorithm for some i oe{ s +1,...,t≠ 1}.B y( ı) and the claim we deduce that r i " oe I(OPT(R i ),r ú ) ´I(OPT(R s ),r ú ). In particular r i is far away from r ú : (a) In the semiplanar case, there are at least 2 terminals of the set OPT(R s )b etween r ú and r i . In particular, {Left OPT(Rs)+r i (r i ), Right OPT(Rs)+r i (r i )} and {Left OPT(Rs)+r ú (r ú ), Right OPT(Rs)+r ú (r ú )} do not intersect and so, at iteration i, neither Left OPT(Rs)+r ú (r ú ) nor Right OPT(Rs)+r ú (r ú ) are added into B.

(b) In the laminar case, there is at least one terminal of the set OPT(R s )b e t w e e n fi OPT(Rs) (r ú ) and r i . In particular, fi OPT(Rs) (r i ) " = fi OPT(Rs) (r ú ), and so, at iteration i, fi OPT(Rs) (r ú ) is not added into B.

Since the statements above are satisfied for every i AE t ≠ 1, we conclude that at time t, r t = r ú satisfies the conditions in line 6 of the algorithms, and so it is selected. This concludes the proof that Algorithms 8 and 9 have forbidden sets of sizes 4 and 3 respectively.

Chapter 9

Algorithm for Uniform Matroids

We devise a variant of Kleinberg's algorithm [START_REF] Kleinberg | A Multiple-Choice Secretary Algorithm with Applications to Online Auctions[END_REF] for uniform matroids whose probability competitiveness tends to 1 as the rank fl goes to infinity. Kleinberg's algorithm is better described when both the rank fl =2 k and the number of elements n =2 N are powers of 2. It was originally presented in a recursive manner, but it is illustrative to describe it without using recursion.

Kleinberg's algorithm. For every i oe N, let I i be the interval of the first n/2 i elements. Then the intervals J k := I k ,J k≠1 := I k≠1 \I k ,...,J 1 := I 1 \I 2 and J 0 = I 0 \I 1 partition the ground set R. The algorithm treats each interval in {J 0 ,J 1 ,...,J k } separately. For 0 AE i AE k ≠ 1, it selects at most b i = fl/2 i+1 elements from J i and at most one element from J k , so that in total at most fl elements are selected. The way the algorithm selects an element or not is determined by a threshold for each interval. Namely, it selects the first arriving element from J k and for i oe{ 0, 1,...,k ≠ 1}, the algorithm uses as threshold in the interval J i the (fl/2 i )-th highest element seen strictly before the interval, i.e., the (fl/2 i )-th element of I i+1 . It selects every element better than this threshold until the budget b i of the interval is depleted, ignoring all the elements arriving later in this interval.

The probability-ratio of Kleinberg's algorithm is at least 4/3. Kleinberg [START_REF] Kleinberg | A Multiple-Choice Secretary Algorithm with Applications to Online Auctions[END_REF] shows that the previous algorithm is guaranteed to obtain an expected fraction 1≠O( Ò 1/fl) of the optimum weight, which in our notation means to be 1

/(1 ≠ O( Ò 1/fl)) = 1 + O( Ò 1
/fl) utility-competitive. This guarantee also holds for the ordinal notion since the algorithm does not need weights. However, as we show next, its probability competitiveness is bounded away from 1. Since J 0 and I 1 have the same cardinality, with probability tending to 1/4 as fl goes to infinity, we simultaneously have that |I 1 fl R fl≠1 | < |J 0 fl R fl≠1 | and r fl oe J 0 . Given that, the threshold for J 0 , which is the fl/2-th element of I 1 , will be attained by an element of R fl≠1 which is strictly better than r fl . Thus, r fl will not be selected. Therefore, the algorithm selects r fl (which is in OPT) with probability at most 1 ≠ 1/4=3/4.

An asymptotically 1 probability-competitive algorithm. The next algorithm is a simple modification of Kleinberg's, which we write in a continuous setting. Every element is associated with a uniform random variable with support [0, 1). It is useful for this part to imagine [0, 1) as a time interval, and identify the realization of the uniform random variable as the arrival time of the element. For each j oe N, let I j be the interval [0, 2 ≠j ) and J j =[ 2 ≠j≠1 , 2 ≠j ) to be its second half. The sequence {J j } joeN partitions the interval [0, 1). For convenience, let K j =[2 ≠j≠1 , 2 ≠j≠1 (2 ≠ 4Á j )) be the left (1 ≠ 4Á j ) fraction of the interval J j , for some parameter Á j , depending on fl,t obe chosen later. Compute the index j such that t i oe J j =[2 ≠j≠1 , 2 ≠j ).

5:

Compute the threshold f j equal to the Á( 12 ) j+1 (1 + Á j )flË-th highest element in R i with arrival time in I j+1 =[0, 2 ≠j≠1 ).

6:

if less than ( 12 ) j+1 fl elements with arrival in J j have been selected and r i º f j then 7: Proof of Theorem 43. Since the algorithm selects at most (1/2) j+1 fl elements from interval J j , in total at most q joeN (1/2) j+1 fl = fl elements are included into ALG. Therefore, the algorithm is correct. Since the matroid is uniform of rank fl, the optimal base is OPT = {r 1 ,r 2 ,...,r fl }.L e tr ú = r k oe OPT, for some k oe{1,...,fl}. In what follows, let j be an integer such that 0 AE j AEÂ 1 2 log(fl/96)Ê := j ú and let Á j = Ò 12 • 2 j ln fl/fl. We first find a lower bound on the probability that r ú is selected, given that its arrival time is in J j .

ALG Ω ALG + r i 8: Return ALG. 0 ••• 0.25 0.5 1
I 0 I 1 J 0 I 2 J 1 I 3 J 2 . . .
For each r i oe R ≠ r ú , let X (j) i and Y

(j) i be the indicator variables that the arrival time of r i is in I j+1 and K j respectively. Let ‡(f j ) be the global ranking of the computed threshold f j , that is, r ‡(f j ) = f j . Consider the following three events,

ÿ ioe[fl+1]\{k} X (j) i < (1 + Á j ) 2 j+1 fl, ÿ ioe ËÏ 1+Á j 1≠Á j fl Ì +1 È \{k} X (j) i Ø 1+Á j 2 j+1 fl, ÿ ioe ËÏ 1+Á j 1≠Á j fl Ì +1 È \{k} Y (j) i < 1 2 j+1 fl,
that we call U 1 ,U 2 and U 3 respectively. Consider a fourth event, U 4 , that is t k oe K j where t k is the arrival time of r k . We claim that provided t k oe J j , the intersection of these four events guarantees that r ú is selected by the algorithm. Conditional on the event that t k oe J j ,e v e n tU 1 fl U 2 implies that fl +1 < ‡(f j ) AEÁ(1 + Á j )fl/(1 ≠ Á j )Ë +1 and r ú º f j .E v e n tU 2 fl U 3 implies that the number of elements strictly higher than the threshold f j and arriving on interval K j is strictly less than ( 12 ) j+1 fl. In particular, this implies that the algorithm has not selected enough elements in the interval J j . Therefore, conditional on the event that t k oe J j , the event U 1 fl U 2 fl U 3 fl U 4 implies that r ú oe ALG. Calling U i to the negation of event U i , by union bound and noting that events from 1 to 3 are independent of the arrival time of r ú = r k , we have Pr(r k " oe ALG | t k oe J j ) AE q 4 i=1 Pr(U i | t k oe J j )=Pr(U 1 )+Pr(U 2 )+Pr(U 3 )+4Á j . The random variables {X (j) i } ioe[n]\{k} are independently and identically Bernoulli distributed of parameter equal to the length of I j+1 , that is 2 ≠j≠1 . Similarly, the random variables {Y (j) i } ioe[n]\{k} are independently and identically Bernoulli distributed of parameter equal to the length of K j that is (1 ≠ 4Á j )2 ≠j≠1 . In the following we upper bound the probabilities in the sum above by using the Chernoff bound [85, p. 64-66, Theorems 4.4 and 4.5], then Pr(U 1 ) AE exp Let µ X and µ Y be the expected sums of the random variables X 2 j+1 Ø 1+Á j 1≠Á j • fl 2 j+1 . The choice of j guarantees that 1/fl < ' j < 1/8, and therefore

µ Y = G 1+Á j 1 ≠ Á j fl H 1 ≠ 4Á j 2 j+1 AE A 1+Á j 1 ≠ Á j + Á j B fl • 1 ≠ 4Á j 2 j+1 AE (1 ≠ 4Á j )(1 + 2Á j ) 1 ≠ Á j fl 2 j+1 AE 1 1+Á j • fl 2 j+1 ,

Chapter 10

C k = {r oe R : c k º r} the lowest layer.F o rj oe{1,...,k≠ 1}, the j-th layer is the set C j = {r oe R : c j º r º c j+1 }. By construction, the layers {C 0 ,C 1 ,...,C k } induced by C form a partition of R. In the following we call a tuple (M,F,C,º)alayered matroid.

An algorithm for the Layered-MSP first sees F but is unable to select any of its elements. The rest of the elements of M arrive in uniform random order. At time step t, the algorithm can get the full value order in R t by using only ordinal information, it can use an independence oracle to test any subset of R t and it can also check membership of any element to each layer induced by C. We say that an algorithm for the Layered-MSP is --competitive if it returns an independent set ALG oeI, and for each j oe{ 0, 1,...,|C|}, E[|ALG fl C j |] Ø1 -|OPT fl C j |, where the expectation is taken both over the distribution of F and the internal algorithm randomness.

Theorem 45 (Feldman et al.,[START_REF] Feldman | A Simple O (log log(rank)) -Competitive Algorithm for the Matroid Secretary Problem[END_REF]Corollary 4.1]). There exists an 8Álog(|C|+1)+1Ëcompetitive algorithm for the Layered-MSP.

For the sake of completeness we include the mentioned algorithm for Layered-MSP of Feldman et al. We remark that the algorithm was introduced in the context of the utility version. Nevertheless, the result above follows in the absence of weights.

Algorithm 12 (Feldman et al. [39]) for Layered-MSP Input: A layered matroid (M,F,C,º)

1: Let • be a uniformly at random number from {0, 1,...,Álog(|C| +1)Ë}.

2: Let ∆ be a uniformly at random number from {0, 1,...,2 Let i be such that r oe B i .

8:

if i oe H and r oe N i and T i + r oeI i then 9:

T i Ω T i + r. From Layered-MSP to ordinal MSP. The main result of this section corresponds to the lemma below, which is a reduction between the ordinal MSP and the version introduced in this section, the Layered MSP. In particular, it allows us to design ordinal/probability-competitive algorithms as long as we have a competitive algorithm for the Layered MSP. Theorem 9 follows directly using this lemma, and the rest of this section is devoted to prove the lemma. Proof of Theorem 9. We observe that g(x)=8 Álog(x +1)+1Ë is non-decreasing, so we can apply Lemma 46 using Algorithm 12 and Theorem 45.

In the following, let A layer be a g(|C|)-competitive algorithm for the layered-MSP. Our algorithm for Lemma 46 (i), depicted as Algorithm 13, first gets a sample from R with expected size n/2, and constructs a partition C using the optimum of the sample. By sampling a set F over the remaining elements it feeds A layer with a layered matroid. Lemma 46 (i). Let OPT = {f (1),...,f(fl)} be such that f (1) º f (2) º ••• º f (fl). Consider the function T : N ae N given by T (0) = 0, T (i)=|{r oe R : r º f (i)}| if i oe [1,fl] and T (i)=n if i>fl . In particular, for i oe [1,fl], T (i) is the number of elements in M that are at least as high as the i-th element of OPT, so f (i)=r T (i) . Observe that for all k such that T (i) AE k<T (i + 1) we have |OPT fl R k | = i. In the following we study the expected number of elements from R k that the algorithm selects, so we can conclude using Lemma 33.I fT (0) AE k<T (1) it holds E[|ALG fl R k |]=0=|OPT fl R k |, so this case is done.

Proof of

Let k oe N be such that T (1) AE k<T (8). Let f be the highest non-loop element in the value order with f (1) º f . With probability at least 1/4, it holds that f (1) oe R \ R s and f oe R s . In this case, f oe OPT(R s ), since f (1) = s(1), and the only non-loop element of C 0 is f (1). Thus, C 0 = {f (1)} =OPT(R \ R s ) fl C 0 . Therefore, Pr(C 0 = {f (1)}) Ø Pr(f (1) oe R \ R s ,f oe R s ) Ø 1/4. Let j Ø 3 and k be such that T (2 j ) AE k<T (2 j+1 ). We denote q =2 j≠3 .L e t A j be the event where |{f (1),...,f(2q)}flR \ R s |Øq and B j is the event where |{f (2q +1),...,f(6q)}flR s |Ø2q. We have that Pr(A j fl B j ) Ø 1/4, since in our algorithm the probability for an element to be sampled equals the probability of not being sampled. Observe that any subset of elements strictly better than f (t) has rank at most t ≠ 1, and therefore f (2q) ≤ s(2q). If B j holds, then s(2 j≠2 )=s(2q) ≤ f (6q). Since f (6q) ≤ f (8q)=f (2 j ), it follows that Since g is non-decreasing and |C|AE1+log ¸AE 1+log fl, Algorithm A layer is g(1+log fl)competitive. Since events A j and B j depend only on the sampling at line 1 of the algorithm (before executing A layer ) and by using linearity of the expectation and the observation above we have that To prove Lemma 46 (ii), consider Algorithm 14 depicted above. Before the analysis, it will be useful to consider the next process. Let (X t ) toeN be a sequence of Bernoulli independent random variables such that Pr(X t =0 )=P r ( X t =1 )=1 /2f o re v e r y t oe N.W ec r e a t et w os e t sV, W ™ R iteratively using the following procedure.

Algorithm 15

Coupling procedure Input: Matroid M(R, I, º).

1: Initialize V Ωÿ, W Ωÿand ◊ Ω 0.

2: for i =1ton do 3:

if r i oe OPT(V + r i ) then 4:

◊ Ω ◊ + 1 and Y ◊ = X i .

5:

if Y ◊ =0then 6:

V Ω V + r i 7:

else W Ω W + r i .

The value ◊ represents a counter on the elements that improve over the current set V . When the counter is updated, we say that the element considered on that iteration is assigned coin Y ◊ . Lemma 47. (V, W) has the same distribution as (OPT(R s ),R + s ) in Algorithm 14. Proof. Let (V i ,W i ) n i=1 be the states of the coupling process at the end of each iteration. Let Z = {r i : X i =0 }. Observe that Z and the sample R s of Algorithm 14 have the same distribution. Since the coupling procedure checks from highest to lowest element, it follows that V i =OPT(Z flR i )foreveryi oe{1,...,n}, and therefore V n =OPT(Z).

To conclude the lemma it suffices to check that W n = {r oe R \ Z : r oe OPT(Z + r)}. In fact, it can be proven by induction that W i = {r oe R i \ Z : r oe OPT(V i + r)} for every i oe{1,...,n}, and the lemma follows, since R n = R and V n =OPT(Z). Lemma 46 (ii). Thanks to Lemma 47 we assume that (OPT(R s ),R + s ) is generated by the process described in Algorithm 15. In what follows, fix f (j)=r T (j) oe OPT. We know that at step T (j) of the coupling procedure, f (j) oe OPT(R s + f (j)) no matter the trajectory of (X i ) ioeN .L e t ◊ be such that r T (j) is assigned coin Y ◊ , 10.2. Comparison between ordinal measures Chapter 10 that is, Y ◊ = X T (j) . Then, with probability at least 1/8, the event E defined as Y ◊≠1 = Y ◊+1 = 0 and Y ◊ = 1, holds. If E happens, let s(h) be the element of OPT(R s ) who was assigned coin Y ◊≠1 . In particular, the element s(h + 1) is assigned coin Y ◊+1 . Thus, C h = {r oe R + s : s(h) º r º s(h +1)} = {f (j)} =OPT(R + s ) fl C h .

Proof of

Therefore by using that the occurrence of E is decided before executing

A

Comparison between ordinal measures

In this section we discuss about some incomparability results for the competitiveness measures previously introduced. We show that an algorithm that is utility-competitive is not necessarily competitive for the rest of the measures. In particular, we provide an instance where the O(log fl) utility-competitive algorithm by Babaioff, Immorlica and Kleinberg [START_REF] Babaioff | Matroids, secretary problems, and online mechanisms[END_REF] has a poor competitiveness for the other three. Regarding the notions of the ordinal MSP, we show that the intersection and the ordinal measures are incomparable. More specifically, we show the existence of an algorithm and an instance where it is arbitrarily close to 1 intersection-competitive, but have an unbounded ordinal/probability-competitiveness. And on the other hand, we also show the existence of an algorithm and an instance where it is arbitrarily close to 1 ordinalcompetitive, but has an unbounded intersection/probability-competitiveness. Recall that probability is the strongest in the sense that it implies competitiveness for all the other measures considered (see Lemma 34).

In the utility variant, the weight w(r) of an element is revealed to the algorithm when arrived. Suppose for simplicity that the rank fl of the matroid is known3 and that the weights the algorithm sees are all different. In the above mentioned algorithm, called by the authors the Threshold Price Algorithm (TPA), it is taken a sample R s of s ≥ Bin(n, 1/2) elements 4 and it records the top weight w ú of a non-loop5 element seen in R s . It chooses uniformly at random a number • in the set {0, 1, 2,...,Álog 2 flË}, and then it selects greedily any non-sampled element whose weight is at least T = w ú /2 • . Theorem 48 (Babaioff et al. [11]). The algorithm TPA is O(log fl) utility-competitive.

Résumé

L'optimisation convexe a été un outil puissant pour concevoir des algorithmes. Dans la pratique est largement utilisé dans des domaines tels que la recherche opérationnelle et l'apprentissage automatique, mais aussi dans de nombreux problèmes combinatoires fondamentaux, ils cèdent aux algorithmes d'approximations les mieux connues fournissant des garanties inconditionnelles sur la qualité de la solution. Dans la première partie de ce travail, nous étudions l'effet de la construction de relaxations convexes sur un problème d'emballage, basé sur l'application de méthodes de levage et de projet. Nous montrons une faiblesse de ces relaxations lorsqu'elles sont obtenues à partir des formulations naturelles de ce problème, en montrant l'impossibilité de réduire l'écart même lorsque ces relaxations sont très importantes. Nous fournissons un moyen de combiner des procédures de rupture de symétrie et des méthodes de levage et de projet pour obtenir des écarts arbitraires.

Dans la deuxième partie de cette thèse, nous étudions les problèmes de sélection en ligne, c'est-à-dire que les éléments arrivent dans le temps et nous devons en sélectionner certains irrévocablement pour répondre à certaines contraintes combinatoires, mais aussi pour maximiser la qualité de la sélection. Habituellement, cette qualité est mesurée en termes de poids, mais nous considérons une variante plus forte dans laquelle les poids ne sont pas nécessairement connus en raison de la disponibilité de l'information. Au lieu de cela, tant que nous pouvons classer les éléments, nous pouvons fournir un cadre général pour obtenir des algorithmes d'approximation avec de bons ratios compétitifs dans de nombreux contextes.

Mots Clés

Programmation linéaire, Programmation semidéfinie, Ordonnancement, Selection en ligne, Algorithmes d'approximation.

Abstract

Convex optimization has been a powerful tool for designing algorithms. In practice is a widely used in areas such as operations research and machine learning, but also in many fundamental combinatorial problems they yield to the best know approximations algorithms providing unconditional guarantees over the solution quality. In the first part of this work we study the effect of constructing convex relaxations to a packing problem, based on applying lift & project methods. We exhibit a weakness of this relaxations when they are obtained from the natural formulations of this problem, by showing the impossibility of reducing the gap even when this relaxations are very large. We provide a way of combining symmetry breaking procedures and lift & project methods to obtain arbitrarily good gaps.

In the second part of this thesis we study online selection problems, that is, elements arrive over time and we have to select some of them, irrevocably, in order to meet some combinatorial constraints, but also trying to maximize the quality of the selection. Usually this quality in measured in terms of weight, but we consider a stronger variant in which weights are not necessarily known because of information availability. Instead, as long as we can rank the elements, we can provide a general framework to obtain approximation algorithms with good competitive ratios in many contexts.

x 1 x 2 Figure 2 :

 22 Figure 2: By introducing a Chvatal-Gomory cut, one improves the integrality gap by removing basic feasible solutions that are fractional. The constraint x 2 AE 4 is valid for every integer feasible solution.

Figure 1 . 1 :

 11 Figure 1.1: Example of a schedule on three identical machines.

ÿ

  CoeC y iC = 1 for all i oe M , (1.1) ÿ ioeM ÿ CoeC m(p, C)y iC = n p for all p oe{p j : j oe J}, (1.2)y iC Ø 0 for all i oe M, for all C oeC.(1.3)

Figure 1 . 2 :

 12 Figure 1.2: Machine scheduled according to a configuration C with makespan T =13, with m(3,C)=2 ,m(1,C) = 1 and m(4,C) = 1. The load of the configuration is 2 • 3+1• 1+1• 4=11.

K K 1 K 2 Figure 1 . 3 :

 1213 Figure 1.3: Two tightenings of a polytope using the hierarchy.

Figure 1 . 5 :

 15 Figure 1.5: Organization of Part I.

Figure 2 . 1 :

 21 Figure 2.1: On the left, the Petersen graph G 1 . On the right, the mutigraph G 3 obtained from considering 3 copies of each edge in the Petersen graph.

Figure 2 . 2 :

 22 Figure 2.2: The edges in purple induce the configuration {20 +2 4 , 2 0 +2 4 , 2 4 +2 9 , 2 9 + 2 6 , 2 3 +2 8 } and the orange edges induce the configuration {2 0 +2 4 , 2 4 +2 3 , 2 3 +2 8 , 2 9 + 2 7 , 2 2 +2 1 }.The first has a load of 1402 and the second has a load of 951.

2. 1 .Figure 2 . 3 :Lemma 1 .

 1231 Figure 2.3: The Petersen graph and its six perfect matchings (coloured edges). Observe that the blue matchings are isomorphic.

  CoeCm(p, C)y Hfi{(i,C)} = n p y H for all p oe{p j : j oe J}, for all H oeP r (M ◊C),

Corollary 7 . 4 .

 74 Consider the problem of scheduling identical machines to minimize the makespan with a fixed number of machines equal to m. Then, the m = O(1) level of the SA hierarchy over the configuration LP has an integrality gap equal to 1. Proof of Theorem 3. The convexity of the set SA m proj (clp(T )) and Lemma 5(i) imply that SA m proj (clp(T )) ´conv 3 clp(T ) fl{0, 1} M ◊C The other inclusion comes from applying Lemma 6 with S = M and r = m.

machine 9 Figure 4 . 1 :

 941 Figure 4.1: Consider the instance I 3 , with nine machines. It is shown the partial schedule given by the M -matching {(1,C 1 ), (2,C 1 ), (3,C 2 )}; the machines in {4,...,9} are fractional.

Figure 4 . 2 :

 42 Figure 4.2: Proof scheme: The protection matrices are positive semidefinite.

3k≠|A| 6 and

 6 therefore the task now is to check that two matrices of constant dimension are positive semidefinite.Lemma 22.For every M -matching A in M ◊C -, the covariance matrix Cov + (A) belongs to Sym

Figure 5 . 1 :

 51 Figure 5.1: Permutation matrix of ‡ =(12)(34)(5).

Figure 5 . 2 :

 52 Figure 5.2: Schedule of an instance with three machines and five jobs. Effect of the permutation ‡ = (13) in the solution.

ÿLemma 27 .

 27 H™J:K™H (≠1) |H\K| ext(x) Ifi({i}◊H) , for every I oeP 2(r≠|K|)+2 (M ◊ J). The following property is usually called the Möbius inversion in the moment matrices literature, or inclusion-exclusion in the probability context. Let x oe Las r (assign(B, T)) and i oe M . Then, x = q K™J x(i, K). Proof. Let I oeP 2r+2 (M ◊J). By substituting, parameterizing in H \K and reordering the summation it follows that ÿ K™J x(i, K) I = ÿ K™J ÿ H™J:K™H (≠1) |H\K| ext(x) Ifi({i}◊H) |R| ext(x) Ifi({i}◊H) = ÿ H™J ext(x) Ifi({i}◊H) ÿ R™J:R™H (≠1) |R| .

  Feldman et al.'s algorithm

Figure 6 . 1 :

 61 Figure 6.1: Organization of Part II.

(

  M1) if I oeI and I Õ ™ I, then I Õ oeI, (M2) if I 1 and I 2 are in I and |I 1 | < |I 2 |, then there is an element e oe I 2 \ I 1 such that I 1 fi{e}oeI.

Figure 6 . 3 :

 63 Figure 6.3: The probability notion is the strongest. The intersection notion is incomparable to the ordinal one.

Definition 35 .

 35 An algorithm has forbidden sets of size k if it has the following properties. 1. (Correctness) The algorithm returns an independent set ALG. 2. (Sampling property) It chooses a sample size s at random from Bin(n, p)f o r some fixed sampling probability p, and it does not accept any element from the first s arriving ones. 3. (k-forbidden property) For every triple (X, Y, r ú ) with Y ™ R, r ú oe OPT(Y )

Figure 7 . 1 :

 71 Figure 7.1: Given a bipartite graph, in the transversal matroid a set of nodes on the bottom side is independent if there exists a matching covering them. The thick edges {{a, 3}, {b, 1}, {c, 2}} form a matching providing a witness for {a, b, c}.

Figure 8 . 1 :

 81 Figure 8.1: Presentation of a transversal matroid with terminals R = {a, b, c, d, e}. The sets {a, b, c} and {a, d, e} are bases.

8. 1 .Figure 8 . 2 :

 182 Figure 8.2: Presentation of a gammoid with terminals R = {a, b, c, d, e} and sources S = {1, 2, 3}. The sets {a, b, e} and {a, b, d} are bases. The diameter of this gammoid presentation is 4, then the exchangeability µ is at most 3.

Figure 8 . 3 :

 83 Figure 8.3: The Petersen graph (V, E). In the matching matroid M(V, G, {K 2 }), the set {a, g, d} is independent since it is covered by the matching {{a, g}, {g, b}, {c, d}}.

Figure 8 . 4 :

 84 Figure 8.4: Canonical orientation (at the right) of the forest at the left.

Figure 8 . 5 :

 85 Figure 8.5: Representation of the graphic matroid in the graph K 4 . The columns representing the tree {{a, b}, {a, c}, {c, d}} are linearly independent.

Theorem 14 .

 14 Algorithm 7 has forbidden sets of size k. By setting p = p(k), we get an -(k) probability-competitive algorithm for k-framed matroids.

Figure 8 . 6 :

 86 Figure 8.6: Laminar family.

Figure 8 . 7 :

 87 Figure 8.7: Semiplanar drawing of a laminar matroid with ground set[START_REF] Bateni | Submodular secretary problem and extensions[END_REF]. Nonunit arc capacities are shown. Below we show the partition (fi J (j)) joeJ induced by the independent set J = {3, 5, 10, 13, 15}.

5 : 6 :Theorem 15 . 3 Ò 1 / 4

 5615314 for i = s +1 to n do if r i oe OPT(R i ) and fi OPT(Rs) (r i ) " oe B then 7:ALG Ω ALG + r i , and B Ω B fi{fi OPT(Rs) (r i )}.8: Return ALG. Algorithm 8 has forbidden sets of size 4. By setting p = p(4) = we get an -(4) = 4 4/3 ¥ 6.3496 probability-competitive algorithm for semiplanar ACGs.

Theorem 16 .

 16 Algorithm 9 has forbidden sets of size 3. By setting p = p(3) = Ò 1/3 we get an -(3) = 3 Ô 3 probability-competitive algorithm for laminar matroids.

Figure 8 . 8 :

 88 Figure 8.8: On the left, a flow f J associated to the independent set J = {1, 4, 6, 11} on a semiplanar gammoid M[N ] with ground set R = [13] (0 and 14 are auxiliary nodes). On the right, M[N 1 (J)] and the partition of the drawing into regions R 0 , R 1 , R 4 , R 6 and R 11 induced by the paths {P j } joeJfi{0,14} . The regions R 0 , R 4 and R 11 are shaded.

Lemma 41 .

 41 Let J ™ [n] be a nonempty independent set in M[N ] and I ™ [n] \ J. Consider the following properties. (P1) For every x, y oe I with x " = y, {Left J+x (x), Right J+x (x)}fl{Left J+y (y), Right J+y (y)} = ÿ.

Proof of Lemma 42 .

 42 Part (a): Let F 4 (X, r ú )={a, b, c, d} from left to right (note that near the borders we could have a = b or c = d), in particular a AE b AE r ú AE c AE d. Denote by a ≠ =Left X (a) and d + = Right X (d).

(

Part (b) :

 : Direct. For parts (c) and (d) let F 3 (X, r ú )={a, b, c} from left to right (in particular b = fi X (r ú ), note that we could be in the cases a = b =0o rb = c = n + 1). Denote by a ≠ =Left X (a) and c + = Right X (c). Part (c): We have many possibilities to analyze. (i) If x = b, then the closest neighbors of r ú in X ≠ x are a and c. In particular fi X≠x (r ú ) is either a or c.I nb o t hc a s e s ,I 3 (X, r ú )=[a, c] ™ I 3 (X ≠ x, r ú ).

  iii) The case x = c " = b and r ú oe [a, b] is analogous to the previous one (iv) If x = a " = b, and r ú oe [a, b], then the closest neighbors of r ú in X ≠ x are a ≠and b. We have that r ú ' b ı r ú ' a ı r ú ' a ≠ where the first inequality holds since fi X (r ú )=b and the second one since [a, r] ™ [a ≠ ,r ú ]. We conclude that fi X≠x (r ú )=b. In particularI 3 (X, r ú )=[a, c] ™ [a ≠ ,c]=I 3 (X ≠ x, r ú ).(v) If x = c " = b and r ú oe [b, c] then the closest neighbors of r ú in X ≠ x are b and c + . We have that r ú ' b @ r ú ' c ı r ú ' c + where the first inequality holds since fi X (r ú )=b and the second holds since [r ú ,c] ™ [r ú ,c + ]. We conclude that fi X≠x (r ú )=b. In particular I 3 (X, r ú )=[a, c] ™ [a, c + ]=I 3 (X ≠ x, r ú ).

Figure 9 . 1 :Theorem 43 .

 9143 Figure 9.1: Definition of the sets I j and J j

3 ≠ 12 • 2 j ln fl 3fl 2 ≠j≠1 fl 4 =exp 3 ≠2 ln fl 4 AE 1

 3124341 fl .

10 :

 10 Return ALG = fi ioeH T i .About the algorithm of Feldman et al. We denote by odd(k) and even(k) the odd and even numbers, respectively, in the set {0, 1,...,k}. The set I i is the independent sets family of a matroid M i =(N i , I i ) defined as follows. Let B Øi = fi joe{i,...,Á(∆+|C|)/2 • Ë} B j . The matroid M 1 is obtained from M by contracting 1 F fl B Ø2 and then restricting 2 to B 1 .F o ri>1, M i is obtained from M by contracting F fl B Øi+1 and then restricting it to B i fl span(F fl B Øi≠1 ).

Lemma 46 .

 46 Suppose there exists a g(|C|)-competitive algorithm for the Layered-MSP, where g is a non-decreasing function. Then, (i) there exists an O(g(1 + log fl)) ordinal-competitive algorithm for the MSP, and (ii) there exists an O(g(1 + fl)) probability-competitive algorithm for the MSP.

Algorithm 13 O 1 : 3 :

 1313 (g(1 + log fl)) ordinal-competitive algorithm Input: Matroid M(R, I, º) in random order r 1 ,r 2 ,...,r n . Let s ≥ Bin(n, 1/2) and compute OPT(R s )={s(1),...,s(¸)}, where s(1) º s(2) º•••ºs(¸). 2: Let C = {s(1),s(2),s(4),...,s(2 k≠1 )}, where k = Âlog ¸Ê +1. Let t ≥ Bin(n ≠ s, 1/2) and let F = {r s+1 ,...,r s+t } be the next t elements from R \ R s . 4: Return ALG = A layer (M| R\Rs ,F,C,º).

10. 1 .

 1 Ordinal/Probability: Proof of Theorem 9 Chapter 10Since g is non-decreasing and |C|AE1+log ¸AE 1+log fl, Algorithm A layer is g(1+log fl)competitive. Furthermore, the event C 0 = {f (1)} depends only on steps 1 and 2 of the algorithm before executing A layer . It follows thatPr(f (1) oe ALG) Ø 1 4 Pr(f (1) oe ALG|C 0 = {f (1)})= 1 4 E[|ALG fl C 0 ||C 0 = {f (1)}] Ø 1 4g(1 + log fl) E[|OPT(R \ R s ) fl C 0 ||C 0 = {f (1)}]= 1 4g(1 + log fl) . Since |OPT fl R k |AE8, we conclude in this case that E[|ALG fl R k |] Ø Pr(f (1) oe ALG) Ø 1 4g(1 + log fl) Ø 1 32g(1 + log fl) |OPT fl R k |.

C 4 E 5 |ALG-A j fl B j 6 .-

 456 i ™{r oe R \ R s : r ≤ f (2 j )} = R T (2 j ) fl R \ R s .This implies thatE[|ALG fl R k |] Ø 1 fl R T (2 j ) | Furthermore, if A j holds, then ----OPT(R \ R s ) fl j≠3 = |{f oe OPT fl R \ R s : f ≤ s(2q)}| Ø|{f oe OPT fl R \ R s : f ≤ f (2q)}| Ø q.

1 : 2 :

 12 fl) |OPT fl R k |,where the last inequality holds since |OPT fl R k |AE2 j+1 =1 6 q. By usingLemma 33 we conclude that the algorithm is O(g(1 + log fl)) ordinal-competitive.Algorithm 14 O(g(1 + fl)) probability-competitive algorithmInput: Matroid M(R, I, º) in random order r 1 ,r 2 ,...,r n . Let s ≥ Bin(n, 1/2) and compute OPT(R s )={s(1),...,s(¸)}, where s(1) º s(2) º•••ºs(¸). Let t ≥ Bin(n ≠ s, 1/2) and let F = {r s+1 ,...,r s+t } be the next t elements from R \ R s .3: Return ALG = A layer (M| R + s ,F fl R + s , OPT(R s ), º), where R + s = {r oe R \ R s : r oe OPT(R s + r)}.

  Proof of Theorem 4. By Lemma 22,C o v + (A) oe Sym

	3k≠|A| 6	and then we can apply
	Lemma 21. Therefore, the matrix Cov

+ (A) is positive semidefinite if and only

Table 6 .

 6

	Matroid Class	Previous guarantees			New algorithms
		(u,o,p competitive)		p-approx	ref.	forb.
	Transversal	o: 16 [32], 8 [68], e [64]			e	Alg. 3	1
	µ exch. gammoids	u: O(µ 2 )[ 68], eµ [64]		µ µ/(µ≠1)	Alg. 4	µ
	(type of hypermatching)
	Matching matroids	-				4	Alg. 5	2
	µ exch. matroid packings	-			µ µ/(µ≠1)	Alg. 5	µ
	Graphic	o: 16 [11], 3e [9], 2e [68]			4	Alg, 6	2
	Hypergraphic	-				4	Alg, 6	2
	k-sparse matroids	o: ke [96]			k k/(k≠1)	Alg. 7	k
	k-framed matroids	-			k k/(k≠1)	Alg. 7	k
	Semiplanar gammoids Laminar	-o: 177.77 [55] o: 3 Ô 3e ¥ 14.12 [56] p: 9.6 [79]	3	Ô	4 4/3 3 ¥ 5.196	Alg. 8 Alg. 9	4 3
	Uniform U (n, fl)	p: e [10]		1+O( 	log fl/fl) Alg. 10	-
		o: 1 + O( 	1/fl)
	Cographic	p: 3e [96]				-		-	-
	Regular, MFMC	o: 9e [33]				-		-	-

1: State-of-the-art competitive ratios for all known matroid classes, including our results.

  r t of the first t elements arriving. Abbreviate P t (•)=P r ( •|r t = r ú ,R t = Y, s). By Lemma 32, r ú oe OPT(R t ) and by the k-forbidden property, P t (r ú oe ALG) Ø P t (For all j oe{s +1,...,t≠ 1},r j

  1: ALG Ωÿ, s Ω Bin(n, p), B Õ Ωÿ. 2: for i = s +1 to n do

	3:

  Algorithm 8 for semiplanar gammoids. if r i oe OPT(R i ), Left OPT(Rs)+r i (r i ) " oe B and Right OPT(Rs)+r i (r i ) " oe B then ALG + r i , and B Ω B fi{Left OPT(Rs)+r i (r i ), Right OPT(Rs)+r i (r i )}

	Input: An semiplanar gammoid with a fixed semiplanar drawing
	1: ALG Ωÿ, s Ω Bin(n, p), 2: if s =0then
	3: ALG Ω{r 1 } 4: else B Ωÿ. 5: for i = s +1 to n do
	6:
	7: ALG Ω 8: Return ALG.
	Algorithm 9 for laminar matroids.
	Input: A laminar matroid with a fixed semiplanar drawing
	1: ALG Ωÿ, s Ω Bin(n, p), 2: if s =0then
	3: 4: else B Ωÿ. ALG Ω{r 1 }

  Algorithm 10 for uniform matroids. Input: A uniform matroid U (n, fl) with ground set R and rank fl.1: Get a sample of size n, independently and uniformly at random from [0, 1). Sort it from smallest to largest as t 1 <t 2 < ••• <t n . Thus t i is interpreted as the arrival time of r i .

2: ALG Ωÿ 3: for i =1ton do 4:

  With probability 1/2, set H = odd(|C|) or even(|C|) otherwise. 5: For each i oe H let T i Ωÿ.

• ≠ 1}. 3: Let B = {B 1 ,B 2 ,...,B Á(∆+|C|)/2 • Ë } where B i = t min{|C|,2 • i≠∆} j=max{0,2 • (i≠1)≠∆+1} C j . 4: 6: for each element in r oe R \ F do 7:

  layer which is g(1 + ¸) AE g(1 + fl) competitive, we get that

	Pr(f (j) oe ALG) Ø =	1 8 1 8	Pr(f (j) oe ALG|E) E[|ALG fl C h ||E] Ø	1 8g(1 + fl)	E[|OPT(R + s ) fl C h ||E]=	1 8g(1 + fl)	,

and we conclude that Algorithm 14 is O(g(1 + fl)) probability-competitive.

For every Á>0, there is an algorithm that computes a solution with cost at most (1 + Á)opt, where opt is the cost of the optimal solution in a minimization problem. The running time of the algorithm is polynomial in the input size.

In general, the SA and LS + hierarchies are incomparable, so (iii) does not follow directly from (ii). The linear counterpart of Lovász-Schrijver, the LS hierarchy, is weaker than SA and therefore the result follows in that case from (ii).

An independence system is a pair (R, I)whereR is finite, and I is a nonempty family of subsets of R that is closed under inclusion. The sets in I are called independent sets.

A matroid is an independence system (R, I) satisfying the next augmentation property: whenever X, Y oeI, and |X| < |Y |, there must be an element r oe Y \ X such that X + r oeI.

As e tA = {a 1 ,...,a k }™R is lexicographically larger than a set B = {b 1 ,...,b k }™R of the same size, with respect to the order º on A fi B if a i º b i for the first i on which a i and b i differ.

For particular classes of matroids, we may assume that M is known beforehand by the algorithm, or alternatively that it is discovered by the algorithm via an independence oracle that allows it to test any subset of revealed elements. In any case, it is a standard assumption that the algorithm at least know the number of elements n in the matroid.

A factor-critical graph is one such that H ≠ x admits a perfect matching for all x oe V (H). A 1-propeller is a graph having a leaf r, and a vertex c such that for every x oe V (H) ≠ c, H ≠ x admits a perfect matching.

An alternative way to understand this definition is to imagine that in the drawing nodes and arcs have positive area (they are circles and thick lines). A drawing of a path is any continuous nonself-intersecting curve drawn inside the union of all circles and thick lines associated to the nodes and arcs of P visiting them in the correct order. A collection of paths are mutually noncrossing if we can find drawings such that no pair of them intersects. Note that two noncrossing paths can still share arcs and nodes.

Thecontraction of M =(R, I)b yQ, M/Q, has ground set R ≠ Q and a set I is independent if fl(I fi Q) ≠ fl(Q)=|I|.

The restriction of M =(R, I)t oQ, M| Q , has ground set Q and a set I is independent if I oeI and I ™ Q.

This assumption can be removed by using standard arguments; we can set fl equal to twice the rank of the sampled part.

The original analysis uses half of n, but the analysis gets simpler if one uses Bin(n, 1/2) since one can assume that each element is in the sample with probability 1/2 independent of the rest.

A loop in a matroid is an element that belongs to no basis.

Acknowledgments

First of all, I'm really grateful to my advisors, Claire Mathieu and Jose Correa, for all your support, guidance and patience, for those inspiring conversations about research and life. I've learned a lot from you these years about how to do research, and I'm sure I will keep learning from you in the future. Thank you! I thank Christoph Dürr and Samuel Fiorini for carefully reviewing this work, and your helpful comments. I also thank to Rida Laraki, Nicole Megow, Tobias Mömke, Alantha Newman and Fernando Ordoñez for being part of the jury.

I had the chance to share with two very inspiring group of people, at Talgo ENS

assign(B, T), x C (i, I) ij oe{ 0, 1} for all j oe J and conf(I)=C i (x C (i, I)). In particular, from the symmetry breaking constraints it follows that L B (C i (x C (i, I))) Ø L B (C h (x)), since by Proposition 28 the vector x C (i, I) remains integral at h and in the same configuration than x. The function L B is strictly increasing, and therefore conf(I)=C i (x C (i, I)) Ø lex C h (x).

Observe that it is guaranteed by the algorithm that machine m is integral at the end of Phase 1. In the following, we prove that at the end of every iteration of Phase 1, the machines between other two that have been induced to be integral by using the decomposition are all fractionally scheduled according to the same configuration. In particular, it guarantees that the greedy approach of Phase 2 works. Lemma 30. Let ¸oe{ 1,...,|C|}. For every i oe M such that i ¸= max{i q :0AE q< ¸, i q < OE} <iAE i ¸and every q oe{1,...,s}, q joeJq y ij = m(q, C ¸).

Proof. Let i oe M be a machine such that i ¸<iAE i ¸. By Lemma 29,f o re v e r yK ™ J such that y ¸(i, K) ÿ > 0 it holds that conf(K) Ø lex C ¸, but we show next that they are all equalities. Suppose there exists K ™ J such that C t = conf(K) > lex C ¸for some t<. That would imply that i AE i t < OE, contradicting that i ¸<i . By Lemma 27, for every q oe{1,...,s} it holds that

Proof of Theorem 6. For every ¸oe{ 1,...,|C|}, let N ¸= {i oe M : i ¸<i<i ¸}. Observe that some of these sets could be equal to the ÿ. Thanks to Lemma 30, at the end of Phase 1 we obtain a solution y |C| satisfying every constraint of assign(B, T), it is integral for every machine in M \fi |C| ¸=1 N ¸and every machine in N ¸is fractionally scheduled according to configuration C ¸, for all ¸oe{1,...,|C|}. We now see how we construct a schedule with makespan at most -• T for the jobs that have not been scheduled in Phase 1, and using only the machines in M = fi

Left J be all the jobs that have not been scheduled in Phase 1. Consider the bipartite graph with nodes given by the jobs J on one side, and the other side are the set of nodes R = M ◊{1,...,s}. There is an edge between j oe J and (i, q) oeR if y |C| ij > 0 and j oe J q . We consider a transportation problem where the offer of every node in J is exactly 1, and the demand of a node (i, q) is equal to m(q, C ¸) if i oe N ¸. By construction the total offer equals to total demand and y |C| is a fractional solution to this problem. Therefore, since this is a feasible transportation problem, the integrality of the flow formulation implies that exists an integral solution and a way of implementing Phase 2.

Proof of Theorem 6

Chapter 5 Given ¸oe{1,...,|C|} with i ¸< OE, in Phase 2 we have that every machine i oe N is such that conf(K i )=C ¸= conf(K), where K i are the jobs scheduled to i in x lex , and K the jobs scheduled to i ¸. The partitioning of the jobs is --balanced, so we have that

since the load at machine i ¸is guaranteed to be at most T thanks to Phase 1. That concludes the proof.

Part II Online Optimization: Selection Problems

Chapter 6

that the set of selected elements is at all times independent 4 in the matroid. The objective of the algorithm is to return a set ALG as close as OPT as possible according to certain competitiveness metric.

Recall that the algorithm considered for the MSP have access to the elements in an online and uniformly at random fashion. We denote by r 1 the first element arriving, r 2 the second, and so on. In general, R t = {r 1 ,r 2 ,...,r t } is the set of elements arriving up to time t.

Measures of competitiveness: Ordinal MSP

Recall that an algorithm for the utility MSP returning a set ALG is -Ø 1 utilitycompetitive if

We introduce three measures of competitiveness for the ordinal MSP. Recall that the algorithm only learns ordinal information about the elements but it cannot access numerical weights. In this sense, they are closer to the classical secretary problem than the utility variant (for a discussion about this aspect in the original secretary problem, see [START_REF] Ferguson | Who Solved the Secretary Problem?[END_REF]). Since the weight function remains completely hidden for the algorithm, the first measure of competitiveness we consider is the following. An algorithm isordinalcompetitive if for every weight function w compatible with the value order, condition (6.1) holds. An equivalent characterization of competitiveness is obtained by the following lemma.

Lemma 33. An algorithm is -Ø 1 ordinal-competitive if and only if for every k oe

Proof. Consider anordinal-competitive algorithm returning a set ALG and let k oe [n]. Define the weight function w(r) = 1 if r oe R k and zero otherwise, which is compatible with the value order. Then,

2) holds. Then, for any compatible function w, and defining w(r n+1 ) := 0,

Chapter 6

measure is incomparable with the other measures. It is not hard to find fixed families of instances for which a given algorithm is almost 1 intersection-competitive but has unbounded utility/ordinal/probability-competitiveness. There are also examples achieving almost 1 ordinal-competitiveness but unbounded intersection-competitive ratio.

where in the last inequality we used that Á j < 1/8. By Chernoff bound on events U 2 and U 3 , we obtain

Putting all together, it follows that

Then, the algorithm is (1≠O(

Chapter 10

Algorithms for general matroids

In this section we provide algorithms for general matroids in the different competitiveness notions we consider in this work. We first show an O(1)-intersection competitive algorithm and then we proceed with ordinal/probability notions. Our algorithm for the intersection notion works as follows. We first sample s elements, where s is chosen appropriately later. After that, we select an element as long as it is part of the optimum of the subset of elements seen so far, and it preserves the independence of the current solution. Recall that we denote by R i = {r 1 ,r 2 ,...,r i } the first i elements seen by the algorithm.

Algorithm 11 Improving Greedy

Input: Matroid M(R, I) in random order r 1 ,r 2 ,...,r n , and a fixed integer s oe {1,...n}. The idea of only considering elements that belong to the current optimum is not new. Ma et al. [START_REF] Ma | The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems[END_REF] consider an algorithm that after sampling a fraction of the elements, selects an element as long as it belongs to the current offline optimum, and they prove this to be 9.6 utility-competitive (and the analysis holds for probability as well) for laminar matroids. The same algorithm was suggested by Babaioff et al. [START_REF] Babaioff | Matroids, secretary problems, and online mechanisms[END_REF], and they showed how this algorithm fails to be even constant utility-competitive. In contrast, we show this algorithm to be O(1) intersection-competitive.

Lemma 44. Let B = {r

, where H j denotes the j-th harmonic number.

Proof. For every i oe [n] if we condition the set R i to be some fixed set F oe

Therefore, by linearity of expectation we conclude that

Proof of Theorem 17. We study the competitiveness of the algorithm when the sample size is s, and then we optimize over this value to conclude the theorem. For any random ordering,

Furthermore, ALG fi (OPT \ R s ) ™ B, where B is the set defined in Lemma 44. Since the elements arrive in uniform random order, for r oe OPT we have that Pr(r/ oe R s )= (n ≠ s)/n =1≠ s/n. Therefore, the right hand side of the previous inequality is at least

This quantity is maximized in s = n/2. So, by assuming n even (which can be done by adding an extra dummy element if n is odd), and setting the algorithm for s = n/2, we obtain

The same holds if we modify the algorithm by choosing a random sample size of expected value n/2, that is, s ≥ Bin(n, 1/2).

Ordinal/Probability: Proof of Theorem 9

We introduce a variant of the MSP that helps us to leverage existing algorithms for the utility version of the MSP, in order to get competitive algorithms for the ordinal and probability variants. We need a concept similar to the aided sample-based MSP introduced by Feldman et al . [START_REF] Feldman | A Simple O (log log(rank)) -Competitive Algorithm for the Matroid Secretary Problem[END_REF].

In the Layered-MSP the input is a tuple (M,F,C,º) where M =( R, I, º) is a totally ordered matroid, C = {c 1 ,c 2 ,...,c k } is a finite set with C fl R = ÿ, º is a total order over R fi C with c 1 º c 2 º•••ºc k , and F is a random subset of R in which every element is present with probability 1/2. The set C defines a partition of R in the following way. We call C 0 = {r oe R : r º c 1 } the highest layer and We show in this section that TPA is Ω(fl)-competitive in the intersection, ordinal and probability measures. We first revisit the proof by [START_REF] Babaioff | Matroids, secretary problems, and online mechanisms[END_REF] for the O(log fl) utilitycompetitiveness of TPA.

Proof of Theorem 48. Let OPT = {f (1),...,f(fl)} be the optimal base such that w 1 >w 2 > ••• >w fl , where w i = w(f (i)) for each i oe{ 1,...,fl}. Suppose that f (1) / oe R s . Then, if the second non-loop element of the matroid is sampled and if • = 0, the element f (1) will be selected in the second phase of TPA. Hence Pr(f (1) oe ALG) Ø 1/4 • 1/(Álog flË +1)=Ω(1/ log fl).

Let B = {i oe{ 2,...,fl} : w i Ø w 1 /fl}, and let E i be the event where f (1) oe R s and w i /2 <T AE w i .F o r e a c h i oe B, we have log(w 1 /w i ) < log fl and therefore Pr(E i )=1 /2 • Pr(• = Álog(w 1 /w i )Ë)=Ω ( 1 / log fl). The random order assumption implies that in expectation (i ≠ 1)/2 Ø i/4 elements in {f (2),...,f(i)} are nonsampled, hence the expected rank of the matroid restricted to non-sampled elements of weight at least w i = w(f (i)) is Ω(i). Therefore, given i oe B and conditioned on E i , the algorithm selects Ω(i) elements of value at least w i /2. It follows that for each i oe B,

In addition, observe that the elements in OPT \{f (i):i oe B fi{1}} have total weight less than w 1 (fl ≠|B|≠1)/fl < w 1 , and therefore 2 q ioeBfi{1} w i Ø w(OPT). Putting all together, we have that the expected weight of the output is

We study in the following the competitiveness of TPA for the ordinal measures. Since probability is the strongest (Lemma 34), it is enough to check that TPA is Ω(fl) ordinal and intersection competitive. Let R = {r 1 ,...,r n } with n =2fl 3 . Consider the laminar family {R n/2 ,R}, where R n/2 = {r 1 ,...,r n/2 }, and take the laminar matroid (R, I) where a set I oeI is independent if |I fl R n/2 |AE1 and |I|AEfl. In particular, the matroid rank is fl. Given Á>0, the weights are given by w(r i )=8≠ Ái for i oe{1,...n/2}, and w(r i )=7≠ Ái for i oe{n/2+1,...,n}.

Observe that the optimal basis is given by OPT = {r 1 ,r n/2+1 ,...,r n/2+fl≠1 }.I fw e run TPA on this instance, with probability p =1≠ 2 ≠n/2 the top weight w ú in the sample is from R n/2 , and thus, 7 <w ú < 8. Let E be this event. No matter the value of T , the algorithm always select at most fl elements in the non-sampled part, and 10.2. Comparison between ordinal measures Chapter 10 therefore

Conditional on E, we have that either T>7o rT<4. In the first case, TPA will select at most one element, which would come from R n/2 , and so |ALG fl OPT|AE1. Otherwise, if T<4, the algorithm will select at most one element from R n/2 and at most the first fl non-sampled elements from R \ R n/2 . The expected number of elements in {r n/2+1 ,...,r n/2+fl≠1 } appearing in {r s+1 ,...,r s+fl }, that is the first fl elements appearing after the sample, is (fl≠1

is upper bounded by 2, and therefore E[|ALG fl OPT|] AE 3. The discussion above implies as well that E[|ALG fl R n/2+fl≠1 |] AE 3, and then TPA is Ω(fl) intersection and ordinal competitive. The conclusion for the ordinal case follows by using the characterization for ordinal competitiveness in Lemma 33.

Ordinal and intersection notions. We show in the following that there is no competitiveness dominance between the intersection and the ordinal notions. Let m and M be two positive integers. Consider R = {r 1 ,r 2 ,...,r (M +1)m } and let L be the partition of R given by

In particular, we consider the partition matroid M m,M =( R, I) where I oeIif |I fl L|AE1f o re v e r yL oeL . The matroid rank is m + M . The algorithm we choose is greedy: we initialize ALG Ωÿ , and when an element r arrives it is selected if ALG + r oeI. Proposition 49. Suppose M Ø m 2 . Then, the greedy algorithm over instance M m,M is (1 + 1/m) ordinal-competitive and Ω(m) intersection-competitive.

In fact, the ordinal competitiveness holds no matter what the value of M is. We adjust the value of M in order to get a poor competitiveness for the intersection notion.

Proof of Proposition 49. The optimal base of M m,M is the highest element of each part in L, that is, OPT = {r 1 ,r 2 ,...,r m }fi{r jm+1 : j oe{1,...,M}}.

In particular, we have

..,m}, m + j if k oe{jm +1,...,(j +1)m} and j oe{1,...,M}.

Observe that an element r oe Q, with Q oeL , is selected by the algorithm if and only if r is the first element of Q that arrives. Therefore, Pr(r i oe ALG) = 1 if i oe{1,...,m} and Pr(r i oe ALG) = 1/m if i oe{m +1,...,(m +1)m}. It follows that

Thus, when k oe{ 1,...,m}, we have

and thus the greedy algorithm is (1 + 1/m) ordinal-competitive for M m,M . In the first inequality we used that "(x)=(m ≠ x)/(m

and so the algorithm is at least Ω(m) intersection-competitive.

Although not mentioned explicitly in the proof, since Pr(r i oe ALG) = 1/m for i>mit follows that the algorithm is m probability competitive for M m,M , and for every M . In the following we construct an instance for which the intersection competitiveness is close to 1, but the ordinal competitiveness is poor. Let m be a positive integer and R = {r Proof. An element r oe Q, with Q oeL, is selected by the algorithm if and only if r is the first element of Q that arrives. Therefore, Pr(r i oe ALG) = 1/m if i oe{1,...,m} and Pr(r i oe ALG) = 1 if i oe{m+1,...,2m≠1}. Since OPT = {r 1 ,r m+1 ,...,r 2m≠1 },

hence the algorithm is Ω(m) ordinal-competitive. Finally, we have

and so the greedy algorithm is (1 + 1/m) intersection-competitive over N m .

Concluding Remarks

In this thesis we studied applications to scheduling and online selection problem through general frameworks. For scheduling, we considered relaxations obtained from performing lift & project steps. We proved that if we apply these techniques directly over the assignment formulations known for the problem, then they fail to reduce the integrality gap even when the size of the relaxations is exponentially large on the input size. All the relaxations above mentioned are symmetric with respect to machine permutations, so we go back one step in our approach, and before applying lift & project we break the machine symmetries. It turns out that in this way we get arbitrarily close to one integrality gaps, and the relaxations are of polynomial size. We summarize below the main message of this part.

Lift & project methods are powerful tools for obtaining relaxations with good integrality gaps, but they have be applied to the right model. Symmetries are harmful, so, we suggest an operator that break symmetires, lift & project.

We believe that understanding the interaction between the action of a group over a formulation and its effect at the moment of using hierarchies should be understood better. In particular, it opens the way to combine techniques that look for symmetries in a formulation (they are not always evidently present as in the scheduling problem), break them and then strengthening the model.

In the second part of the thesis we considered the matroid secretary problem under a strong notion of competitiveness. We provide a general tool that allows to obtain O(1) competitiveness for many matroid families. Furthermore, we obtained probability competitiveness for general matroids, and in a weaker notion we matched the best known for the classic weighted secretary problem.

We develop a framework to analize algorithms by studying the size of the forbidden sets and the competitiveness attained is a function of this parameter. The smaller the size of the forbidden sets, the better the competitiveness.

In particular, the existence of an algorithm with forbidden sets of size one for every matroid would prove the strong MSP conjecture. It is an interesting question whether this approach can be applied to obtain good competitive ratios in non-matroidal settings. In our analysis we require an optimality condition that is necessary for matroids, but we do not know if it is sufficient.