Aurélien Babarit
email: aurelien.babarit@ec-nantes.fr

Fabian Wendt
email: fabian.wendt@nrel.gov

Yi-Hsiang Yu
email: yi-hsiang.yu@nrel.gov

Jochem Weber
email: jochem.weber@nrel.gov

Y.-H Yu

Investigation on the energy

Keywords: Renewable energy, wave energy converter, pressure differential, numerical model, optimization, energy performance

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

Ocean waves are a largely untapped natural renewable energy resource [START_REF] Gunn | Quantifying the global wave power resource[END_REF]. Since the early 1980s, hundreds of wave energy converters (WECs) have been studied and developed. Review of technologies can be found in [START_REF] Falnes | A review of wave energy extraction[END_REF] or [START_REF] De | Wave energy utilization: a review of technologies[END_REF]. Several fullscale prototypes have been tested at sea, however WECs have still not reached the commercial stage. This is mainly because of their high cost of energy in comparison with other renewable energy technologies such as wind or solar photovoltaics [START_REF] Meyer | Bølgekraftprogram: Afsluttende rapport fra Energistyrelsens Rådgivende Bølgekraftudval Bølgekraftudvalgets Sekretariat, Rambøll[END_REF][START_REF] Previsic | E2I EPRI Assessment: Offshore Wave Energy Conversion Devices, E2I EPRI[END_REF][START_REF] Neary | Methodology for design and economic analysis of marine energy conversion (MEC) technologies[END_REF].

The cost of wave energy may decrease in the long term with industrialization and mass production of successful WEC prototypes. However, it is uncertain that a sufficient level of cost reduction can be achieved with WEC technologies based on well-known working principles (see for example [START_REF] De | Wave energy utilization: a review of technologies[END_REF] for a review of working principles of wave energy converters). That is why it is crucial to carry on basic research of new wave energy concepts and components as it may lead to a breakthrough in energy and economic performance. Examples of potential revolutionary technologies include flexible WECs such as the Anaconda WEC [START_REF] Farley | Rubber tubes in the sea[END_REF] or the S3 WEC [START_REF] Babarit | Hydro-elastic modelling of an electro-active wave energy converter[END_REF]; passively phase-controlled WECs such as the CorPower WEC [START_REF] Hals Todalshaug | Tank testing of an inherently phasecontrolled wave energy converter[END_REF]; or WECs with variable geometry such as the National Renewable Energy Laboratory's (NREL's) oscillating wave energy converter [START_REF] Tom | Development of a nearshore oscillating surge wave energy converter with variable geometry[END_REF].

Another example is the M3 flexible WEC [START_REF] Morrow | Submerged wave energy converter[END_REF], known as a pressure-differential device. It takes advantage of the spatially varying pressure differentials in the wave field to drive a fluid flow. The working principle of the M3 WEC is described in [START_REF] Mcnatt | Preliminary modeling and analysis of a horizontal pressure differential wave energy converter[END_REF]:

(It) consists of two deformable air chambers separated by a distance on the order of half a wavelength. The chambers are connected by a pipe with an internal bidirectional turbine. The device is fully submerged and fixed near the sea floor. Due to dynamic wave pressure, one air chamber compresses while the other expands forcing air through the turbine.

As the wave pressure progresses, the pressure differential switches signs, reversing the direction of the air flow.

Figure 1 shows a picture of a scale prototype of the M3 WEC that was deployed and tested offshore the coast of Oregon in September 2014.

In [START_REF] Mcnatt | Preliminary modeling and analysis of a horizontal pressure differential wave energy converter[END_REF], the separating distance and orientation of the device was optimized to maximize the excitation pressure on the device assuming diffraction is negligible.

It was found that for a nondirectional spectrum, the optimal distance between the chambers is close to half the wavelength of the spectrum peak frequency.

The WEC itself was not modeled in [START_REF] Mcnatt | Preliminary modeling and analysis of a horizontal pressure differential wave energy converter[END_REF]. To our knowledge, there are no other publicly available studies that cover the energy performance of pressure-differential WECs (such as the M3 WEC). Thus, the energy performance of fixed-bottom pressuredifferential wave energy converters is an open question, and is therefore the motivation for this study.

The rest of the paper is organized as follows. In Section 2, numerical models of two versions of the pressure-differential WECs are presented. A frequency domain approach was used. One version has the moving surfaces on the bottom of the air chambers whereas the other version has the moving surfaces on the top. Fundamental differences between the two versions are discussed. In Section 3, we provide comparisons of numerical results for energy performance. The most promising design is further investigated and compared to other WEC technologies for energy and economic performance.

Numerical model

Ocean waves model and wave resource

In this study, ocean waves were modeled by unidirectional irregular waves. Irregular waves are a more realistic model for real ocean waves than regular waves.

Only unidirectional waves were considered because the pressure-differential WEC device is designed for small water depths where directional spreading is expected to be negligible thanks to refraction.

In this work, we considered the wave resource for a site located on the west coast of France. The scatter diagram for the wave resource at this site is shown in Figure 2, which was obtained from actual measurements of the wave elevation [START_REF]candhis.cetmef.developpement-durable[END_REF]. However, only the joint probability distributions for the significant height, H S , and the spectrum peak period, T p , are available. The measured sea spectra were not retained. Therefore, it is necessary to assume a spectral shape for the wave spectrum. The JONSWAP spectrum was used in this study with a frequency spreading parameter γ = 3.3. The mean water depth is 47 m at the point where the wave resource was measured.

The targeted deployment water depth of the pressure-differential WEC is shallower.

The effect of water depth on the wave spectrum and wave resource must be taken into account. The waves were assumed to propagate into shallow water according to linear refraction. Because of bottom friction and wave breaking, the wave resource is expected to be less near-shore than offshore. In [START_REF] Folley | Analysis of the nearshore wave energy resource[END_REF], it was shown that the gross wave resource from a 50-m water depth site to a 10-m water depth site is reduced by 20% to 44%. At first, we assumed a constant energy loss of ǫ = 30% for each and every wave component in the wave spectrum. Thus, the following ad-hoc near-shore wave spectrum S h was used:

S h (f ) = 1 -ǫ tanh(kh) + kh cosh(kh) S ∞ (f ) ( 1
)
where f is the frequency, h is the water depth, k is the wavelength, and S ∞ is the well-known JONSWAP spectrum. The factor 1ǫ accounts for the fraction ǫ of the wave energy that is dissipated. The factor

1 tanh(kh)+ kh cosh(kh)
takes into account the wave amplitude modulation caused by shoaling. version is inspired by the M3 WEC, which has the deformable membranes on the bottom of the air chambers. For simplicity, the supporting frame shown in Figure 1 was excluded in the numerical model. Note that there may be other significant and important differences both in geometry and configuration between the studied device and the system that we used as a source of inspiration, thus also the performance may differ.

The studied device consists of a structure standing on the sea bottom and two identical air chambers. The air chambers are connected with a pipe that allows air to be exchanged between the chambers. The power take-off (PTO) is an air turbine that converts the kinetic energy of the air flow in the pipe into mechanical rotational energy. Then, the mechanical rotational energy can be converted into electricity using a generator. The waves are propagating from left to right.

In this analysis, we assumed that the air chambers are identical square boxes with length L c , width B, and height H. Their cross section is denoted by S = L c B. The bottom surfaces of the air chambers are assumed to move only vertically, which may be achieved in practice by using bellows. The distance from the free surface at rest and the bottom of the chambers at rest is denoted as D. The vertical motion of the front chamber is denoted as Z 1 . The vertical motion of the back chamber is denoted as Z 2 . The length of the pipe connecting the two chambers is L and its cross-section area is s. The air turbine is assumed to be located in the middle of the pipe. The volume of each air chamber at static equilibrium is denoted by V S = SH + 1 2 sL.

Modeling of the deformations of the chambers

The mass of the moving surfaces is assumed to be negligible in comparison with their added mass. Thus, at each time t, the moving surfaces are at static equilibrium:

-KZ 1 (t) + S 1 (p * e (M, t) -p * i (M, t)) dS = 0 -KZ 2 (t) + S 2 (p * e (M, t) -p * i (M, t)) dS = 0 ( 2
)
where K is the chamber stiffness coefficient, p * e is the total pressure on the water side, p * i is the total pressure in the chamber with index i, and M is a point on the surface. It is assumed that the stiffness is provided by the bellows or other appropriate mechanisms. Let us denote the dynamic outer pressure p e and the inner dynamic pressure p i . The difference between the total pressure and the dynamic pressure is the static pressure.

Modeling of the outer flow

It is assumed that the deformations of the air chambers and that the amplitude of the waves are small so that linear potential theory is applicable for the modeling of the outer flow. Thus, the outer pressure can be written:

p * e (M, t) = p ex (M, t) + p rad (M, t) + p 0 -ρgz (3)
where p ex is the excitation pressure from the incident wave, p rad is the dynamic pressure from the radiated wave, p 0 is the atmospheric pressure, ρ is the water density, g is the gravity, and z is the vertical coordinate. z = 0 defines the ocean water surface at rest.

The symbol˜indicates the Fourier transform and ω is the wave frequency. pe (M, ω) = pex (M, ω) + prad (M, ω) is the total dynamic pressure in the frequency domain. Let us define:

• The generalized modes [START_REF] Newman | Wave effects on deformable bodies[END_REF] that correspond to the modes of deformation of air chambers 1 and 2:

∂ Φj ∂n (M, ω) = -1 on the bottom of air chamber j ∂ Φj ∂n (M, ω) = 0 everywhere else (4)

• The corresponding generalized forces Fij = S i prad,j (M, ω)dS = -ρ S i ∂ Φj ∂t (M, ω)dS.

Mode 1 corresponds to an oscillatory motion with unit amplitude velocity and wave frequency ω of the bottom surface of the air chamber 1. Mode 2 corresponds to an oscillatory motion with unit amplitude velocity of the bottom surface of the air chamber 2. Φj is the elementary velocity potential for mode j. Any particular motion of chamber 1 and chamber 2 can be written as the superimposition of the two modes 1 and 2 with appropriate modal amplitudes. Thanks to linearity, the velocity potential for this particular deformation is the combination of the elementary velocity potentials.

The elementary velocity potentials (and diffraction potential) may be obtained by solving-in the frequency domain-the linear free-surface potential flow boundary volume problem with the appropriate boundary conditions on the body surface. In this study, the boundary-element-method solver WAMIT was used. Results are excitation force coefficients on the bottom surfaces of the chambers F ex,i , and added masses A ij and radiation damping coefficients B ij for the radiation force on the air chamber i for a unit amplitude deformation of chamber j. Therefore, the dynamic outer pressure on the bottom surface of chamber j can be written in the frequency domain:

S i pe (M, ω)dS = a(ω)F ex,i (ω) - 2 j=1 A ij (ω) Zj (ω) - 2 j=1 B ij (ω) Zj (ω) ( 5
)
where a is the incident wave amplitude.

Modeling of the internal flow

Now we consider the internal flow. The internal pressure at static equilibrium is p S . According to equation (2), p S = p 0 + ρgD.

With the density of air being small, it can be assumed that the thermodynamic processes in the chambers are quasi-static (dynamics effects are neglected). Pressure losses at the inlet and outlet of the pipes are neglected as well as losses caused by friction on the pipe walls. Thus, the pressure is homogeneous in the chambers including the portion of the pipe from the chamber to the air turbine.

Temperature of sea water is constant at the wave period timescale. The device has a large surface of heat exchanges with the surrounding seawater. Thus, it is assumed that thermodynamic processes in the chambers and connecting pipe are isothermal (the air temperature in the chambers is constant and equal to the temperature of the surrounding seawater). Using the perfect gas model for air [START_REF] Kestin | A Course in Thermodynamics[END_REF], one can show:

ṗ * j p * j = ρj ρ j (6)
where ρ j is the air density in chamber j.

The mass of air in chamber j is denoted as m j . m j = ρ j V j where V j is the volume for air chamber j. ṁj = ρj V j + ρ j Vj is the opposite of the mass flow rate from air chamber j through the turbine. The variation of the chamber volume is Vj = -S Żj . We further assume small variations around static equilibrium for the physical quantities of the internal flow. Using equation ( 6) and neglecting higher order terms, it can be shown:

V S p S ṗ * j -S Żj = ṁj ρ ′ (7)
where ρ ′ is the air density in the chambers at static equilibrim.

Let us define the volume flow rate through the turbine

Q = -ṁ1 ρ ′ . Because of mass conservation, ṁ1 + ṁ2 = 0, thus Q = ṁ2 ρ ′ .
By combining with equation ( 7), it can be shown that the time derivative of the pressure in the chambers is related to the deformations of the chambers and the volume flow rate through the turbine:

ṗ1 = p S V S S Ż1 -p S V S Q ṗ2 = p S V S S Ż2 + p S V S Q (8)
To close the problem, a relationship between the internal pressure in the air chambers and the flow rate in the connecting pipe can be written. It is assumed that the head loss through the turbine is proportional to the volume flow rate Q, which is a reasonable assumption for a Wells turbine [START_REF] Brito-Melo | Analysis of Wells turbine design parameters by numerical simulation of the OWC performance[END_REF]. Let B PTO be the proportionality coefficient. Thus, the pressure difference between the air chambers and the volume flow rate are related by the following equation:

p 2 -p 1 = -B PTO Q (9)

Assembled model for version 1 of the pressure-differential WEC

Finally, by combining equations ( 2), ( 5), [START_REF] Babarit | Hydro-elastic modelling of an electro-active wave energy converter[END_REF], and ( 9) and by recalling that the internal static pressure p S is equal to p S = p 0 + ρgD, the equation of motion for version 1 of the pressure-differential WEC can be written in the frequency domain and for a unit wave amplitude as:

           2 j=1 A 1j Zj + 2 j=1 B 1j Zj + p1 S + (K + (ρ -ρ ′ )gS) Z1 = F ex,1 2 j=1 A 2j Zj + 2 j=1 B 2j Zj + p2 S + (K + (ρ -ρ ′ )gS) Z2 = F ex,2 p1 -p S V S S Z1 + p S V S p1 B PTO -p S V S p2 B PTO = 0 p2 -p S V S S Z2 -p S V S p1 B PTO + p S V S p2 B PTO = 0 (10)
The average absorbed power is given by the time average of the product of the head loss through the turbine times the flow rate. For a regular wave of unit amplitude (a = 1) and by using equation ( 9), the power function (in W/m 2 ) can be written:

p = 1 2B PTO |p 2 -p1 | 2 (11)
For an irregular wave, the average absorbed power (in Watt) is the sum of the power contribution from each frequency in the spectrum: We conducted a similar analysis to the one performed for version 1. Only the equations that are different from version 1 are mentioned in the following. The equation for the motion of the moving surfaces for version 2 is:

P = ∞ 0 S h (f )p(f )df (12) 2.3
-KZ 1 (t) -S 1 (p * e (M, t) -p * i (M, t)) dS = 0 -KZ 2 (t) -S 2 (p * e (M, t) -p * i (M, t)s) dS = 0 (13)
The generalized modes that correspond to the modes of deformation of air chambers 1 and 2 are defined as:

∂Φ j ∂n = 1 on the top of air chamber j ∂Φ j ∂n = 0 everywhere else [START_REF] Folley | Analysis of the nearshore wave energy resource[END_REF] and the generalized forces become Equation ( 8) for the time derivative of the pressure in the air chambers becomes:

F ij = ρ S i ∂Φ j ∂t dS.
ṗ1 = -p S V S S Ż1 -p S V S Q ṗ2 = -p S V S S Ż2 + p S V S Q (15)
Finally, the equation of motion for version 2 of the pressure-differential WEC can be written in the frequency domain and for a unit wave amplitude as:

           2 j=1 A 1j Zj + 2 j=1 B 1j Zj -p1 S + (K -(ρ -ρ ′ )gS) Z1 = F ex,1 2 j=1 A 2j Zj + 2 j=1 B 2j Zj -p2 S + (K -(ρ -ρ ′ )gS) Z2 = F ex,2 p1 + p S V S S Z1 + p S V S p1 B PTO -p S V S p2
B PTO = 0 p2 + p S V S S Z2 -p S V S p1 B PTO + p S V S p2 B PTO = 0 (16)
The average absorbed power for version 2 in regular and irregular waves is calculated by applying the same equations ( 11) and ( 12) used for version 1.

Discussion on the basic differences between version 1 and version 2

By comparing equations ( 10) and ( 16), it is evident that the differences between the two versions are in the signs of the coupling terms between the internal pressures and the velocities of the moving surfaces; and in the signs of the hydrostatic stiffness term (ρρ ′ )gS.

In the case in which the moving surfaces are on top of the chambers, the sign in front of the term (ρρ ′ )gS is negative. This implies that if the additional stiffness coefficient K is not large enough (K < (ρρ ′ )gS), the equilibrium position is unstable. Any small disturbance from the equilibrium position will increase until one of the air chambers is fully inflated whereas the other is fully deflated. The

system cannot work if K < (ρ -ρ ′ )gS.
Thus, sufficient additional stiffness must be provided (K ≥ (ρ-ρ ′ )gS). Assuming it is technically feasible, this feature of version 2 of the pressure-differential WEC has a key advantage over version 1 because it provides a mean to tune the natural frequency of the chambers to the dominant wave frequency. Indeed, in the case of version 1, wherein the moving surfaces are on the bottom, the stiffness coefficient

is (K + (ρ -ρ ′ )gS).
The natural frequency cannot be tuned to frequencies below

≈ (ρ-ρ ′ )gS A 11 .
Figure 5 shows the hydrodynamic coefficients for the two versions of the pressuredifferential WEC. The top figures show the meshes that were used to calculate the hydrodynamic coefficients. The connecting pipe and foundations were not taken into account in this first analysis for the sake of simplicity. It is believed that their effect can be made negligible with appropriate design. Dimensions of the chambers are given in Table 1. Left figures represent version 1 of the pressure-differential device.

Right figures represent version 2. The general dimensions of the two versions are the same. In particular, the submergence of the active surfaces is the same in both versions.

When comparing the two versions for the added-mass coefficients, it can be observed that they are significantly smaller for version 2 than for version 1. In the case of version 1, the added-mass coefficients are increased because the device is closer to the seabed. The wall effect adds additional added mass to the system. The added-mass coefficients A jj are approximately halved in version 2 than in version 1, which is expected to be an advantage for version 2 because it could lead to a greater bandwidth for power absorption.

Unlike the added mass coefficients, the radiation damping coefficients are similar for the two versions. They appear to be slightly greater for version 2 than version 1.

Again, this increase is expected to be an advantage for version 2 because it shows a greater potential for wave cancellation, which is the physical process by which wave energy is absorbed [START_REF] Falnes | A review of wave energy extraction[END_REF], [START_REF] Wypych | On the application of circular-cylindrical waves to ocean power absorption[END_REF].

For the excitation force coefficient, it can be observed that the amplitude of the 3. Energy performance of the pressure-differential WECs

Comparison of energy performance of version 1 and version 2

The energy performance of version 1 of the pressure-differential WEC is investigated first. The equation of motion [START_REF] Tom | Development of a nearshore oscillating surge wave energy converter with variable geometry[END_REF] was implemented in Matlab, which allows for the calculation of the power function p using equation [START_REF] Morrow | Submerged wave energy converter[END_REF] and in irregular waves P using equation [START_REF] Mcnatt | Preliminary modeling and analysis of a horizontal pressure differential wave energy converter[END_REF]. By varying the sea state characteristics H S and T p , the power matrix of the device can be built. Then, the annual average of power absorption can be obtained by combining the power matrix with the sea state statistics of Figure 2.

The dimensions given in Table 1 were used for the geometry of the device. Once the geometric dimensions are set, the two remaining variables are the chamber stiffness coefficient K and the air turbine damping coefficient B PTO . Several discrete values for the stiffness coefficient K were considered and the B PTO damping coefficient was systematically optimized to maximize the annual average of power absorption.

A brute-force search was used for the optimization. Figure 6 shows the annual average of power absorption as a function of the chamber stiffness coefficient K for version 1. It can be observed that the maximum power is obtained with zero chamber stiffness. Indeed, as discussed in Section 2.4, version 1 is inherently stiffer than version 2 because of its geometrical configuration. According to equation [START_REF] Tom | Development of a nearshore oscillating surge wave energy converter with variable geometry[END_REF], the minimum stiffness coefficient is equal to the hydrostatic stiffness (ρρ ′ )gS. It is approximately equal to 640 kN/m with the dimensions in Table 1. The added mass is on the order of 400 kN/m.s 2 , according to Figure 5, which results in a maximum natural period of 5 s for the device. It is in the bottom range of periods for the wave resource (5-15 s, as shown in Figure 2). Any increase in the stiffness coefficient leads to a decrease in the device's natural period, leading to a poorer agreement between the bandwidth of the device and the wave resource and thus a decrease in power absorption as shown in Figure 6.

On the other hand, it can be expected that the power absorption would increase with the negative stiffness coefficient. According to Figure 2, it seems that a natural period close to 10 s would provide the best agreement between the device's bandwidth and the wave resource. It would require a negative spring with stiffness coefficient on the order of -480 kN/m. Figure 7 shows that the annual average absorbed power peaks at K = -500 kN/m, which is very close to the estimate. The annual average absorbed power is six times greater for the optimal negative stiffness coefficient than for zero stiffness. Including a system that provides a negative spring effect is highly beneficial to version 1 of the pressure-differential WEC with respect to energy performance. an hypothetical near-shore site as a function of the chamber stiffness coefficient (negative stiffness coefficients were considered in comparison to Figure 6). Note that no stroke limitation has been taken into account for the moving surface motion.

Mechanical arrangements that can provide a negative spring effect have been proposed recently [START_REF] Hals Todalshaug | Tank testing of an inherently phasecontrolled wave energy converter[END_REF]. The same effect may also be obtained with active control of actuators, but in that case the actuator's efficiency is critical to the overall effectiveness of the control [START_REF] Genest | Effect of non ideal power take off on the energy absorption of a reactively controlled one degree of freedom wave energy converter[END_REF]. In the case of the pressure-differential WEC, the hydrostatic term in the equation of motion can behave as a negative spring if the moving surfaces are set to the top of the air chambers instead of the bottom (see Section 2.4).

As follows, we show that it allows the negative spring requirement to be suppressed while maintaining high energy absorption performance.

Version 2 of the pressure-differential WEC is now considered (the moving surfaces are on the top). The geometric dimensions of version 2 are identical to the those of version 1 except for the vertical position, which is chosen to have the submergence depth of the active surfaces at 9 m in both versions.

For version 2, the chamber stiffness coefficient K must be greater than the hydrostatic stiffness (ρρ ′ )gS ≈ 640 kN/m. Otherwise, the static equilibrium position is unstable and the system cannot work. Figure 8 shows the annual average of power absorption and capture width as a function of the chamber stiffness coefficient. It can be seen that the power absorption peaks for a stiffness coefficient close to 720 kN/m. For version 2, Figure 5 shows that the added mass is close to 200 kN/m.s 2 . Thus, the natural period is approximately 10 s. For version 2 of the pressure-differential WEC, it is possible to make the device's bandwidth match the wave periods with a positive stiffness coefficient. In practice, it should be relatively easy to achieve the appropriate stiffness by using simple springs that connect the top and bottom surfaces of the air chambers. Note that the bellows may provide the appropriate stiffness by themselves.

When comparing Figures 7 and8, it can be observed that the shape of the curves is similar. This result was expected because the main difference in the equation of motion of the two versions is in the hydrostatic stiffness coefficient as discussed in Section 2.4. The response of version 2 for a stiffness coefficient of K 2 is close to the response of version 1 for a stiffness coefficient of

K 1 + (ρ -ρ ′ )gS = K 2 -(ρ -ρ ′ )gS.
The peak power for version 2 is obtained for K 2 ≈ 720 kN/m, which corresponds to K 1 = -560 kN/m. K 1 = -560 kN/m is close to the stiffness of the peak in Figure 7. Note that it appears that the peak power is slightly greater for version 2 than for version 1 and that the bandwith is slightly wider. This increase can be explained by the slightly greater radiation damping coefficient (higher peak power) and the smaller added mass (greater bandwidth).

Energy performance of version 2 with motion constraint

Version 2 of the pressure-differential WEC with K = 720 kN/m appears to be the most promising design with respect to energy performance. It is further investigated in this section, particularly with respect to stroke limitation. The motion of the moving surface is limited because of practical constraints. Also, the linear potential theory that was used to model the outer flow assumes small amplitude motion. If the motion is too large, the actual power performance may deviate significantly from the numerical prediction. It can be observed that the device is highly responsive to wave forcing, over a wide range of wave frequencies. At peak, the motion of the top surfaces of the air chambers is eight times the incident wave amplitude. For a typical incident wave with a 1-m wave amplitude, such a large response is unrealistic, because it is much greater than the height of the chamber (1 m). It is also very unlikely that it is possible to make an air chamber with a bellow allowing a 16-m stroke. Moreover, the small amplitude motion assumption would be violated. Nonlinear effects in the outer fluid structure interaction would limit the motion response. However, for small amplitude waves on the order of a few tens of centimeters, these limitations do not apply. Therefore, it is expected that large motion RAO would be observed in practice for small waves.

The device would be highly efficient in these cases.

It is also worth noting that the response of the bottom and back chambers are superimposed, which indicates that when the top surface of the front chamber goes up, the surface of the back chamber goes down with the same amplitude. This response indicates that compressibility effects in the air chambers are small. The top right plot in Figure 9 shows the dynamic internal pressure in the two chambers. The bottom left plot is the volume flow rate through the air turbine (red line). In the same graph, the product of the chambers' motion RAO, moving surface area, and wave frequency (| Z1 |Sω) has been plotted as well (dashed black line) and corresponds to the volume flow rate assuming air is incompressible. It can be observed that the results are superimposed. It shows that compressibility effects are negligible.

The bottom right plot in Figure 9 shows the absorbed power by the device (red line). The theoretical maximum for a point absorber with a dipole-like wave radiation pattern was plotted in the same graph for the sake of comparison (P max = ρg 2 4ω tanh(kh) + kh cosh(kh) 2 k [START_REF] Wypych | On the application of circular-cylindrical waves to ocean power absorption[END_REF]). Indeed, the pressure-differential WEC can be approximated by two point sources separated by the distance S. As the two chambers move in opposite directions (because compressibility effects are negligible), the wave radiation pattern from the pressure-differential device is similar to the wave radiation pattern of a dipole in the far field. This outcome is confirmed in Figure 10 wherein the wave radiation patterns of the pressure-differential WEC and a dipole are compared for a wave period of 10 s. In Figure 9, it can be observed that the wave power absorption by the device is rather close to the theoretical maximum over a wide range of frequencies.

Nevertheless, for moderate and strong sea states, the motion response predicted by the numerical model-and thus power absorption-is unrealistic if stroke limita-371 tion is not taken into account. In practice, stroke limitation may come from nonlinear 372 stiffness or a moving surface reaching the end stops, which is a highly nonlinear effect.

373

Thus, it cannot be taken into account directly in the linear frequency domain-based 374 model. However, it can be considered indirectly.

375

The effect of stroke limitation is to limit the amplitude of motion. This limitation 376 results in a reduction in power absorption that is related to the ratio of the predicted 377 motion amplitude to the motion constraint Z mx . If the ratio is smaller than 1 (motion 378 amplitude is smaller than the motion constraint), there is no reduction in power 379 absorption. Otherwise, the power loss is expected to increase quadratically with 380 increasing ratio of motion amplitude to motion constraint. By using equations ( 11 and ( 9), assuming the volume flow rate Q is approximately proportional to the chambers deformation velocities because the effect of compressibility appears to be negligible, and taking into account the motion constraint, the average absorbed power pc is on the order of:

pc ≈ 1 2 B PTO ω 2 min(| Z1 | 2 , Z 2 mx ) (17)
Thus, if | Z1 | > Z mx , the difference in absorbed power with and without consideration of the motion constraint is on the order of

1 2 B PTO ω 2 | Z1 | 2 (| Z1 | 2 -Z 2 mx ). It increases quadratically with | Z1 |.
The power loss can be mitigated by increasing the PTO damping coefficient B PTO in comparison with its optimal value without motion constraint. The direct effect of increasing B PTO is higher damping in the system, thus reduced motion amplitude 17), it can be seen that increasing B PTO has no effect on the term min(| Z1 | 2 , Z 2 mx ) in the constrained absorbed power pc while | Z1 | is greater than the motion constraint Z mx . Thus, while this condition is maintained, the constrained absorbed power is expected to increase linearly with increasing B PTO . In conclusion, it appears that the PTO damping coefficient should be optimized for each and every sea state to maximize the power absorption while maintaining the motion amplitude below or equal to the motion constraint.

| Z1 |. But from equation (
Following this discussion, we now introduce the significant motion response which is similar to the significant height:

Z 2 1/3 = 4max ∞ 0 S h (ω)| Z1 (ω)| 2 dω, ∞ 0 S h (ω)| Z2 (ω)| 2 dω (18)
Z 1/3 is equal to 2 times the standard deviation of the motion response of the device. It provides a measure for the air chamber motion in response to the sea state defined by the wave spectrum S h (ω) as the significant height H S does for the wave crests. Note that the significant height is a measure of the wave elevation stroke (distance from the crests to the troughs) whereas Z 1/3 is a measure for the amplitude of the motion (half of the stroke).

The air turbine coefficient B PTO was reoptimized to limit the air chamber response Z 1/3 below the threshold Z mx . This optimization has been applied to different thresholds between 0.25 and 2 m. The air turbine coefficient B PTO was optimized for each sea state. Note that, because Z 1/3 is 2 times the variance of the motion, the motion amplitude may be sometimes higher than the threshold Z mx . However, these events are expected to be rather infrequent, thus, the effect on power absorption of stroke limitation during these events is expected to be small. Figure 11 shows the annual average of absorbed power as a function of the threshold Z mx . It can be observed that the absorbed power increases with the increasing threshold Z mx . The increase rate appears to be linear up to Z mx = 0.75 m. Then, the increase rate seems to de- crease as Z mx keeps increasing. It is clear that Z mx should be as large as practically possible to maximize energy performance.

The threshold Z mx = 1 m is selected for further investigation as it corresponds to the full utilization of the height of the chamber (H=1 m). The nameplate rated power is set to P rated = 150 kW, meaning that, for each sea state of the power matrix, the average power is capped at 150 kW. Figure 12 shows the power matrix of the device (in kW), the significant motion response matrix (in m), the optimal air turbine coefficient matrix (in Pa.s/m -3 ) and the matrix of the significant pressure drop through the turbine (in kPa). It can be observed that the significant motion response reaches the motion threshold much quicker than the absorbed power reaches the power threshold (rated power).

To maintain the amplitude of the motion response below the motion threshold, the top right plot in Figure 12 shows that the air turbine coefficient B PTO must increase by two orders of magnitude from the weaker to the stronger sea states. This increase may be challenging to achieve in practice particularly while maintaining a good conversion efficiency from kinetic energy in the air flow to electricity. A technical solution may require using several connecting pipes and air turbines in parallel. Depending on the sea states, some of the pipes may close or open to maintain appropriate air flow velocities at the air turbines.

Assuming this issue can be overcome, the annual average absorbed power by the device is 82 kW. This corresponds to a capture width [START_REF] Falnes | A resonant point absorbed of ocean-wave power[END_REF] of 4.9 m, the wave power resource at the site being 16.8 kW/m. As the device width is 8 m, it appears that the device is able to capture wave energy over a distance that is of the same order of magnitude as its width. Following [START_REF] Babarit | A database of capture width ratio of wave energy converters[END_REF], a characteristic active width B C is defined as the diameter of a disk in which the surface area is equal to the area of the two moving surfaces: B C = 12.7 m. Then, the maximum relative capture width η 1 = C W B C is 38%. Compared to other WECs (see Figure 16 in [START_REF] Babarit | A database of capture width ratio of wave energy converters[END_REF]), it seems 443 that the pressure-differential WEC could be as efficient in absorbing waves as the 2.

449

On a practical note, the pressure-differential WEC may have some advantages 450 as compared to fixed OWSCs. Indeed, a challenge with fixed OWSCs is the large 451 horizontal force in the foundation [START_REF] Tom | Development of a nearshore oscillating surge wave energy converter with variable geometry[END_REF], [START_REF] Babarit | The NumWEC project: Numerical estimation of energy delivery from a selection of wave energy converters[END_REF]. The horizontal force is much smaller for the pressure-differential WEC because of the small vertical surface. The vertical force in the foundation is expected to be closely related to the volume of air in the air chambers when fully inflated (buoyancy force). When considering motion constraint, the vertical force may be estimated approximately three times the buoyancy force for the air chamber at rest. By using an inexpensive ballast, it should be relatively easy to achieve sufficient system mass to avoid the device being lifted by the waves.

If the seabed allows, suction anchors may also be appropriate.

Comparison with other WEC technologies for economic performance measures

In [START_REF] Babarit | Numerical benchmarking study of a selection of wave energy converters[END_REF], eight WEC technologies were studied and compared with respect to economic performance measures. It is interesting to compare how the pressuredifferential WEC performs in comparison with these other devices. Following the specifications of the performance measures in [START_REF] Babarit | Numerical benchmarking study of a selection of wave energy converters[END_REF], the characteristic mass of the pressure-differential WEC is taken as being equal to three times the volume to account for the foundations (V c =384 tons). The characteristic surface area is calculated as being equal to the outer surface of the connecting pipe plus four times the outer surface of the air chambers with the height increased to 2 m to include the foundations. This approach provides a characteristic surface area of S c =414 m 2 . Thus, the ratio of annual absorbed energy E to characteristic mass is E Vc =1.9. This ratio is 20% better than the best of the other WEC technologies in [START_REF] Babarit | Numerical benchmarking study of a selection of wave energy converters[END_REF] ( E Vc =1.6 for the fixed-bottom heave-buoy array). The ratio of annual absorbed energy to the characteristic surface area is E Sc =1.8, which is close to the best-performing fixed-bottom oscillating flap ( E Sc =2 in [START_REF] Babarit | Numerical benchmarking study of a selection of wave energy converters[END_REF]).

However, in [START_REF] Babarit | Numerical benchmarking study of a selection of wave energy converters[END_REF] the near-shore wave resource was decreased by only 10% in comparison with the offshore resource whereas in this study it was decreased by 30%. Thus, the annual average absorbed power by the pressure-differential WEC was recalculated for a 10% decrease of the offshore resource. The nameplate rated power was increased to 190 kW while the motion constraint was maintained at Z mx = 1 m. The annual average absorbed power is equal to 99 kW and the ratio of annual absorbed energy to the characteristic surface area is 2.1. Thus, the energy-to-surface ratio is actually 5% greater for the pressure-differential WEC than for the fixedbottom oscillating flap when considering the same level of wave resource. [START_REF] Babarit | Numerical benchmarking study of a selection of wave energy converters[END_REF] and the pressure-differential WEC. The top plot is the mean annual absorbed power, the middle plot is the ratio of absorbed energy to characteristic volume. The bottom plot is the ratio of absorbed energy to characteristic surface.

performance criteria; and that it performs slightly better than the best of other 488 technologies with respect to these two particular critera.

489

Finally, it can be observed that the pressure-differential WEC appears to have a high capacity factor (55%), suggesting a cost-efficient PTO design. In this study, the power matrix was capped at 150 kW. In Figure 11, the uncapped annual average absorbed power is 89 kW for Z mx = 1 m. Thus, capping the power at 150 kW decreases power absorption by only 7%. The high capacity factor can be explained by the wide bandwidth as shown in Figure 12 and the demanding motion constraint Z mx = 1 m. Because of the motion constraint, the power increases slowly with increasing significant height, thus explaining the high capacity factor. Note that if the motion is not constrained and the power is not capped, the annual average absorbed power is 340 kW (four times the power without constraints). Also, note that a capacity factor of 55% is significantly greater than other renewable energy technologies such as wind turbines and solar photovoltaics.

Conclusion

The motivation for this study was to investigate the energy performance of a new WEC concept that takes advantage of the spatially varying pressure differentials in the wave field to drive a fluid flow. Two versions of the concept were considered.

Version 1 has the moving surfaces on the bottom of the air chambers whereas version 2 has the moving surfaces on the top.

Numerical models were developed to calculate power absorption for both regular and irregular waves. A fundamental difference between version 1 and version 2 for the hydrostatic force was highlighted. Because of this difference, it is much easier to tune the bandwidth of version 2 to match with the wave periods than for version 1.

It appears preferable to have the moving surfaces on the top.

The most promising design for version 2 was further investigated. It was found necessary to take into account stroke limitations when optimizing the system to avoid unrealistic results for motion response. The significant motion response was limited to 1 m by increasing the air turbine coefficient with increasing energy in the sea conditions. The estimated annual average absorbed power of the device is 82 kW for a near-shore site with a 16.8 kW/m wave resource and a 150-kW rated power. The capacity factor is greater than 50%.

When comparing the energy performance and economic performance measures to other WEC technologies, it appears that the pressure-differential WEC is among the most efficient WECs with respect to energy performance. The device seems to perform slightly better than the best of other technologies with respect to energyto-mass and energy-to-surface-area economic performance measures.

Therefore, we believe that the pressure-differential WEC deserves further study.

With respect to energy performance, the effect of the size of the air chambers may be investigated as well as the effect of the separating distance between the chambers.

The significance of the energy losses in the internal flow should also be assessed.

This research may be achieved relatively easily with computational fluid dynamics calculations. Further, the design of the air turbine(s) may have a strong impact on the efficiency of the conversion of the absorbed wave power into electricity. There are also practical challenges, such as the design of air chambers with bellows, the integration of springs to achieve the appropriate air chamber stiffness, and the design of the foundations. Convincing installation and maintenance scenarios need to be developed, specifically for devices that are designed to be submerged in energetic sites.

Finally, because the pressure-differential WEC design is near-shore and apparently rather efficient at absorbing waves, further research may be directed at assessing its potential for coastal erosion protection. On the other hand, sediment transport and scour around the device may raise further issues.

Figure 1 :

 1 Figure 1: The scale prototype of the M3 WEC during its deployment offshore the coast of Oregon in September 2014.

Figure 2 :

 2 Figure 2: Measured wave scatter diagram offshore Yeu island on the west coast of France (GPS coordinates 046 o 40,000' N -02 o 25,000' N).

Figure 3 :

 3 Figure 3: Sketch of version 1 of the pressure-differential wave energy device with moving surfaces on the bottom.

2. 2 .

 2 Figure3shows a sketch of the pressure-differential wave energy device. This

Figure 4

 4 Figure 4 shows a sketch of the second version of a pressure-differential wave energy device. The difference with the first version is that the moving surfaces are on top of the air chambers.

Figure 4 :

 4 Figure 4: Sketch of version 2 of the pressure-differential wave energy device with moving surfaces on the top.

  hydrodynamic coefficients is the same for the front and back chambers (|F ex,1 | = |F ex,2 |) for the two versions. It shows that diffraction effects are negligible for this size of the air chambers. As expected, the excitation increases with decreasing wave frequency. The limit for ω → 0 is in agreement with ρgS = 640 kN/m. Because diffraction effects are negligible, the excitation force coefficients are identical for the two versions. Neither version 1 nor 2 has an advantage on this aspect.

Figure 6 :

 6 Figure 6: Annual average of power absorption for version 1 of the pressure-differential WEC at an hypothetical near-shore site as a function of the chamber stiffness coefficient. Note that no stroke limitation has been taken into account for the moving surface motion.

Figure 7 :

 7 Figure7: Annual average of power absorption for version 1 of the pressure-differential WEC at an hypothetical near-shore site as a function of the chamber stiffness coefficient (negative stiffness coefficients were considered in comparison to Figure6). Note that no stroke limitation has been taken into account for the moving surface motion.

Figure 8 :

 8 Figure8: Annual average of power absorption and capture width for version 2 of the pressuredifferential WEC at a hypothetical, near-shore site as a function of the chamber stiffness coefficient. Note that no stroke limitation has been taken into account for the moving surface motion.

Figure 9

 9 Figure 9 shows the response of version 2 of the pressure-differential WEC in regular waves with K = 720 kN/m. The top left plot shows the motion response amplitude operators (RAOs) of the top surfaces of the front and back air chambers.

Figure 9 :

 9 Figure 9: Response of version 2 of the pressure-differential WEC in regular waves. The top left plot shows the motion RAOs of the top surfaces of the front and back air chambers. The top right plot shows the dynamic internal pressure in the two chambers. The bottom left plot is the actual volume flow rate through the air turbine and the volume flow rate for incompressible air. The bottom right plot shows the absorbed power by the device and the theoretical maximum for a point absorber with a dipole-like wave radiation pattern.

Figure 10 :

 10 Figure 10: Left plot: amplitude of the free surface elevation for the wave radiated by the pressuredifferential WEC. Right plot: amplitude of the free surface elevation for the wave radiated by a dipole. The wave period is 10 s. The pattern is similar.

Z 1/ 3 ,Figure 11 :

 311 Figure 11: Annual average of absorbed power for version 2 of the pressure-differential WEC as a function of the threshold on the significant motion response Z mx . The air turbine coefficient B PTO was optimized for each state to limit the air chamber response Z 1/3 below the threshold. The chamber stiffness is K = 720 kN/m.

Figure 12 :

 12 Figure 12: Power matrix (top left, in kW), significant motion response matrix (bottom left, in m), optimal air turbine coefficient matrix (top right, in Pa.s/m -3 ) and matrix of the significant pressure drop through the turbine (bottom right, in kPa) for version 2 of the pressure-differential WEC. The chamber stiffness is K = 720 kN/m. The average power is capped at 150 kW. The motion threshold is Z mx = 1 m.

444

  most efficient WECs (i.e., fixed oscillating wave surge converters[OWSCs]). This 445 possibility is not surprising as the wave radiation pattern of the pressure-differential 446 WEC is similar to the wave radiation pattern of OWSCs (dipole-like pattern). A 447 summary of energy performance metrics of this optimized version of the pressure-448 differential WEC is shown in Table

Figure 13 showsFigure 13 :

 1313 Figure13shows the comparison of the economic performance measures for the eight WECs technologies studied in[START_REF] Babarit | Numerical benchmarking study of a selection of wave energy converters[END_REF] and the pressure-differential WEC. It appears that the pressure-differential WEC is significantly better than the average of other technologies for both the energy-to-mass and energy-to-surface-area economic

Table 1 :

 1 Hydrodynamic coefficients for the two versions of the pressure-differential WEC. The top figures show the meshes that were used for the calculation of the hydrodynamic coefficients. Dimensions are given in Table1. Left figures are for version 1 of the pressure-differential device. Right figures represent version 2. The most noticeable difference is the added mass coefficients for version 2 that are significantly smaller than for version 1. Excitation force coefficients appear to be identical (wave direction is 0 degrees, i.e., waves are propagating along the x-axis). Dimensions of the pressure-differential WECs considered in this study. The dimensions are the same in the two versions including the submergence depth of the moving surfaces.

		Z			Z
	Version 1	Y	X	Version 2	Y	X

  )

	400					400
						0.2					0.2
						0.19					0.19
						0.18					0.18
						0.17					0.17
	200				0.16	200			0.16
						0.15					0.15
						0.14					0.14
						0.13					0.13
						0.12					0.12
	Y	0				0.11 0.1	Y	0			0.11 0.1
						0.09					0.09
						0.08					0.08
						0.07					0.07
						0.06					0.06
	-200				0.05	-200			0.05
						0.04					0.04
						0.03					0.03
						0.02					0.02
						0.01					0.01
	-400 -400	-200	X 0	200	400	-400 -400	-200	X 0	200	400
	381

Table 2 :

 2 Summary of energy performance metrics for the optimized version of version 2 of the pressure-differential WEC.

	Wave power resource	16.8 kW/m
	Annual average absorbed power 82 kW
	Rated power	150 kW
	Capacity factor	55%
	Width	8 m
	Characteristic width	12.7 m
	Capture width	4.9 m
	Capture width ratio	38 %

Acknowledgements

This work was supported by the U.S. Department of Energy under Contract No. DE-AC36-08GO28308 with the National Renewable Energy Laboratory. Funding for the work was provided by the DOE Office of Energy Efficiency and Renewable Energy, Wind and Water Power Technologies Office. It was carried out in collaboration between Ecole Centrale de Nantes (ECN) and NREL. Aurélien Babarit thanks NREL for hosting him during this study. The authors are also grateful to the three anonymous reviewers whose comments helped improve significantly the manuscript.

The U.S. Government retains and the publisher, by accepting the article for publication, acknowledges that the U.S. Government retains a nonexclusive, paidup, irrevocable, worldwide license to publish or reproduce the published form of this work, or allow others to do so, for U.S. Government purposes.


Cristina Bazgan

Laurent Gourvès
email: laurent.gourves@lamsade.dauphine.fr

Jérôme Monnot
email: monnot@lamsade.dauphine.fr

Approximation with a fixed number of solutions of some biobjective maximization problems ⋆

Approximation with a fixed number of solutions of some multiobjective maximization problems

Introduction

In multiobjective combinatorial optimization a solution is evaluated considering several objective functions and a major challenge in this context is to generate the set of efficient solutions or the Pareto set (see [START_REF] Ehrgott | Multicriteria optimization[END_REF] about multiobjective combinatorial optimization). However, it is usually difficult to identify the efficient set mainly due to the fact that the number of efficient solutions can be exponential in the size of the input and moreover the associated decision problem is NP-complete even if the underlying single-objective problem can be solved in polynomial time. To handle these two difficulties, researchers have been interested in developing approximation algorithms with an a priori provable guarantee such as polynomial time constant approximation algorithms. Considering that all objectives have to be maximized, and for a positive ρ ≤ 1, a ρ-approximation of Pareto set is a set of solutions that includes, for each efficient solution, a solution that is at least at a factor ρ on all objective values. Intuitively, the larger the size of the approximation set, the more accurate it can be.

It has been pointed out by Papadimitriou and Yannakakis [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF] that, under certain general assumptions, there always exists a (1ε)-approximation, with any given accuracy ε > 0, whose size is polynomial both in the size of the instance and in 1/ε but exponential in the number of criteria. In this result, the accuracy ε > 0 is given explicitly but the size of the approximation set is not given explicitly. When the number of solutions in the approximation set is limited, not every level of accuracy is possible. So, once the number of solutions is fixed in the approximation set of a multiobjective problem, the following questions are raised: What is the accuracy for which an approximation is guarantee to exist? Which accuracy can be obtained in polynomial time?

In this paper we are interested in establishing for biobjective maximization problems the best approximation ratio of the set of efficient solutions when the size of the approximation set is given explicitly. We give two approaches that deal with biobjective problems that allow us to obtain approximations of the set of efficient solutions with one or several solutions. More precisely, in a first approach, we consider a general maximization problem (denoted by Π 1 in the following) and establish a sufficient condition that guarantees the construction of a constant approximation of the Pareto set with an explicitly given number of solutions. As a corollary, we can construct a (1ε)-approximation of the Pareto set with O( 1 ε ) solutions. In a second approach, we establish a necessary and sufficient condition for the construction of a constant approximation of the Pareto set with one solution.

Properties defined in these two approaches apply to several problems previously studied in single-objective approximation. Then we derive polynomial time constant approximations with one solution for Biobjective Max Bisection, Biobjective Max Partition, Biobjective Max Cut, Biobjective Max Set Splitting, Biobjective Max Matching. Some instances show that the given biobjective appromixation ratios are the best we can expect. In addition Biobjective Max Partition, Biobjective Max Cut, Biobjective Max Set Splitting admit a (1ε)-approximation of the Pareto set with O( 1 ε ) solutions.

Several results exist in the literature on the approximation of multiobjective combinatorial optimization problems. One can mention the existence of fully polynomial time approximation schemes for biobjective shortest path [START_REF] Hansen | Bicriteria path problems[END_REF][START_REF] Warburton | Approximation of pareto-optima in multiple-objective shortest path problems[END_REF][START_REF] Tsaggouris | Multiobjective optimization: Improved fptas for shortest paths and non-linear objectives with applications[END_REF], knapsack [START_REF] Erlebach | Approximating multiobjective knapsack problems[END_REF][START_REF] Bazgan | Implementing an efficient fptas for the 0-1 multi-objective knapsack problem[END_REF], minimum spanning tree [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF], scheduling problems [START_REF] Angel | On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems[END_REF], randomized fully polynomial time approximation scheme for matching [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF], and polynomial time constant approximation for max cut [START_REF] Angel | Approximation algorithms for the bi-criteria weighted max-cut problem[END_REF], a biobjective scheduling problem [START_REF] Stein | On the existence of schedules that are near-optimal for both makespan and total weighted completion time[END_REF] and the traveling salesman problem [START_REF] Angel | Non)-approximability for the multi-criteria TSP(1,2)[END_REF][START_REF] Manthey | On approximating multi-criteria tsp[END_REF]. Note that [START_REF] Angel | Approximation algorithms for the bi-criteria weighted max-cut problem[END_REF] and [START_REF] Stein | On the existence of schedules that are near-optimal for both makespan and total weighted completion time[END_REF] are approximations with a single solution.

This article is organized as follows. In Section 2, we introduce basic concepts about multiobjective optimization and approximation. Section 3 is devoted to an approach for approximating some biobjective problems with one or several solutions. Section 4 presents a necessary and sufficient condition for approximating within a constant factor some biobjective problems with one solution. Conclusions are provided in a final section. Due to space limitation, some proofs are omitted.

Preliminaries on multi-objective optimization and approximation

Consider an instance of a multi-objective optimization problem with k criteria or objectives where X denotes the finite set of feasible solutions. Each solution x ∈ X is represented in the objective space by its corresponding objective vector w(x) = (w 1 (x), . . . , w k (x)). We assume that each objective has to be maximized. From these k objectives, the dominance relation defined on X states that a feasible solution x dominates a feasible solution x ′ if and only if w i (x) ≥ w i (x ′ ) for i = 1, . . . , k with at least one strict inequality. A solution x is efficient if and only if there is no other feasible solution x ′ ∈ X such that x ′ dominates x, and its corresponding objective vector is said to be non-dominated. Usually, we are interested in finding a solution corresponding to each non-dominated objective vector, set that is called Pareto set.

For any 0 < ρ ≤ 1, a solution x is called a ρ-approximation of a solution x ′ if w i (x) ≥ ρ • w i (x ′ ) for i = 1, . . . , k. A set of feasible solutions X ′ is called a ρapproximation of a set of efficient solutions if, for every feasible solution x ∈ X, X ′ contains a feasible solution x ′ that is a ρ-approximation of x. If such a set exists, we say that the multi-objective problem admits a ρ-approximate Pareto set with |X ′ | solutions.

An algorithm that outputs a ρ-approximation of a set of efficient solutions in polynomial time in the size of the input is called a ρ-approximation algorithm. In this case we say that the multi-objective problem admits a polynomial time ρ-approximate Pareto set.

Consider in the following a single-objective maximization problem P defined on a ground set U. Every element e ∈ U has a non negative weight w(e). The goal is to find a feasible solution (subset of U) with maximum weight. The weight of a solution S must satisfy the following scaling hypothesis: if opt(I) denotes the optimum value of I, then opt(I ′ ) = t • opt(I), where I ′ is the same instance as I except that w ′ (e) = t • w(e). For example, the hypothesis holds when the weight of S is defined as the sum of its elements' weights, or min w(e) : e ∈ S, etc.

In the biobjective version, called biobjective P , every element e ∈ U has two non negative weights w 1 (e), w 2 (e) and the goal is to find a Pareto set within the set of feasible solutions. Given an instance I of biobjective P , we denote by opt i (I) (or simply opt i ) the optimum value of I restricted to objective i, i = 1, 2.

Here, the objective function on objective 1 is not necessarily the same as on objective 2, but both satisfy the scaling hypothesis.

3 Approximation with a given number of solutions Papadimitriou and Yannakakis [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF] proved the existence of at least one (1ε)approximation of size polynomial in the size of the instance and 1 ε . In this result, the accuracy ε > 0 is given explicitly but the size of the approximation set is not given explicitly. In this section we consider a general maximization problem Π 1 and establish a sufficient condition that guarantees the construction of a constant approximation of the Pareto set with an explicitly given number of solutions for Π 1 . This result allows to construct a (1ε)-approximation of the Pareto set with O( 1 ε ) solutions but not necessarily in polynomial time. Moreover, if the single objective problem is polynomial time constant approximable and the sufficient condition is strengthened then the biobjective version is also polynomial time constant approximable with one solution. Thus we obtain constant approximations and polynomial time constant approximations with one solution for Biobjective Max Partition, Biobjective Max Cut, Biobjective Max Set Splitting, Biobjective Max Matching.

In the following, we are interested in particular cases of biobjective maximization problems, Biobjective Π 1 , which satisfy the following property.

Property 1. Given any two feasible solutions S 1 and S 2 , and any real α satisfying 0 < α ≤ 1, if w 2 (S 1 ) < αw 2 (S 2 ) and w 1 (S 2 ) < αw 1 (S 1 ) then there exists a feasible solution S 3 which satisfies w

1 (S 3 ) > (1 -α)w 1 (S 1 ) and w 2 (S 3 ) > (1 -α)w 2 (S 2 ).
We say that Biobjective Π 1 satisfies polynomially Property 1 if S 3 can be constructed in polynomial time.

Property 1 means that if S 1 is not an α-approximation of S 2 and S 2 is not an α-approximation of S 1 for both objective functions w 1 and w 2 , then there exists a feasible solution S 3 which simultaneously approximates S 1 and S 2 with performance guarantee 1α.

Given a positive integer ℓ, consider the equations x 2ℓ = 1x ℓ and x 2ℓ-1 = 1x ℓ . Denote by α ℓ and β ℓ their respective solutions in the interval [0, 1).

Remark that α ℓ = √ 5-1 2 1/ℓ and α ℓ < β ℓ+1 < α ℓ+1 , ℓ ≥ 1.
Theorem 1. If Biobjective Π 1 satisfies Property 1, then it admits a β ℓ -approximate Pareto set (resp. an α ℓ -approximate Pareto set) containing at most p solutions, where p is a positive odd integer such that p = 2ℓ -1 (resp. a positive even integer such that p = 2ℓ).

Proof. Let S 1 (resp. S 2 ) be a solution optimal for the first objective (resp. second one). In the following, opt denotes the optimal value on the first objective and also on the second objective. This can be assumed without loss of generality because a simple rescaling can make the optimal values coincide (e.g. we can always assume that opt 2 = 0, thus by multiplying each weight w 2 (e) by opt1 opt2 we are done). Then

w 1 (S 1 ) = w 2 (S 2 ) = opt. If p is odd then ρ = β ℓ with p = 2ℓ -1, otherwise ρ = α ℓ with p = 2ℓ. Subdivide the bidimensionnal value space with coordinates {0} ∪ {ρ i opt : 0 ≤ i ≤ p}. See Figure 1 for an illustration. Given i, 1 ≤ i ≤ p, the strip s(i, .
) is the part of the space containing all couples (w 1 , w 2 ) satisfying ρ i opt < w 1 ≤ ρ i-1 opt and 0 ≤ w 2 ≤ opt. The strip s(p + 1, .) is the part of the space containing all couples (w 1 , w 2 ) satisfying 0 ≤ w 1 ≤ ρ p opt and 0 ≤ w 2 ≤ opt. Given j, 1 ≤ j ≤ p, the strip s(., j) is the part of the space containing all couples (w 1 , w 2 ) satisfying ρ j opt < w 2 ≤ ρ j-1 opt and 0 ≤ w 1 ≤ opt. The strip s(., p + 1) is the part of the space containing all couples (w 1 , w 2 ) satisfying 0 ≤ w 2 ≤ ρ p opt and 0 ≤ w 1 ≤ opt. Suppose that w 2 (S 1 ) < ρ p opt and w 1 (S 2 ) < ρ p opt. In other words S 1 ∈ s(1, .) ∩ s(., p + 1) and S 2 ∈ s(., 1) ∩ s(p + 1, .). Using Property 1 there exists a solution S 3 satisfying w 1 (S 3 ) > (1ρ p )opt and w 2 (S 3 ) > (1ρ p )opt. For the case ρ = β ℓ and p = 2ℓ -1, we get that 1 -

ρ p = 1 -β 2ℓ-1 ℓ = β ℓ ℓ = ρ ℓ .
For the case ρ = α ℓ and p = 2ℓ, we get that 1 -

ρ p = 1 -α 2ℓ ℓ = α ℓ ℓ = ρ ℓ . Then S 3 is a ρ-approximation of any solution S satisfying max{w 1 (S), w 2 (S)} ≤ ρ ℓ-1 opt.
One can construct a ρ-approximate Pareto set P as follows: P = {S 3 } at the beginning and for j = ℓ -1 down to 1, pick a feasible solution s with maximum weight w 1 in s(., j) (if s(., j) contains at least one value of a feasible solution) and set P = P ∪ {S}. Afterwards, for i = ℓ -1 down to 1, pick a feasible solution S with maximum weight w 2 in s(i, .) (if s(i, .) contains at least one value of a feasible solution) and set P = P ∪ {S}. For every strip the algorithm selects a solution which ρ-approximates (on both objective functions) any other solution in the strip. Since the solutions of P approximate the whole bidimensionnal space, P is a ρ-approximate Pareto set containing at most 2ℓ -1 solutions. Here 2ℓ -1 is equal to p when p is odd, otherwise it is equal to p -1. Now suppose that w 2 (S 1 ) ≥ ρ p opt (the case w 1 (S 2 ) ≥ ρ p opt is treated similarly). Solution S 1 must be in s(., j * ) for 1 ≤ j * ≤ p. Since w 1 (S 1 ) = opt, S 1 is a ρ-approximation of any solution S in s(., p) ∪ s(., p + 1). One can build an ρapproximate Pareto set P as follows: P = {S 1 } at the beginning and for j = j * -1 down to 1, pick a feasible solution S with maximum weight w 1 in s(., j) (if s(., j) contains at least one value of a feasible solution) and set P = P ∪ {S}. Since the strips form a partition of the space, the algorithm returns an ρ-approximate Pareto set containing at most p solutions.

⊓ ⊔ Corollary 1. If Biobjective Π 1 satisfies Property 1, then it admits a (1ε)approximate Pareto set containing O( 1 ε ) solutions. Property 1 can be relaxed in the following way: Property 2. We are given two feasible solutions S 1 and S 2 , and a real α satisfying 0 < α ≤ 1. If w 2 (S 1 ) < αw 2 (S 2 ) and w 1 (S 2 ) < αw 1 (S 1 ) then there exists a feasible solution S 3 which satisfies w 1 (S 3 ) > (cα)w 1 (S 1 ) and w 2 (S 3 ) > (cα)w 2 (S 2 ), where 0 < c ≤ 1.

We define similarly that Biobjective Π 1 satisfies polynomially Property 2.

Given a positive integer ℓ, consider the equations x 2ℓ = cx ℓ and x 2ℓ-1 = c-x ℓ . Denote by γ ℓ and δ ℓ their respective solutions in the interval [0, 1). Remark that γ ℓ = (

√ 1+4c- 1 2
) 1/ℓ and γ ℓ < δ ℓ < γ ℓ+1 , ℓ ≥ 1.

Theorem 2. If Biobjective Π 1 satisfies Property 2, then it admits a δ ℓ -approximate Pareto set (resp. an γ ℓ -approximate Pareto set) containing at most p solutions, where p is a positive odd integer such that p = 2ℓ -1 (resp. a positive even integer such that p = 2ℓ).

Proof. The proof is similar with the proof of Theorem 1. Suppose that w 2 (S 1 ) < ρ p opt and w 1 (S 2 ) < ρ p opt. Using Property 2 there exists a solution S 3 satisfying w 1 (S 3 ) > (c-ρ p )opt and w 2 (S 3 ) > (c-ρ p )opt. For the case ρ = δ ℓ and p = 2ℓ-1, we get that c -

ρ p = c -δ 2ℓ-1 ℓ = δ ℓ ℓ = ρ ℓ .
For the case ρ = γ ℓ and p = 2ℓ, we get that cρ p = cγ 2ℓ ℓ = γ ℓ ℓ = ρ ℓ . Then S 3 is a ρ-approximation of any solution S satisfying max{w 1 (S), w 2 (S)} ≤ ρ ℓ-1 opt.

⊓ ⊔

The previous results of this section consider the construction, not necessarily in polynomial time, of an approximate Pareto set with a fixed number of solutions. We give in the following some conditions on the construction in polynomial time of an approximate Pareto set with one solution.

Proposition 1. If Π 1 is polynomial time ρ-approximable and Biobjective Π 1 satisfies polynomially Property 1 (resp. 2), then Biobjective Π 1 is polynomial time ρ 2 -approximable (resp. cρ 2 -approximable) with one solution. Proof. Let S 1 (resp. S 2 ) be a polynomial time ρ-approximation solution for the first objective (resp. second one). In the following, opt 1 (resp. opt 2 ) denotes the optimal value on the first objective (resp. second one). If w 2 (S 1 ) ≥ w2(S2)

Max Pos NAE

The Max Pos NAE problem consists of a set of clauses C defined on a set of boolean variables x 1 , . . . , x n . The clauses are composed of two or more positive variables and they are endowed with a non negative weight. The Max Pos NAE problem consists of finding an assignment of the variables such that the total weight of the clauses that are satisfied is maximum, where a positive clause is satisfied by an assignment if it contains at least a true variable and at least a false variable. Max Pos NAE generalizes Max Cut and so it is NP-hard and 0.7499-approximable [START_REF] Zhang | Improved approximations for max set splitting and max NAE SAT[END_REF]. Max Pos NAE is also known under the name Max Set Splitting or Max Hypergraph Cut [START_REF] Zhang | Improved approximations for max set splitting and max NAE SAT[END_REF]. Lemma 1. Biobjective Max Pos NAE satisfies polynomially Property 1.

Proof. Let α ∈ (0, 1] and S 1 , S 2 two solutions of an instance of biobjective Max Pos NAE satisfying the inequalities: w 2 (S 1 ) < αw 2 (S 2 ) and w 1 (S 2 ) < αw 1 (S 1 ). Consider S 3 = (S 1 \ S 2 ) ∪ (S 2 \ S 1 ). Let c(S) be the set of clauses satisfied by assigning variables from S to true and those from S to false. Clearly c(S) = {C i = x i1 ∨ . . . ∨ x it : ∃x ij ∈ S, ∃x i ℓ ∈ S}. In the following a clause C i is identified by the set of variables that it contains {x i1 , . . . , x it }. Then c(S 1 ) \ c(S 2 ) = {C :

C ∩ S 1 = ∅ and C ∩ S1 = ∅} ∩ {C : C ⊆ S 2 or C ⊆ S2 }. Let C ∈ c(S 1 ) \ c(S 2 ). If C ⊆ S 2 then since C ∩ S1 = ∅ we have ∅ = C ∩ (S 2 \ S 1 ) ⊆ C ∩ S 3 . Moreover C ∩ S3 = ∅ since C ∩ S 1 ∩ S 2 = ∅. Thus C ∈ c(S 3 ). If C ⊆ S2 then since C ∩ S 1 = ∅ we have ∅ = C ∩ (S 1 \ S 2 ) ⊆ C ∩ S 3 . Moreover C ∩ S3 = ∅ since C ∩ S3 ⊆ C ∩ S1 ∩ S2 = ∅. Thus c(S 1 ) \ c(S 2 ) ⊆ C(S 3
). In the similar way we can prove c(S 2 )\c(S 1 ) ⊆ C(S 3 ). Thus, c(S 1 )∆c(S 2 ) = c(S 1 )\c(S 2 ) ∪ c(S 2 )\c(S 1 ) is contained in c(S 3 ).

The inequality w 2 (S 1 ) < αw 2 (S 2 ) can be rewritten as follows:

C∈c(S1) w 2 (C) < α C∈c(S2) w 2 (C) C∈c(S1)\c(S2) w 2 (C) + (1 -α) C∈c(S1)∩c(S2) w 2 (C) < α C∈c(S2)\c(S1) w 2 (C)
We can use it to get

w 2 (S 3 ) ≥ C∈c(S1)\c(S2) w 2 (C) + C∈c(S2)\c(S1) w 2 (C) = = C∈c(S1)\c(S2) w 2 (C) + α C∈c(S2)\c(S1) w 2 (C) + (1 -α) C∈c(S2)\c(S1) w 2 (C) > > 2 C∈c(S1)\c(S2) w 2 (C)+(1-α) C∈c(S1)∩c(S2) w 2 (C)+(1-α) C∈c(S2)\c(S1) w 2 (C) ≥ ≥ (1 -α) C∈c(S2) w 2 (C) = (1 -α)w 2 (S 2 ).
Using the same technique we can show that w 1 (S 3 ) > (1α)w 1 (S 1 ). ⊓ ⊔ Corollary 2. Biobjective Max Pos NAE admits a (i) β ℓ -approximate Pareto set (resp. an α ℓ -approximate Pareto set) containing at most p solutions, where p = 2ℓ -1 (resp. p = 2ℓ).

(ii) (1ε)-approximate Pareto set containing O( 1 ε ) solutions.

As indicated above, Corollary 2 deals with the possibility to reach some approximation bounds when the number of solutions in the Pareto set is fixed. We give in the following an approximation bound that we can obtain in polynomial time with one solution.

Corollary 3. Biobjective Max Pos NAE admits a polynomial time 0.374approximate Pareto set with one solution.

Proof. The results follows from Lemma 1 and Proposition 1 with ρ = 0.7499. ⊓ ⊔ We consider in the following a particular case of Max Pos NAE in which every clause contains exactly k variables, denoted Max Pos kNAE. Max Pos 3NAE is 0.908-approximable [START_REF] Zwick | Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint[END_REF]. For k ≥ 4, Max Pos kNAE is (1 -2 1-k )approximable [START_REF] Alimonti | Non-oblivious local search for graph and hypergraph coloring problems[END_REF][START_REF] Kann | Approximability of maximum splitting of k-sets and some other apx-complete problems[END_REF] and this is the best possible since it is hard to approximate within a factor of 1 -2 1-k + ε, for any constant ε > 0 [START_REF] Hastad | Some optimal inapproximability results[END_REF]. Proof. The results follows from Lemma 1 and Proposition 1 with ρ = 0.908 and

ρ = 1 -2 1-k . ⊓ ⊔
We consider in the following another particular case of Max Pos NAE in which every clause contains exactly 2 variables, that is exactly Max Cut which is 0.878-approximable [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF]. Proof. The results follows from Lemma 1 and Proposition 1 with ρ = 0.878 [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF].

⊓ ⊔

Clearly this last result is the same as the one given in [START_REF] Angel | Approximation algorithms for the bi-criteria weighted max-cut problem[END_REF] but we use a different method. We remark that Biobjective Max Cut is not (1/2 + ε)-approximable with one solution [START_REF] Angel | Approximation algorithms for the bi-criteria weighted max-cut problem[END_REF], meaning that we are close to the best possible approximation result.

Max Partition

The Max Partition problem is defined as follows: given a set J of n items 1, . . . , n, each item j of positive weight w(j), find a solution S that is a bipartition J 1 ∪ J 2 of the n items such that w(S) = min{ j∈J1 w(j), j∈J2 w(j)} is maximized. This NP-hard problem was also studied in the context of scheduling, where the number of partitions is not fixed, and consists of maximizing the earliest machine completion time [START_REF] Woeginger | A polynomial time approximation scheme for maximizing the minimum machine completion time[END_REF]. Proof. Max Partition is a particular case of the Max Subset Sum problem. An input of Max Subset Sum is formed by a set J of n items 1, . . . , n, each item j has a positive weight w(j), and an integer t. The problem consists of finding a subset S of J whose sum w(S) is bounded by t and maximum. Max Subset Sum has a fptas [START_REF] Cormen | Introduction to Algorithms[END_REF]. We can obtain a fptas for Max Partition using the previous fptas for t = n i=1 w(i)/2. The results follows from Lemma 2 and Proposition 1 with ρ = 1 -2ε.

⊓ ⊔

Observe that Biobjective Max Partition is not (1/2+ε)-approximable with one solution. In order to see this, consider 3 items of weights w 1 (1) = 2, w 2 (1) = 1, w 1 (2) = 1, w 2 (2) = 2, w 1 (1) = 1, w 2 (3) = 1. The two efficient solutions S i , i = 1, 2 consists of placing i in a part and the other items in the other part and have weights w 1 (S 1 ) = 2, w 2 (S 1 ) = 1, w 1 (S 2 ) = 1, w 2 (S 2 ) = 2. Any other solution is either dominated by one of these two or has weights equal to 1 on both criteria.

Max Matching

Given a complete graph G = (V, E) with non negative weights on the edges, the Max Matching problem is to find a matching of the graph of total weight maximum. Max Matching is solvable in polynomial time [START_REF] Edmonds | Paths, trees, and flowers[END_REF]. We study in this part the biobjective Max Matching problem and consider instances where the graph is a collection of complete graphs inside which the weights satisfy the triangle inequality, since otherwise the biobjective Max Matching problem is not at all approximable with one solution. In order to see this, consider a complete graph on 3 vertices with weights (1, 0), (0, 1), (0, 0). The optimum value on each objective is 1. Nevertheless, any solution has value 0 on at least one objective. Clearly Property 1 is not satisfied in this case.

Biobjective Max Matching problem is NP-hard [START_REF] Serafini | Some considerations about computational complexity for multi objective combinatorial problems[END_REF]. It remains NP-hard even on instances where the graph is a collection of complete graphs inside which the weights satisfy the triangle inequality. ⊓ ⊔

Approximation with one solution

In this section, we establish a necessary and sufficient condition for constructing, not necessarily in polynomial time, a constant approximation with one solution of the Pareto set for biobjective maximization problems. Moreover, if the condition is strengthened and the single-objective problem is polynomial time constant approximable, then the biobjective version is polynomial time constant approximable with one solution. Thus, using this condition, we establish a polynomial time 0.174-approximation with one solution for Biobjective Max Bisection.

In the following, we are interested in particular cases of biobjective maximization problems, Biobjective Π 2 which satisfy the following property. Property 3. We can construct three solutions S 1 , S 2 , S 3 such that S i is a ρ iapproximation for problem Π 2 on objective i, i = 1, 2, and S 3 is such that w 1 (S 2 ) + w 1 (S 3 ) ≥ α • w 1 (S 1 ) and w 2 (S 1 ) + w 2 (S 3 ) ≥ α • w 2 (S 2 ) for some α ≤ 1.

We say that Biobjective Π 2 satisfies polynomially Property 3 if S 1 , S 2 , S 3 can be constructed in polynomial time.

The aim of solution S 3 in Property 3 is to compensate the potential inefficiency of S i on criterion 3i, i = 1, 2.

Theorem 3. Biobjective Π 2 is (resp. polynomial time) constant approximable with one solution if and only if it satisfies (resp. polynomially) Property 3. More precisely, if Biobjective Π 2 satisfies polynomially Property 3 such that S i is a polynomial time ρ i -approximation for problem Π 2 on objective i, i = 1, 2, then Biobjective Π 2 admits a polynomial time α min{ρ1,ρ2} 2 -approximation algorithm with one solution.

Proof. Suppose that Biobjective Π 2 is ρ-approximable with one solution. Let S 3 be this solution and S 1 and S 2 any two solutions. Then w 1 (S 3 ) ≥ ρ • opt 1 ≥ ρ • w 1 (S 1 ) and thus by setting α = ρ we have w 1 (S 2 ) + w 1 (S 3 ) ≥ α • w 1 (S 1 ). The second inequality holds also.

Suppose now that Biobjective Π 2 satisfies Property 3. Since S i is a ρ iapproximation for problem Π 2 on objective i, i = 1, 2, we have w 1 (S 1 ) ≥ ρ 1 •opt 1 and w 2 (S 2 ) ≥ ρ 2 • opt 2 .

Since Property 3 is satisfied, we can construct S 3 such that

w 1 (S 2 ) + w 1 (S 3 ) ≥ α • w 1 (S 1 ) (1)
and

w 2 (S 1 ) + w 2 (S 3 ) ≥ α • w 2 (S 2 ) (2)
Now, we study different cases:

• If w 1 (S 2 ) ≥ α 2 w 1 (S 1
), then we deduce that S 2 is a good approximation of the Pareto set. From the hypothesis, we have w 1 (S 2 ) ≥ α 2 w 1 (S 1 ) ≥ α • min{ρ1,ρ2} 2 opt 1 . On the other hand, we also have w

2 (S 2 ) ≥ ρ 2 • opt 2 ≥ α min{ρ1,ρ2} 2 opt 2 . • If w 2 (S 1 ) ≥ α 2 w 2 (S 2
), then we deduce that S 1 is a good approximation of the Pareto set. From the hypothesis, we have w

2 (S 1 ) ≥ α 2 w 2 (S 2 ) ≥ α • min{ρ1,ρ2} 2
opt 2 . On the other hand, by the construction of S 1 we also have

w 1 (S 1 ) ≥ ρ 1 • opt 1 ≥ α • min{ρ1,ρ2} 2 opt 1 . • If w 1 (S 2 ) ≤ α 2 w 1 (S 1
) and w 2 (S 1 ) ≤ α 2 w 2 (S 2 ), then it is S 3 which is a good approximation of the Pareto set. Indeed, from inequality (1), we deduce

w 1 (S 3 ) ≥ α 2 w 1 (S 1 ) ≥ α • min{ρ1,ρ2}
2 opt 1 and on the other hand, from inequality (2), we also get w

2 (S 3 ) ≥ α 2 w 2 (S 2 ) ≥ α • min{ρ1,ρ2} 2 opt 2 .
In any of these three cases, we obtain a α • min{ρ1,ρ2} 2 -approximation with one solution.

Clearly, if S 1 , S 2 , S 3 are computable in polynomial time, then Biobjective Π 2 is approximable in polynomial time.

⊓ ⊔

Remark that we can extend Theorem 3 to the case where ρ i are not constant. The interest of Property 3 is to find a simple method in order to construct a polynomial time constant approximation for Biobjective Π 2 . This method does not allow us to obtain the best polynomial time constant approximation for Biobjective Π 2 with one solution, but only to prove the fact that the problem is polynomial time constant approximable with one solution.

In Lemma 1 we prove that if a problem Π is (resp. polynomial time) constant approximable and if Biobjective Π satisfies (resp. polynomially) Property 1, then Biobjective Π is (resp. polynomial time) constant approximable with one solution, and thus Biobjective Π satisfies (resp. polynomially) Property 3 by Theorem 3. Thus all problems studied in Section 3 satisfies Property 3.

There exist problems which are polynomial time constant approximable and thus satisfy Property 3 and do not satisfy Property 1. One example is Biobjective TSP, which is polynomial time 7 27 -approximable with one solution [START_REF] Manthey | On approximating multi-criteria tsp[END_REF][START_REF] Paluch | A 7/9 -approximation algorithm for the maximum traveling salesman problem[END_REF] and does not satisfy Property 1.

Proposition 2. Biobjective TSP does not satisfy Property 1.

Proof. Consider the complete graph K 5 where a fixed K 4 is decomposable into 2 Hamiltonian paths P 1 and P 2 . For every edge e ∈ E(K 5 ), set w 1 (e) = 1 and w 2 (e) = 0 if e ∈ P 1 , w 1 (e) = 0 and w 2 (e) = 1 if e ∈ P 2 and w 1 (e) = 0 and w 2 (e) = 0 if e / ∈ P 1 ∪ P 2 . We can check that there are four non-dominated tours T i , i = 1, . . . , 4 with w 1 (T 1 ) = 3, w 2 (T 1 ) = 0, w 1 (T 2 ) = 0, w 2 (T 2 ) = 3, w 1 (T 3 ) = 2, w 2 (T 3 ) = 1 and w 1 (T 4 ) = 1, w 2 (T 4 ) = 2. Consider S i = T i , i = 1, 2 and α = 1/2. Clearly w 2 (S 1 ) < αw 2 (S 2 ) and w 1 (S 2 ) < αw 1 (S 1 ). Moreover there is no solution S 3 such that w 1 (S 3 ) > (1α)w 1 (S 1 ) and w 2 (S 3 ) > (1α)w 2 (S 2 ).

⊓ ⊔

We consider in the following a problem that satisfies Property 3 and for which we are not able to prove that it satisfies Property 1.

Max Bisection

Given a graph G = (V, E) with non negative weights on the edges, the Max Bisection problem consists of finding a bipartition of the vertex set V into two sets of equal size such that the total weight of the cut is maximum. We establish in this part a polynomial time ρ 4 -approximation algorithm for Biobjective Max Bisection where ρ is any polynomial time approximation ratio given for Max Bisection. Max Bisection is NP-hard [START_REF] Karp | Reducibility among combinatorial problems[END_REF] and the best approximation ratio known for Max Bisection is ρ = 0.701 [START_REF] Halperin | A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems[END_REF]. Proof. The results follows from Theorem 3 and Lemma 4 and using the polynomial time 0.701-approximation algorithm for Max Bisection [START_REF] Halperin | A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems[END_REF].

⊓ ⊔

Conclusion

In this paper, we established some sufficient conditions that allow to conclude on the existence of constant approximations of the Pareto set with an explicitly given number of solutions for several biobjective maximization problems. The results we obtained establish a polynomial time approximation when we ask for a single solution in the approximation set. A possible future work would be to give a polynomial time approximation for any explicitly given number of solutions. A necessary and sufficient condition is given for the construction of (polynomial time) constant approximation with one solution for biobjective maximization problems. It would be interesting to generalize this result to maximization problems with more than two objectives. Another interesting future work would be to establish lower bounds for any explicitly given number of solutions for multiobjective maximization problems. Our approaches deal with maximization problems and they do not seem to apply to minimization problems. A possible explanation is that, in the maximization framework, adding elements to a partial solution rarely deteriorates it. Minimization problems rarely satisfy this property. Establishing constant approximation of the Pareto set with a given number of solutions or show that this is not possible for minimization problems is an interesting open question.

Fig. 1 .

 1 Fig. 1. Illustration of Theorem 1

2 then w 2 ( 2 then w 1 ( 2 ,

 22212 S 1 ) ≥ ρ 2 opt 2 and thus S 1 is a ρ 2 -approximate Pareto set. If w 1 (S 2 ) ≥ w1(S1) S 2 ) ≥ ρ 2 opt 1 and thus S 2 is a ρ 2 -approximate Pareto set. Otherwise, w 2 (S 1 ) < w2(S2) 2 and w 1 (S 2 ) < w1(S1) 2 and since Biobjective Π 2 satisfies polynomially Property 1, we can construct in polynomial time a feasible solution S 3 which satisfies w 1 (S 3 ) ≥ w1(S1) 2 and w 2 (S 3 ) ≥ w2(S2) that is a ρ 2 -approximate Pareto set. ⊓ ⊔ We consider in Sections 3.1, 3.2, and 3.3 several examples of problems Π 1 that satisfy the scaling hypothesis and such that Biobjective Π 1 satisfy Property 1 or Property 2.

Corollary 4 .

 4 Biobjective Max Pos 3NAE admits a polynomial time 0.454approximate Pareto set with one solution. For k ≥ 4, Max Pos kNAE admits a polynomial time 1/2 -2 -k -approximate Pareto set with one solution.

Corollary 5 .Corollary 6 .

 56 Biobjective Max Cut admits a (i) β ℓ -approximate Pareto set (resp. an α ℓ -approximate Pareto set) containing at most p solutions, where p = 2ℓ -1 (resp. p = 2ℓ).(ii) (1ε)-approximate Pareto set containing O( 1 ε ) solutions. Biobjective Max Cut admits a polynomial time 0.439-approximate Pareto set with one solution.

Lemma 2 .Corollary 7 .Corollary 8 .

 278 Biobjective Max Partition satisfies polynomially Property 1. Biobjective Max Partition admits a (i) β ℓ -approximate Pareto set (resp. an α ℓ -approximate Pareto set) containing at most p solutions, where p = 2ℓ -1 (resp. p = 2ℓ). (ii) (1ε)-approximate Pareto set containing O( 1 ε ) solutions. Biobjective Max Partition admits a polynomial time (1/2ε)approximate Pareto set with one solution, for every ε > 0.

Lemma 3 .Corollary 9 .

 39 Biobjective Max Matching satisfies polynomially Property 2 with c = 1/3. Biobjective Max Matching admits a δ ℓ -approximate Pareto set (resp. an γ ℓ -approximate Pareto set) containing at most p solutions, where p = 2ℓ -1 (resp. p = 2ℓ). Corollary 10. Biobjective Max Matching admits a polynomial time 1 6 -approximate Pareto set with one solution. Proof. It follows from Lemma 3 and Proposition 1 considering ρ = 1.

Lemma 4 .

 4 Biobjective Max Bisection satisfies polynomially Property 3 with α = 1 and ρ 1 = ρ and ρ 2 = ρ 2 , where ρ is any polynomial time approximation ratio given for Max Bisection. Corollary 11. Biobjective Max Bisection admits a polynomial time 0.174approximate Pareto set with one solution.

⋆ This research has been supported by the project ANR-09-BLAN-0361 GUaranteed Efficiency for PAReto optimal solutions Determination (GUEPARD)