Rodrick Wallace
email: wallace@nyspi.columbia.edu

PASSENGER CROWDING AND 'TRAFFIC JAM' INSTABILITIES OF V2I PUBLIC TRANSIT SYSTEMS

According to the Data Rate Theorem, if the rate at which control information can be provided to an unstable system is below a critical limit defined by the rate at which the system generates 'topological information', there is no coding strategy, no timing strategy, no control scheme of any form, that can provide stability. For an urban bus system embedded in a larger traffic stream, no matter what V2I headway manipulations are applied, there will always be a critical passenger density per vehicle that creates the public transit system equivalents of a traffic jam such as 'bunching', long headways, and extended on/off delays. An extension of the model finds that V2I systems in general, as a consequence their inherently cognitive nature, may be subject to multiple phase transitions in which passenger density becomes convoluted with traffic density. The only solution to cascading dysfunction under such conditions is to provide adequate numbers of passenger vehicles. In sum, no communications or other 'tech fix' can mitigate inadequate levels of public transportation service.

... [T]he negative impacts of crowding on the reliability of public transport services should be carefully analysed... [START_REF] Tirachini | Crowding in public transport systems: effects on users, operation and implications for the estimation of demand[END_REF]

I. INTRODUCTION

Urban public transportation, particularly bus service, necessarily interacts with a more general traffic flow on congested roadways that may include trucks, passenger cars, taxis, and emergency vehicles, forming a complex transit ecosystem that is inherently difficult to manage (e.g., [START_REF] Chiabaut | Evaluation of a multimodal urban arterial: the passenger macroscopic fundamental diagram[END_REF][START_REF] Geroliminis | A threedimensional macroscopic fundamental diagram for mixed bimodel urban networks[END_REF]. Recent advances make it possible for an embedding regulatory infrastructure -the 'I' of the title -to communicate with bus and light rail vehicles in real time -the 'V' of the title. Such V2I systems fall under the necessary constraints of the asymptotic limit theorems of control and information theories. Indeed, public transit has been the subject of much mathematical modeling, and the effects of passenger crowding on service continue to receive central focus (e.g., [START_REF] Tirachini | Crowding in public transport systems: effects on users, operation and implications for the estimation of demand[END_REF][START_REF] Tirachini | Multimodal pricing and optimal design of urban public transport: the interplay between traffic congestion and bus crowding[END_REF]Ivanchev et al. 2014, and references therein). [START_REF] Tirachini | Crowding in public transport systems: effects on users, operation and implications for the estimation of demand[END_REF] describe the classic passenger crowding conundrum as follows:

When buses and trains circulate with a low number of passengers, everyone is able to find a seat, transfer of passengers at stations is smooth, and passenger-related disruptions that impose unexpected delays are rare. As the number of passengers increases, a threshold is reached at which not everyone is able to find a seat and some users need to stand inside vehicles. In turn, this may make more difficult the movement of other passengers that need to board to or alight from a vehicle: therefore, riding time increases due to friction or crowding effects among passengers... [Study] finds that dwell time increases with the square of the number of standees inside a bus, multiplied by the total number of passengers boarding and alighting at a bus stop... A formal treatment [finds]... that average waiting time is related not only to the headway (the inverse of bus frequency) but also to the occupancy rate or crowding level in an additive or multiplicative way... A second effect of high occupancy levels on waiting times is the possibility of triggering bus bunching [by a number of mechanisms]... The seduction of real-time V2I systems using GPS positioning of individual transit vehicles is the assumption that sufficient control of vehicle headway will smooth out passenger and vehicle congestion, avoiding bunching, mitigating overcrowding, and so on. Here, via the Data Rate Theorem that links control and information theories, we show that assumption to be an illusion, and that there will always be a critical value of passenger density at which a public transit system suffers the functional equivalent of a massive traffic jam.

The phenomenological model we develop will, in fact, link larger-scale vehicles/mile traffic density with passengers/bus density.

The underlying conceit of V2I systems is that the infrastructure can control individual vehicles to regulate traffic flow. An essential constraint on such systems, however, is that they are inherently unstable, and require a constant flow of control information to stay on the road or, if on a track, to avoid collisions. Aircraft can be designed to be inherently stable, in the sense that, for a short time at least, they can be allowed to proceed 'hands off', as long as the center of pressure of the vehicle is behind the center of gravity. Then small perturbations from steady state rapidly die out. Ground vehicles in heavy traffic on twisting roads must, by contrast, always be under real-time direction by a cognitive entity.

The first stage of modeling is a linear expansion around a nonequilibrium steady state in which control information is sufficient to keep the system 'on track'.

II. THE DATA RATE THEOREM FOR TRAFFIC FLOW

The Data Rate Theorem [START_REF] Nair | Feedback control under data rate constraints: an overview[END_REF]) establishes the minimum rate at which externally-supplied control information must be provided for an inherently unstable system to maintain stability. Given the linear expansion near a nonequilibrium steady state, an n-dimensional vector of system parameters at time t, x t , determines the state at time t + 1 according to the model of figure 1, so that

x t+1 = Ax t + Bu t + W t (1)
where A, B are fixed n × n matrices, u t is the vector of control information, and W t is an n-dimensional vector of white noise. The Data Rate Theorem (DRT) under such conditions states that the minimum control information rate H is determined by the relation

H > log[| det[A m |] ≡ a 0 (2)
where, for m ≤ n, A m is the subcomponent of A having eigenvalues ≥ 1. The right hand side of Eq.( 2) is interpreted as the rate at which the system generates 'topological information'. The proof of Eq.( 2) is not particularly straightforward [START_REF] Nair | Feedback control under data rate constraints: an overview[END_REF], and the Mathematical Appendix uses the Rate Distortion Theorem (RDT) to derive a more general version of the DRT. For a simple traffic flow system on a fixed highway network, the source of 'topological information' is the linear vehicle density ρ. The 'fundamental diagram' of traffic flow studies relates the total vehicle flow to the linear vehicle density, shown in figure 2 for a Rome street [START_REF] Blandin | A general phase transition model for vehicular traffic[END_REF]. Behavior shifts from smooth flow to traffic jams at about 40 vehicles/mile, at which value the system 'crystallizes' out into discrete 'chunks' that interfere with each other [START_REF] Kerner | Phase transitions in traffic flow on multilane roads[END_REF][START_REF] Wallace | Canonical instabilities of autonomous vehicle systems[END_REF]. Similar dynamics can be expected from 'macroscopic passenger fundamental diagrams' that examine multimodal travel networks, but focusing on passenger rather than vehicle flow [START_REF] Geroliminis | A threedimensional macroscopic fundamental diagram for mixed bimodel urban networks[END_REF][START_REF] Chiabaut | Evaluation of a multimodal urban arterial: the passenger macroscopic fundamental diagram[END_REF].

Given ρ as the critical traffic density parameter, we can extend Eq.( 2) as

H(ρ) > f (ρ)a 0 (3)
where a 0 is a road network constant and f (ρ) is a positive, monotonically increasing function. The Mathematical Appendix uses a Black-Scholes model to approximate the 'cost' of H as a function of the 'investment' ρ. Surprisingly (or not) the first approximation is linear, i.e. H ≈ κ 1 ρ + κ 2 . Taking f (ρ) to similar order, so that

f (ρ) ≈ κ 3 ρ + κ 4 (4)
the limit condition for stability becomes

T ≡ κ 1 ρ + κ 2 κ 3 ρ + κ 4 > a 0 ( 5
)
FIG. 3: The horizontal line represents the critical limit a0. If κ2/κ4 κ1/κ3, at some intermediate value of linear traffic density ρ, the temperature analog T ≡ (κ1ρ + κ2)/(κ3ρ + κ4) falls below that limit, traffic flow becomes 'supercooled', and traffic jams become increasingly probable.

For ρ = 0, the stability condition is κ 2 /κ 4 > a 0 . At large ρ this becomes κ 1 /κ 2 > a 0 . If κ 2 /κ 4 κ 1 /κ 2 , the stability condition may be violated at high traffic densities, and instability becomes manifest, as at the higher ranges of figure 2. See figure 3.

III. MULTIMODAL TRANSPORT SYSTEMS

For buses embedded in a larger traffic stream there are two critical densities that must interact: vehicles per linear mile and passengers per bus. There is not, then, a simple 'density' index, but rather a density matrix ρ

ρ 11 ρ 12 ρ 21 ρ 22
where ρ 11 is the number of passengers per bus, ρ 22 vehicles per mile, and the off-diagonal terms are measures of interaction between these since, at the least, buses are part of the traffic stream.

One might extend the model to higher dimensions by including, for example, passenger densities of a subway or light rail system feeding into a transit 'hot spot'.

Can there still be a single scalar 'ρ' under such complex circumstances so that the conditions of figure 3 apply? An n × n matrix ρ has n invariants r i , i = 1..n, that remain fixed when 'principal component analysis' transformations are applied to data, and these can be used to construct an invariant scalar measure, using the polynomial relation

p(λ) = det(ρ -λI) = λ n + r 1 λ n-1 + ... + r n-1 λ + r n (6)
det is the determinant, λ is a parameter and I the n×n identidy matrix. The invariants are the coefficients of λ in p(λ), normalized so that the coefficient of λ n is 1.

For a 2 × 2 matrix the invariants are the determinant and the trace. It then becomes possible to define a composite scalar index r as a monotonic increasing function of these invariants

r = f (T r[ρ], det[ρ]) (7)
The simplest example would be Again, an n×n matrix will have n such invariants from which a scalar index r can be constructed. Typically, the first invariant will be the trace and the last ± the determinant.

r = α 1 T r[ρ] + α 2 | det[ρ]| (

IV. MULTIPLE PHASES OF V2I DYSFUNCTION

The DRT argument implies a raised probability of a transition between stable and unstable behavior if the temperature analog T from Eq.( 5) falls below a critical value, as in figure 3. [START_REF] Kerner | Phase transitions in traffic flow on multilane roads[END_REF], however, argue that traffic flow can be subject to more than two phases. We can recover something similar for V2I transit systems driven by passenger density via a 'cognitive paradigm' similar to that used by [START_REF] Atlan | Immune information, selforganization, and meaning[END_REF] in their study of the immune system. They view a system as cognitive if it must compare incoming signals with a learned or inherited picture of the world, then actively choosing a response from a larger set of those possible to it. V2I systems are clearly cognitive in that sense. Such choice, however, implies the existence of an information source, since it reduces uncertainty in a formal way. See [START_REF] Wallace | Consciousness, crosstalk and the mereological fallacy: an evolutionary perspective[END_REF][START_REF] Wallace | An Information Approach to Mitochondrial Dysfunction: Extending Swerdlow's hypothesis[END_REF] for details of the argument.

Given the 'dual' information source associated with the inherently unstable cognitive V2I public transit system, an equivalence class algebra can be constructed by choosing different system origin states and defining the equivalence of subsequent states at a later time by the existence of a high probability path connecting them to the same origin state. Disjoint partition by equivalence class, analogous to orbit equivalence classes in dynamical systems, defines a symmetry groupoid associated with the cognitive process [START_REF] Wallace | Consciousness, crosstalk and the mereological fallacy: an evolutionary perspective[END_REF]. Groupoids are generalizations of group symmetries in which there is not necessarily a product defined for each possible element pair [START_REF] Weinstein | Groupoids: unifying internal and external symmetry[END_REF], for example in the disjoint union of different groups.

The equivalence classes across possible origin states define a set of information sources dual to different cognitive states available to the inherently unstable V2I system. These create a large groupoid, with each orbit corresponding to a transitive groupoid whose disjoint union is the full groupoid. Each subgroupoid is associated with its own dual information source, and larger groupoids must have richer dual information sources than smaller.

Let X Gi be the V2I system's dual information source associated with groupoid element G i . Given the argument leading to Eqs.(5-7), we construct a Morse Function [START_REF] Pettini | Geometry and Topology in Hamiltonian Dynamics[END_REF] as follows.

Let H(X Gi ) ≡ H Gi be the Shannon uncertainty of the information source associated with the groupoid element G i . We can define a Boltzmann-like pseudoprobability as

P [H Gi ] ≡ exp[-H Gi /T ] j exp[-H Gj /T ] (9)
where the sum is over the different possible cognitive modes of the full system. A 'free energy' Morse Function F can then be defined as

exp[-F/T ] ≡ j exp[-H Gj /T ] ( 10
)
As a consequence of the inherent groupoid structure, we can now apply an extension of Landau's version of phase transition [START_REF] Pettini | Geometry and Topology in Hamiltonian Dynamics[END_REF]. Landau saw spontaneous symmetry breaking as representing phase change in physical systems, with the higher energies available at higher temperatures being more symmetric. The shift between symmetries is highly punctuated in the temperature index, here the 'temperature' analog of Eq.( 5), in terms of the scalar construct r, but in the context of groupoid rather than group symmetries. Usually, for physical systems, there are only a few phases possible. [START_REF] Kerner | Phase transitions in traffic flow on multilane roads[END_REF] recognize three phases in ordinary traffic flow, but V2I transit systems embedded in a larger traffic network may have relatively complex stages of dysfunction, with highly punctuated transitions between them as passenger density increases.

V. DISCUSSION AND CONCLUSIONS

The essential content of the Data Rate Theorem [START_REF] Nair | Feedback control under data rate constraints: an overview[END_REF]) is that, if H, the rate at which control information can be provided to an unstable system is below the critical limit defined by the rate at which the system generates 'topological information', there is no coding strategy, no timing strategy, no control scheme of any form, that can provide stability. Generalization, based on the inherently cognitive nature of V2I systems, suggests that there may be a sequence of stages of increasing dysfunction for public transit under the burden of rising per-bus passenger densities.

In our development, for a bus system necessarily embedded in a larger traffic flow, no matter what V2I headway manipulations are applied, there will always be a critical per-bus passenger density that creates the public transit equivalent of a traffic jam; bunching, long headways, extended on/off delays, and so on. The arguments of [START_REF] Kerner | Phase transitions in traffic flow on multilane roads[END_REF] and [START_REF] Wallace | Canonical instabilities of autonomous vehicle systems[END_REF] on phase transitions carry over into public transit systems whose dynamics are driven by multiple density measures and their interaction. For a given route at a fixed time, there should be a 'passenger macroscopic fundamental diagram' much like figure 2 showing passengers/hour as a function of passengers/vehicle [START_REF] Chiabaut | Evaluation of a multimodal urban arterial: the passenger macroscopic fundamental diagram[END_REF][START_REF] Geroliminis | A threedimensional macroscopic fundamental diagram for mixed bimodel urban networks[END_REF].

The essential solution to traffic jam analogs in public transportation systems is to provide adequate numbers of vehicles so that critical passenger densities are not exceeded.

In sum, there can be no tech fix for inadequate service.

VI. MATHEMATICAL APPENDIX

A. An RDT approach to the DRT

The RDT asks how much a signal can be compressed and have average distortion, according to an appropriate measure, less than some predetermined limit D. The result is an expression for the minimum necessary channel capacity, R, as a function of D. See [START_REF] Cover | Elements of Information Theory[END_REF] for details. Different channels have different expressions. For the Gaussian channel under the squared distortion measure,

R(D) = 1 2 log[ σ 2 D ] D < σ 2 R(D) = 0 D ≥ σ 2 (11)
where σ 2 is the variance of channel noise having zero mean.

Our concern is how a control signal u t is expressed in the system response x t+1 . We suppose it possible to deterministically retranslate an observed sequence of system outputs x 1 , x 2 , x 3 , ... into a sequence of possible control signals û0 , û1 , ... and to compare that sequence with the original control sequence u 0 , u 1 , ..., with the difference between them having a particular value under the chosen distortion measure, and hence an observed average distortion.

The correspondence expansion is as follows. [START_REF] Feynman | Lectures on Computation[END_REF], expanding on ideas of Bennett, identifies information as a form of free energy. Thus R(D), the minimum channel capacity necessary for average distortion D, is also a free energy measure, and we may define an entropy S as

S ≡ R(D) -DdR/dD (12)
For a Gaussian channel under the squared distortion measure,

S = 1/2 log[σ 2 /D] + 1/2 (13)
Other channels will have different expressions.

The simplest dynamics of such a system are given by a nonequilibrium Onsager equation in the gradient of S, (de Groot and Mazur 1984) so that

dD/dt = -µdS/dD = µ 2D (14)
By inspection,

D(t) = √ µt (15)
which is the classic outcome of the diffusion equation.

For the 'natural' channel having R(D) ∝ 1/D, D(t) ∝ the cube root of t. This correspondence reduction allows an expansion to more complicated systems, in particular, to the control system of figure 1.

Let H be the rate at which control information is fed into an inherently unstable control system, in the presence of a further source of control system noise β, in addition to the channel noise defined by σ 2 . The simplest generalization of Eq.( 14), for a Gaussian channel, is the stochastic differential equation

dD t = [ µ 2D t -F (H)]dt + βD t dW t (16)
where dW t represents white noise and F (H) ≥ 0 is a monotonically increasing function. This equation has the nonequilibrium steady state expectation

D nss = µ 2F (H) (17)
measuring the average distortion between what the control system wants and what it gets. In a sense, this is a kind of converse to the famous radar equation which states that a returned signal will be proportional to the inverse fourth power of the distance between the transmitter and the target. But there is an even deeper result to be found.

Applying the Ito chain rule to Eq.(15) [START_REF] Protter | Stochastic Integration and Differential Equations[END_REF][START_REF] Khashminskii | Stochastic Stability of Differential Equations[END_REF], it is possible to calculate the expected variance in the distortion as E(D 2 t ) -(E(D t )) 2 . But application of the Ito rule to D 2 t shows that no real number solution for its expectation is possible unless the discriminant of the resulting quadratic equation is ≥ 0, so that a necessary condition for stability is

F (H) ≥ β √ µ H ≥ F -1 (β √ µ) (18)
where the second expression follows from the monotonicity of F . As a consequence of the correspondence reduction leading to Eq.( 15), we have generalized the DRT of Eq.( 2). Different 'control channels', with different forms of R(D), will give different detailed expressions for the rate of generation of 'topological information' by an inherently unstable system.

B. A Black-Scholes model

Take H(ρ) as the control information rate 'cost' of stability at the level of crowding ρ. What is the mathematical form of H(ρ) under conditions of volatility i.e., variability in ρ proportional to it? Let

dρ t = g(t, ρ t )dt + bρ t dW t ( 19
)
where dW t is taken as white noise and the function g(t, ρ) will 'fall out' of the calculation on the assumption of certain regularities.

Let H(ρ t , t) be the minimum needed incoming rate of control information under the Data Rate Theorem, and expand in ρ using the Ito chain rule [START_REF] Protter | Stochastic Integration and Differential Equations[END_REF]) Since H is an information index, it is a kind of free energy in the sense of [START_REF] Feynman | Lectures on Computation[END_REF] and L is a classic entropy measure.

dH t =
Heuristically, replacing dX with ∆X in these expressions and applying Eq.( 20), ∆L = (-∂H/∂t -1 2 b 2 ρ 2 ∂ 2 H/∂ρ 2 )∆t ( 22)

As in the classical Black-Scholes model [START_REF] Black | The pricing of options and corporate liabilities[END_REF], the terms in g and dW t 'cancel out', and the effects of noise are subsumed into the Ito correction factor, a regularity assumption making this an exactly solvable but highly approximate model.

The conventional Black-Scholes calculation takes ∆L/∆T ∝ L. Here, at nonequilibrium steady state, we assume ∆L/∆t = ∂H/∂t = 0, so that

- 1 2 b 2 ρ 2 ∂ 2 H/∂ρ 2 = 0 (23)
By inspection,

H = κ 1 ρ + κ 2 (24)
where the κ i are nonnegative constants.

FIG. 1 :

 1 FIG.1:A linear expansion near a nonequilibrium steady state of an inherently unstable control system, for which xt+1 = Axt + But + Wt. A, B are square matrices, xt the vector of system parameters at time t, ut the control vector at time t, and Wt a white noise vector. The Data Rate Theorem states that the minimum rate at which control information must be provided for system stability isH > log[| det[A m |],where A m is the subcomponent of A having eigenvalues ≥ 1.

  8) for positive α i . Recall that, for n = 2, Tr[ρ] = ρ 11 + ρ 22 and det[ρ] = ρ 11 ρ 22 -ρ 12 ρ 21 .

  [∂H/∂t + g(ρ t , t)∂H/∂ρ + 1 2 b 2 ρ 2 t ∂ 2 H/∂ρ 2 ]dt +[bρ t ∂H/∂ρ]dW t (20)Define a quantity L as a Legendre transform of the rate H by convention having the form

	L = -H + ρ∂H/∂ρ	(21)


Approximability and exact resolution of the Multidimensional Binary Vector Assignment problem

LIRMM, Université Montpellier 2, France {marin.bougeret,guillerme.duvillie,rodolphe.giroudeau}@lirmm.fr Abstract. In this paper we consider the multidimensional binary vector assignment problem. An input of this problem is dened by m disjoint sets V1 , V 2 , . . . , V m , each composed of n binary vectors of size p. An output is a set of n disjoint m-tuples of vectors, where each m-tuple is obtained by picking one vector from each set V i . To each m-tuple we associate a p dimensional vector by applying the bit-wise AND operation on the m vectors of the tuple. The objective is to minimize the total number of zeros in these n vectors. We denote this problem by min 0, and the restriction of this problem where every vector has at most c zeros by (min 0) #0≤c . (min 0) #0≤2 was only known to be APX-complete, even for m = 3 [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF]. We show that, assuming the unique games conjecture, it is NP-hard to (n -ε)-approximate (min 0) #0≤1 for any xed n and ε. This result is tight as any solution is a n-approximation. We also prove without assuming UGC that (min 0) #0≤1 is APX-complete even for n = 2, and we provide an example of n -f (n, m)-approximation algorithm for min 0. Finally, we show that (min 0) #0≤1 is polynomialtime solvable for xed m (which cannot be extended to (min 0) #0≤2 according to [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF]).

Introduction 1.Problem denition

In this paper we consider the multidimensional binary vector assignment problem denoted by min 0. An input of this problem (see Figure 1) is described by m disjoint sets V 1 , . . . , V m , each set V i containing n binary p-dimensional vectors. For any j ∈ [n] 1 , and any i ∈ [m], the j th vector of set V i is denoted v i j , and for any k ∈ [p], the k th coordinate of v i j is denoted v i j [k]. The output of the problem consists in a set S of n disjoint stacks. A stack s = (v s 1 , . . . , v s m ) is an m -tuple of vectors such that v s i ∈ V i , for any i ∈ [m]. Two stacks s 1 and s 2 are disjoint if and only if no vector belongs to s 1 and s 2 .

We now introduce the operator ∧ which assigns to a pair of vectors (u, v) the vector given by u ∧ v = (u [START_REF] Alimonti | Some APX-completeness results for cubic graphs[END_REF] ∧ v [START_REF] Alimonti | Some APX-completeness results for cubic graphs[END_REF], u [START_REF] Ausiello | Reductions, completeness and the hardness of approximability[END_REF] ∧ v [START_REF] Ausiello | Reductions, completeness and the hardness of approximability[END_REF], . . . , u[p] ∧ v[p]). We associate to each stack s a unique vector given by v s = i∈[m] v s i .

The cost of a vector v is dened as the number of zeros in it. More formally

if v is p-dimensional, c(v) = p -k∈[p] v[k].
We extend this denition to a set of stacks S = {s 1 , . . . , s n } as follows : c(S) = s∈S c(v s ).

The objective is then to nd a set S of n disjoint stacks minimizing the total number of zeros. This leads us to the following denition of the problem:

Optimization Problem 1 min 0

Input

m sets of n p-dimensional binary vectors.

Output A set S of n disjoint stacks minimizing c(S).

Throughout this paper, we denote (min 0) #0≤c the restriction of min 0 where the number of zeros per vector is upper bounded by c.

Related work

The dual version of the problem called max 1 (where the objective is to maximize the total number of 1 in the created stacks) has been introduced by Reda et al. in [START_REF] Reda | Maximizing the functional yield of wafer-towafer 3-d integration[END_REF] as the yield maximization problem in Wafer-to-Wafer 3-D Integration technology. They prove the NP-completeness of max 1 and provide heuristics without approximation guarantee. In [START_REF] Duvillié | On the complexity of wafer-to-wafer integration[END_REF] we proved that, even for n = 2, for any ε > 0, max 1 is O(m 1-ε ) and O(p 1-ε ) inapproximable unless P = NP.

We also provide an ILP formulation proving that max 1 (and thus min 0) is FPT2 when parameterized by p.

We introduced min 0 in [START_REF] Dokka | Approximation algorithms for the wafer to wafer integration problem[END_REF] where we provide in particular 4

3 -approximation algorithm for m = 3. In [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF], authors focus on a generalization of min 0, called Multi Dimensional Vector Assignment, where vectors are not necessary binary vectors. They extend the approximation algorithm of [START_REF] Dokka | Approximation algorithms for the wafer to wafer integration problem[END_REF] to get a f (m)-approximation algorithm for arbitrary m. They also prove the APXcompleteness of the (min 0) #0≤2 for m = 3. This result was the only known inapproximability result for min 0.

Contribution

In section 2 we study the approximability of min 0. Our main result in this section is to prove that assuming UGC, it is NP-hard to (n -ε)-approximate (min 0) #0≤1 (and thus min 0) for any xed n ≥ 2, ∀ε > 0. This result is tight as any solution is a n-approximation.

Notice that this improves the only existing negative result for min 0, which was the APX-hardness of [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF] (implying only no-PTAS).

We also show how this reduction can be used to obtain the APX-hardness for (min 0) #0≤1 for n = 2 unless P = NP, which is weaker negative result, but does not require UGC. We then give an example n -f (n, m) approximation algorithm for the general problem min 0.

In section 3, we consider the exact resolution of min 0 (and max 1). We only focus on what we will call sparse instances, i.e. instances of (min 0) #0≤1 .

Indeed, recall that authors of [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF] show that (min 0) #0≤2 is APX-complete even for m = 3, implying that (min 0) #0≤2 cannot be polynomial-time solvable for xed m unless P = NP.

(g(x, S))| ≤ β|Opt(f (x))- m 2 (S)| then (f, g) is an L-reduction. In following, Π 1 L-reduces to Π 2 is noted Π 1 < L Π 2 .
Gap reduction We briey recall the denition of such a reduction, as presented in [START_REF] Ausiello | Reductions, completeness and the hardness of approximability[END_REF] by Ausiello et al.

Denition 2. Let Π dec be a decision problem and Π opt a minimization problem. Let f be a polynomial-time computable function that given any instance x of Π dec associates an instance f (x) of Π opt . If there exists two function a and r such that:

1. x is a YES-instance ⇒ Opt(f (x)) ≤ a(x) 2. x is a NO-instance ⇒ Opt(f (x)) ≥ r(x)a(x)
then f is a r(x)-Gap reduction.

2.2 Inapproximability results for (min 0) #0≤1

From now we suppose that ∀k ∈ [p], ∃i, ∃j such that v i j [k] = 0. In other words, for any solution S and ∀k, there exists a stack s such that v s [k] = 0. Otherwise, we simply remove such a coordinate from every vector of every set, and decrease p by one. Since this coordinate would be set to 1 in all the stacks of all solutions, such a preprocessing preserves approximation ratios and exact results.

In a rst time, we dene the following polynomial-time computable function f which associates an instance of (min 0) #0≤1 to any k-uniform hypergraph, i.e. an hypergraph G = (U, E) such that every hyperedges of E contains exactly k distinct elements of U .

Denition of f

We consider a k-uniform hypergraph G = (U, E). We call f the polynomial-time computable function that creates an instance of (min 0) #0≤1 from a G as follows.

1. We set m = |E|, n = k and p = |U |. 2. For each hyperedge e = {u 1 , u 2 , . . . , u k } ∈ E, we create the set V e containing k vectors {v e j , j ∈ [k]}, where for all j ∈ [k], v e j [u j ] = 0 and v e j [l] = 1 for l = u j . We say that a vector v represents u ∈ U i v[u] = 0 and v[l = u] = 1
(and thus vector v e j represents u j ).

An example of this construction is given in Figure 2.

a b c d V a V b V c V d 1

Output

Distinguish between the following cases:

YES Case there exist k disjoint subsets U 1 , U 2 , . . . , U k ⊆ U , satisfying |U i | ≥ 1-ε k |U |
and such that every hyperedge contains at most one vertex from each U i . NO Case every vertex cover has size at least

(1 -δ)|U |.
It is shown in [START_REF] Bansal | Inapproximability of hypergraph vertex cover and applications to scheduling problems[END_REF] that, assuming UGC, this problem is NP-complete.

Theorem 1. For any xed n ≥ 2, for any constants ε, δ > 0, there exists a n-nδ 1+nε -Gap reduction from Almost Ek Vertex Cover to (min 0) #0≤1 . Consequently, under UGC, for any xed n (min 0) #0≤1 is NP-hard to approximate within a factor (n -ε ) for any ε > 0.

Proof. We consider an instance I of Almost Ek Vertex Cover dened by two positive constants δ and , an integer k and a k-regular hypergraph G = (U, E).

We use the function f previously dened to construct an instance f (I) of min 0. Let us now prove that if I is a positive instance, f (I) admits a solution S of cost c(S) < (1 + nε)|U |, and otherwise any solution

S of f (I) has cost c (S) ≥ n(1 -δ)|U |.
NO Case Let S be a solution of f (I). Let us rst remark that for any stack s ∈ S, the set {k : v s [k] = 0} denes a vertex cover in G. Indeed, s contains exactly one vector per set, and thus by construction s selects one vertex per hyperedge in G. Remark also that the cost of s is equal to the size of the corresponding vertex cover. Now, suppose that I is a negative instance. Hence each vertex cover has a size at least equal to (1 -δ)|U |, and any solution S of f (I), composed of exactly n stacks, veries c(S)

≥ n(1 -δ)|U |. YES Case If I is a positive instance, there exists k disjoint sets U 1 , U 2 , . . . , U k ⊆ U such that ∀i = 1, . . . , k, |U i | ≥ 1-ε
k |U | and such that every hyperedge contains at most one vertex from each U i . We introduce the subset

X = U \ k i=1 U i . By denition {U 1 , U 2 , . . . , U k , X} is a partition of U and X ≤ ε|U |. Furthermore, U i ∪ X is a vertex cover ∀i = 1, . . . , k.
Indeed, each hyperedge e ∈ E that contains no vertex of U i , contains at least one vertex of X since e contains k vertices. We now construct a solution S of f (I). Our objective is to construct stacks {s i } such that for any i, the zeros of s i are included in U i ∪ X (i.e. {l :

v si [l] = 0} ⊆ U i ∪ X).
For each e = {u 1 , . . . , u k } ∈ E, we show how to assign exactly one vector of V e to each stack s 1 , . . . , s k . For all i ∈ [k], if v e j represents a vertex u with u ∈ U i , then we assign v e j to s i . W.l.o.g., let

S e = {s 1 , . . . , s k } (for k ≤ k) be the set of stacks that received a vertex during this process. Notice that as every hyperedge contains at most one vertex from each U i , we only assigned one vector to each stack of S e . After this, every unassigned vector v ∈ V e represents a vertex of X (otherwise, such a vector v would belong to a set U i , i ∈ k , a contradiction). We assign arbitrarily these vectors to the remaining stacks that are not in S e . As by construction ∀i ∈ [k], v s i contains only vectors representing vertices from

U i ∪ X, we get c(s i ) ≤ |U i | + |X|.
Thus, we obtain a feasible solution S of cost c(S)

= k i=1 c(s i ) ≤ k|X| + k i=1 |U i |.
As by denition we have |X| +

k i=1 |U i | = |U |, it follows that c(S) ≤ |U | + (k -1)ε|U | and since k = n, c(S) < |U |(1 + nε). If we dene a(n) = (1 + nε)|U | and r(n) = n(1-δ) (1+nε)
, the previous reduction is a r(n)-Gap reduction. Furthermore, lim δ,ε→0 r(n) = n, thus it is NP-hard to approximate (min 0) #0≤1 within a ratio (n -ε ) for any ε > 0.

Notice that, as a function of n, this inapproximability result is optimal. Indeed, we observe that any feasible solution S is an n-approximation as, for any instance I of min 03 , Opt(I) ≥ p and for any solution S, c(S) ≤ pn.

Negative results without assuming UGC Let us now study the negative results we can get when only assuming P = NP. Our objective is to prove that (min 0) #0≤1 is APX-hard, even for n = 2. To do so, we present a reduction from Odd Cycle Transversal, which is dened as follows. Given an input graph G = (U, E), the objective is to nd an odd cycle transversal of minimum size, i.e. a subset T ⊆ U of minimum size such that G[U \ T ] is bipartite. Lemma 1. For any constant γ ≥ 2, there exists an L-reduction from OCT Gγ to (min 0) #0≤1 with n = 2.

Proof. Let us consider an integer γ, an instance I of OCT Gγ , dened by a graph G = (V, E) such that G ∈ G γ . W.l.o.g., we can consider that G contains no isolated vertex.

Remark that any graph can be seen as a 2-uniform hypergraph. Thus, we use the function f previously dened to construct an instance f (I) of (min 0

) #0≤1 such that n = 2. Since, G contains no isolated vertex, f (I) contains no position k such that ∀i ∈ [m], ∀j ∈ [n], v i j [k] = 1.
Let us now prove that I admits an odd cycle transversal of size t if and only if f (I) admits a solution of cost p + t.

⇐ We consider an instance f (I) of (min 0) #0≤1 with n = 2 admitting a solution S = {s A , s B } with cost c(S) = p + t. Let us specify a function g which produces from S a solution T = g(I, S) of OCT Gγ , i.e. a set of vertices of U such that G[U \T ] is bipartite.

We dene T = u ∈ U :

v s A [u] = v s B [u] = 0
, the set of coordinates equal to zero in both s A and s B . We also dene A = u ∈ V :

v s A [u] = 0 and v s B [u] = 1 (resp. B = u ∈ V : v s B [u] = 0 and v s A [u] = 1
), the set of coordinates set to zero only in s A (resp. s B ). Notice that {T, A, B} is a partition of U .

Remark that A and B are independent sets. Indeed, suppose that ∃{u, v} ∈ E such that u, v ∈ A. As {u, v} ∈ E there exists a set V (u,v) containing a vector that represents u and another vector that represents v, and thus these vectors are assigned to dierent stacks. This leads to a contradiction. It follows that G[U \T ] is bipartite and T is an odd cycle transversal.

Since c(S)

= |A| + |B| + 2|T | = p + |T | = p + t, we get |T | = t.
⇒ We consider an instance I of OCT Gγ and a solution T of size t. We now construct a solution S = {s A , s B } of f (I) from T .

By denition, G[U \T ] is a bipartite graph, thus the vertices in U \T may be split into two disjoint independent sets A and B. For each edge e ∈ E, the following cases can occur: if ∃u ∈ e such that u ∈ A, then the vector corresponding to u is assigned to s A , and the vector corresponding to e \ {u} is assigned to s B (and the same rule holds by exchanging A and B) otherwise, u and v ∈ T , and we assign arbitrarily v e u to s A and the other to s B .

We claim that the stacks s A and s B describe a feasible solution S of cost at most p + t.

Since, for each set, only one vector is assigned to s A and the other to s B , the two stacks s A and s B are disjoint and contain exactly m vectors. S is therefore a feasible solution.

Remark that v s

A (resp. v s B ) contains only vectors v such that v[k] = 0 =⇒ k ∈ A ∪ T (resp. k ∈ B ∪ T ), and thus c(v A ) ≤ |A| + |T | (resp. c(v B ) ≤ |B| + |T |). Hence c(S) ≤ |A| + |B| + 2|T | = p + t.
Let us now prove that this reduction is an L-reduction. Therefore, we get an L-reduction for α = γ + 1 and β = 1.

Lemma 2. There exist a constant γ and G ⊂ G γ such that OCT G is APX-hard.

Proof. We present an L-reduction from VC-3, the vertex cover problem in graph with maximum degree 3, to OCT G VC for an appropriate G VC . VC-3 is known to be APX-complete [START_REF] Alimonti | Some APX-completeness results for cubic graphs[END_REF].

Given an instance G = (U, E) of VC-3, we construct an instance f (G) = (U , E ) as follows:

1. For each (u, v) ∈ E, create a vertex z u,v . These z-vertices form the set Z.

2. U = U ∪ Z. 3. E = E ∪{(u, z u,v ), (v, z u,v ) : (u, v) ∈ E}. In other words, for each (u, v) ∈ E,
we create the triangle {u, v, z u,v }.

Let us prove that G = (U, E) admits a solution V C of size |V C| = t if and only if f (G) admits a solution T of size |T | = t.

⇒ Consider a vertex cover V C of size |V C| = t, for each u ∈ V C,
T of f (G), computes a solution V C = g(G, T ) of G.
Notice rst that we can suppose that T contains no z-vertex. Otherwise every triangle {u, v, z u,v } covered by a z u,v ∈ T , can instead be covered by either u or v without increasing the size of T . Thus, we set V C = T . By denition of an odd cycle transversal, T covers all the odd cycles of f (G) and especially the created triangles. Thus, the triangle {u, v, z u,v } corresponding to any edge {u,

v} ∈ E is covered by V C. As V C ∩ Z = ∅, V C is a vertex cover of G.
The previous reduction is an L-reduction for α = β = 1. Let us call G V C the class of graph generated in this reduction. The previous reduction shows that

OCT G V C is APX-hard. It remains to check that G V C ⊆ G γ for a constant γ.
Remark that VC-3 is only dened on 3-regular graphs, it implies that for

any instance G = (U, E) of VC-3, Opt(G) ≥ |U | 3 . As |U | = |U | + |E| ≤ 5|U | 2 , it follows that Opt(f (G)) = Opt(G) ≥ |U | 3 ≥ 2|U | 15 . Hence, G V C ⊂ G γ with γ = 15 2 .
The following result is now immediate.

Theorem 2. (min 0) #0≤1 is APX-hard, even for n = 2.

Approximation algorithm for min 0

Let us now show an example of algorithm achieving a n -f (n, m) ratio. Notice that the (n -) inapproximability result holds for xed n and #0 = 1, while the following algorithm is polynomial-time computable when n is part of the input and #0 is arbitrary.

Proposition 1. There is a polynomial-time n -n-1 nρ(n,m) approximation algorithm for min 0, where ρ(n, m) > 1 is the approximation ratio for independent set in graphs that are the union of m complete n-partite graphs.

Proof. Let I be an instance of min 0. Let us now consider an optimal solution

S * = {s * 1 , . . . , s * n } of I. For any i ∈ [n], let Z * i = {l ∈ [p] : v s * i [l] = 0 and v s * t [l] = 1, ∀t = i} be
{Z * i }, implying |Z * 1 | ≥ ∆ n .
Given a subset Z ⊂ [p], we will construct a solution S = {s 1 , . . . , s n } such that for any l ∈ Z, v s1 [l] = 0, and for any i = 1, v si [l] = 1. Informally, the zero at coordinates Z will appear only in s 1 , which behaves as a "trash" stack. The cost of such a solution is c(S) ≤ c(s 1 ) + Let us now dene how we compute Z.

n i=2 c(s i ) ≤ p + (n -1)(p -|Z|).
Let P = {l ∈ [p] : ∀i ∈ [m], |{j : v i j [l] = 0}| ≤ 1}
be the subset of coordinates that are never nullied in two dierent vectors of the same set. We will construct a simple undirected graph G = (P, E), and thus it remains to dene E. For vector v i j , let Z i j = Z(v i j ) ∩ P , where Z(v) ⊆ [p] denotes the set of null coordinates of vector v. For any i ∈ [m], we add to G the edges of the complete n-partite

graph G i = ({Z i 1 × • • • × Z i n }) (i.e. for any j 1 , j 2 , v 1 ∈ Z i j1 , v 2 ∈ Z i j2 , we add edge {v 1 , v 2 } to G).
This concludes the description of G, which can be seen as the union of m complete n-partite graphs.

Let us now see the link between independent set in G and our problem. Let us rst see why Z * 1 is a independent set in G. Recall that by denition of Z * 1 , for

any l ∈ Z * 1 , v s * 1 [k] = 0, but v s * j [k] = 1, j ≥ 2.
Thus, it is immediate that Z * 1 ⊆ P . Moreover, assume by contradiction that there exists an edge in G between to vertices l 1 and l 2 of Z * 1 . This implies that there exists i ∈ [m], j 1 and

j 2 = j 1 such that v i j1 [l 1 ] = 0 and v i j2 [l 2 ] = 0. As by denition of Z * 1 we must have v s * j [k 1 ] = 1 and v s * j [k 2 ] = 1 for j ≥ 2, this implies that s * 1 must contains both v i j1 and v i j2 ,
a contradiction. Thus, we get OP T (G) ≥ |Z * 1 |, where OP T (G) is the size of a maximum independent set in G.

Now, let us check that for any independent set Z ⊆ P in G, we can construct a solution S = {s 1 , . . . , s n } such that for any l ∈ Z, v s1 [l] = 0, and for any i = 1, v si [l] = 1. To construct such a solution, we have to prove that we can add in s 1 all the vectors v such that ∃l ∈ Z such that v[l] = 0. However, this last statement is clearly true as for any i ∈ [m], there is at most one vector v i j with Z(v i j ) ⊆ Z. Remark 1. We can get, for example, ρ(n, m) = mn m-1 using the following algorithm. For any i ∈ [m], let G i = (A i 1 , . . . , A i n ) be the i-th complete n-partite graph. W.l.o.g., suppose that A 1 1 is the largest set among {A i j }. Notice that |A 1 1 | ≥ OP T m . The algorithm starts by setting S 1 = A 1 1 (S 1 may not be an indepen- dent set). Then, for any i from 2 to m, the algorithm set S i = S i-1 \ (∪ j =j0 A i j ), where j 0 = arg max j {|S i-1 ∩ A i j |}. Thus, for any i we have |S i | ≥ |Si-1| n , and S i is an independent set when considering only edges from ∪ i l=1 G l . Finally, we get an independent set of

G of size |S m | ≥ S1 n m-1 ≥ OP T mn m-1 .
3 Exact resolution of sparse instances

The section is devoted to the exact resolution of min 0 for sparse instances where each vector has at most one zero (#0 ≤ 1). As we have seen in Section 2, (min 0) #0≤1 remains NP-hard (even for n = 2). Thus it is natural to ask if (min 0) #0≤1 is polynomial-time solvable for xed m (for general n). This section is devoted to answer positively to this question. Notice that we cannot extend this result to a more general notion of sparsity as (min 0) #0≤2 is APX-complete for m = 3 [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF]. However, the question if (min 0) #0≤1 is xed parameter tractable when parameterized by m is left open.

We rst need some denitions, and refer the reader to Figure 3 where an example is depicted.

Denition 3.

For any l ∈ [p], i ∈ [m], we dene B (l,i) = {v i j : v i j [l] = 0} to be the set of vectors of set i that have their (unique) zero at position l. For the sake of homogeneous notation, we dene B (p+1,i) = {v i j : v i j is a 1 vector}. Notice that the B (l,i) form a partition of all the vectors of the input, and thus an input of (min 0) #0≤1 is completely characterized by the B (l,i) .

For any

l ∈ [p + 1], the block B l = i∈[m] B (l,i) .
Informally, the idea to solve (min 0) #0≤1 in polynomial time for xed m is to parse the input block after block using a dynamic programming algorithm.

When arriving at block B l we only need to remember for each c ⊆ [m] the number x c of partial stacks that have only one vector for each V i , i ∈ c. Indeed, we do not need to remember what is inside these partial stacks as all the remaining vectors from B l , l ≥ l cannot match (i.e. have their zero in the same position) the vectors in these partial stacks.

prole P = x {∅} = 2, x {1} = 1, x {2} = 1, x {3} = 1, x {1,2} = 1, x {1,3} = 1, x {2,3} = 1,
x {1,2,3} = 1 encoding a set S of partial stacks of I containing two empty stacks. The support of s7 is sup(s7) = {1, 3} and has cost c(s7) = 1. In the following, a prole will be used to encode a set S of n partial stacks by keeping a record of their support. In other words, x c , c ⊆ [m] will denote the number of partial stacks in S of support c. This leads us to introduce the notion of reachable prole as follows: Denition 6. Given two proles P = {x c : c ⊆ [m]} and P = {x c : c ⊆ [m]} and a set S = {s 1 , . . . , s n } of n partial stacks, P is said reachable from P through S i there exist n couples (s 1 , c 1 ), (s 2 , c 2 ), . . . , (s n , c n ) such that:

Denition 4.

A partial stack

s = {v s i1 , . . . , v s i k } of I is such that {i x ∈ [m], x ∈ [k]} are pairwise disjoints, and for any x ∈ [k], v s ix ∈ V ix
For each couple (s, c), sup(s) ∩ c = ∅. For each c ⊆ [m], | {(s j , c j ) : c j = c, j = 1, . . . , n} | = x c . Intuitively, the conguration c appears in exactly x c couples.

For each c ⊆ [m], | {(s j , c j ) : sup(s j ) ∪ c j = c , j = 1, . . . , n} | = x c . Intu- itively, there exist exactly x c couples that, when associated, create a partial of prole c . Given two proles P and P , P is said reachable from P , if there exists a set S of n partial stacks such that P is reachable from P through S.

Intuitively, a prole P is reachable from P through S if every partial stack of the set encoded by P can be assigned to a unique partial stack from S to obtain a set of new partial stacks encoded by P .

Remark that, given a set of partial stacks S only their prole is used to determine whether a prole is reachable or not. An example of a reachable prole is given on Figure 4. We introduce now the following problem Π. We then show that this problem can be used to solve (min 0) #0≤1 problem, and we present a dynamic programming algorithm that solves Π in polynomial time when m is xed.

Optimization Problem 2 Π Input (l, P ) with l ∈ [p + 1], P a prole. Remark that an instance I of (min 0) #0≤1 can be solved optimally by solving optimally the instance I = (1, P = {x ∅ = n, x c = 0, ∀c = ∅}) of Π. The optimal solution of I is indeed a set of n partial disjoint stacks of support [m] of minimum cost.

We are now ready to dene the following dynamic programming algorithm that solves any instance (l, P ) of Π by parsing the instance block after block and branching for each of these blocks on every reachable prole.

Fig. 1 :

 1 Fig. 1: Example of min 0 instance with m = 3, n = 4, p = 6 and of a feasible solution S of cost c(S) = 17.

Fig. 2 :

 2 Fig. 2: Illustration of the reduction from an hypergraph G = (U = {1, 2, 3, 4, 5, 6, 7}, E = {{1, 2, 7} , {1, 3, 4} , {2, 4, 5} , {5, 6, 7}}) to an instance (min 0) #0≤1

For any integer γ ≥ 2 ,

 2 we denote G γ the class of graphs G = (U, E) such that any optimal odd cycle transversal T has size |T | ≥ |U | γ . Given G a class of graphs, we denote OCT G the Odd Cycle Transversal problem restricted to G.

1 . 2 .

 12 By denition, any instance I of OCT Gγ veries |Opt(I)| ≥ |U |/γ. Thus, Opt(f (I)) ≤ |U | + Opt(I) ≤ (γ + 1)Opt(I) We consider an arbitrary instance I of OCT Gγ , f (I) the corresponding instance of (min 0) #0≤1 , S a solution of f (I) and T = g(I), S the corresponding solution of I. We proved |T | -Opt(I) = c(S) -|U | -(Opt(f (I)) -|U |) = c(S) -Opt(f (I)).

  we add the vertex u to T . By denition, V C covers all the edges of G and then all its (odd) cycles. Furthermore, it also covers all the created triangles in f (G) since each of these cycles contains exactly one edge in common with f (G)[U \Z]. Thus T is an odd cycle transversal and |T | = |V C|. ⇐ Let us construct a function g that, given any solution

  Our objective is now to compute such a set Z, and to lower bound |Z| according to |Z * 1 |.

  Thus, any ρ(n, m) approximation algorithm gives us a set Z with |Z| ≥ |Z * 1 | ρ(n,m) ≥ ∆ nρ(n,m) , and we get a ratio of p+(n-1)(p-∆ nρ(n,m) ) 2p-∆ ≤ n -n-1 nρ(n,m) for ∆ = p.

Fig. 3 :

 3 Fig.3: Left: instance I of (min 0) #0≤1 partitionned into blocks. Right:A prole P = x {∅} = 2, x {1} = 1, x {2} = 1, x {3} = 1, x {1,2} = 1, x {1,3} = 1, x {2,3} = 1,x {1,2,3} = 1 encoding a set S of partial stacks of I containing two empty stacks. The support of s7 is sup(s7) = {1, 3} and has cost c(s7) = 1.

  . The support of a partial stack s is sup(s) = {i x , x ∈ [k]}. Notice that a stack s (i.e. non partial) has sup(s) = [m]. The cost is extended in the natural way: the cost of a partial stack c(s) = c( x∈[k] v s ix ) is the number of zeros of the bitwise AND of the vectors of s. We dene the notion of prole as follows: Denition 5. A prole P = {x c , c ⊆ [m]} is a set of 2 m positive integers such that c⊆[m] x c = n.

c 5 =Fig. 4 :

 54 Fig. 4: Example of a proleP = x {1,2} = 1, x {2,4} = 1, x {1,2,4} = 2, x {1,2,3,4} = 1 that is reachable from P = x {∅} = 1, x1 = 2, x {2,4} = 1, x {3,4} = 1 reachable through S = {s1 : sup(s1) = {1, 2, 4} , s2 : sup(s2) = {∅} , s3 : sup(s3) = {1, 2} , s4 : sup(s4) = {2} , s5 : sup(s5) = {2, 4}}.

  Output A set of n partial stacks S = {s 1 , s 2 , . . . , s n } such that S is a partition of B = l ≥l B l and for every c ⊆ [m], |{s ∈ S|sup(s) = [m] \ c}| = x c and such that c(S) = n j=1 c(s j ) is minimum.

  Let Π 1 and Π 2 be two optimization problems with objective functions m 1 and m 2 . Let f be a polynomial-time computable function that given any instance x of Π 1 associates an instance f (x) of Π 2 . Let g be another polynomialtime computable function that given any instance x of Π 1 , and feasible solution S of f (x), associates a feasible solution g(x, S) of Π 1 . If f and g verify the two following conditions: 1. ∃α such that Opt(f (x)) ≤ αOpt(x) 2. ∃β such that for each solution S of Π 2 , |Opt(x)-m 1

		Thus, it was natural to ask if (min 0) #0≤1 was
	polynomial-time solvable for xed m. Section 3 is devoted to answer positively
	to this question. Notice that the question of determining if (min 0) #0≤1 is
	FPT when parameterized by m remains open. Due to space constraints, results
	marked with a	are proved in the appendix.
	2 Approximability of min 0
	Let us rst recall denitions of reductions we use in this paper.
	2.1 Denitions
	L-reduction The L-reduction has been introduced by Papadimitriou et al. in
	[7] as follows:
	Denition 1.

  the set of coordinates equal to zero only in stack s * i . Let ∆ = * i , there are at least two stacks with a zero at coordinate l. W.l.o.g., let us suppose that Z * 1 is the largest set among

n i=1 |Z * i |. Notice that we have c(S * ) ≥ ∆ + 2(p -∆), as for any coordinate l outside i Z

Note that [n] stands for {1,

2, . . . , n}.

i.e. admits an algorithm in f (p)poly(|I|) for an arbitrary function f .

Recall that we assume ∀k ∈ [p], ∃i, ∃j such that v i j [k] = 0

Function MinSumZeroDP(l, P ) if k == p + 1 then return 0; return min(c(S )+MinSumZeroDP(l + 1, P )), with P reachable from P through S , where S partition of B l ;

Note that this dynamic programming assumes the existence of a procedure that enumerates eciently all the proles P that are reachable from P . The existence of such a procedure will be shown thereafter.

Lemma 3. For any instance of Π (l, P ), MinSumZeroDP(l, P ) = Opt(l, P ).

Proof. Lemma 3 is true as in a given block l, the algorithm tries every reachable prole, and the zeros of vectors in blocks B = l <l B l cannot be matched with those of vectors in block B = l ≥l B l . This is the reason why the support of the already created partial stacks (stored in prole P ) is sucient to keep a record of what have been done (the positions of the zeros in the partial stacks corresponding to P is not relevant).

Let us focus now on the procedure in charge of the enumeration of the reachable prole. A rst and intuitive way to perform this operation is by guessing, for all c, c ⊆ [m], y c,c the number of partial stacks in conguration c that will be turned into conguration c with vectors of current block B l . For each such guess it is possible to greedily verify that each y c,c can be satised with the vectors of the current block. As each of the y c,c can take values from 0 to n and c and c can be both enumerated in O * (n 2 m ), the previous algorithm runs in O * (n 2 2m ).

This complexity can be improved as follows. The idea is to enumerate every possible prole P and to verify using another dynamic programming algorithm if such a P is reachable from P . We dene Aux P (P, X), that veries if P is reachable from P by using all vectors of X. If X = ∅, then the algorithm returns whether P is equal to P or not. Otherwise, we consider the rst vector v of X (we x any arbitrary order) for which a branching is done on every possible assignment of v. More formally, the algorithm returns

Using Aux in MinSumZeroDP, we get the following theorem.

Theorem 3. (min 0) #0≤1 can be solved in O * (n 2 m+2 ).

We compute the overall complexity as follows: for each of the pn 2 m possible values of the parameters of MinSumZeroDP, the algorithm tries the n 2 m proles P , and run for each one Aux P in O * (n 2 m nm) (the rst parameter of Aux can take n 2 m values, and the second nm as we just encode how many vectors left in X).