Mathurin Body

Bernard Cousin

Paula Viana

Mario Cordeiro

Vitor Rodrigues

Giulia Ferrari

Ingo Hoentsch

IRT, Gernamy Tobias Marx

Walter Bernet

Edgar Müller

Serge Daulard

Thomson

Bernard Algayres

Marc Laurentin

Fpdi

The ASSET Architecture: Integrating Media Applications and Broadcasting Products in a Unified Model and Framework

goal of the ASSET project. This European funded project gathers eight partners (Compaq-HP Group, THOMSON, Dalet a.n.n, INESC Porto, INRIA, Institut fuer Rundfunktechnik, Front Porch Digital International, SHS Multimedia) to create a universal and unified system architecture that shall greatly improve interoperability in broadcasting environments. The implementation of this solution will indeed make integration of different proprietary systems and media applications much easier. This paper outlines the ASSET architecture, describes some key-concepts of the ASSET framework and presents the prototype currently under development.

I. INTRODUCTION

Digital systems for TV content creation offer facilities that cover the complete operational workflow, including acquisition, creation, editing, control, storage, broadcasting publishing and archiving of media assets.

Technical solutions available on the market are limited due to the lack of interoperability between equipment and applications. They are vertically integrated or proprietary and rely typically on a single manufacturer or system integrator. Hence they are not compliant with the broadcaster requirements. Application providers should be able to implement platform independent and device independent programs for increased portability.

The objective of the ASSET project [1] (IST-2001-37379 Architectural Solutions for Services Enhancing digital Television) is to identify solutions and define a software architecture that will overcome these limitations. The project identifies technologies, APIs, and software tools that enable both users and vendors to use/create media applications integrated in systems independent of device manufacturer, programming language and the underlying middleware platform.

The project approach takes advantage of open standards and emerging technologies (like MXF [START_REF]Material eXchange Format (MXF)[END_REF], standard data models for describing essences, XML [START_REF]). W3C Recommendation. World Wide Consortium[END_REF] and distributed system technologies) for defining the ASSET architecture. The structural design of the ASSET solution wraps the standard software layered architecture into a middleware approach that provides:

§ the abstraction of broadcast software and hardware devices as logical resources, § generic, openly defined and extensible interfaces to control devices, data distribution and data flows, § added value for system logic: optimized decisions to configure devices, convert/move data and handle workflows.

II. ASSET SYSTEM ARCHITECTURE

A. Architecture overview

The ASSET architecture is based upon a software framework -the ASSET framework -composed by a set of three standard interfaces and protocols for applications and products working together in an integrated environment. Applications communicate with the framework using the ASSET Public API, which allows them:

§ to communicate with any other application, § to access the public services provided by the framework, § to use additional functionalities implemented by third party integrators as aggregated services. Products from different manufacturers are integrated in the ASSET framework either natively (using an ASSET agent) or via an ASSET proxy. They are controlled and managed through the Media ASSET Bus API, based on XML service schema definitions. This API ensures an easy and seamless integration of devices and products in the framework.

An ASSET Private API is defined to access core services of the framework (common services) that enable the workability of this integrated environment. This API is only used internally in order to guarantee the overall system integrity.

Figure 1

B. ASSET Architecture components

The ASSET Architecture defines a number of concepts, components and functions that enable the implementation of an ASSET Compliant Framework:

The core of the ASSET Framework consists of three main components:

§ The ASSET Public Services expose the mandatory services of the ASSET framework to the applications and the aggregated services through the ASSET Public API. These services provide a minimum set of multimedia functionality, sufficiently rich and extensible to not limit the system efficiency. They ensure the consistency and integrity of the system by handling the internal logic (e.g. access right, resource allocation, etc.) required for each operation. § The ASSET Common Services provide implementation of key infrastructure requirements such as security, logging, notification, resource management, etc. This allows a uniform and single implementation of these services throughout the solution.

C. Media ASSET Bus

Most of the ASSET framework is built above a software bus called the Media ASSET Bus or MAB.

The goal of the MAB is to provide support for the integration of the widest range of products within the ASSET framework, independently of the underlying operating system environments and protocols.

The MAB defines a set of standard interfaces and synchronization process, which ensure a seamless interoperability between ASSET components and products. These interfaces allow any third party media application or product to integrate into the Media ASSET Bus by developing a simple software adapter in an agent or a proxy. A MAB Software Development Kit (SDK) is provided in order to facilitate this task. It gives a uniform way of connecting devices, registering services and exchanging messages within the ASSET framework.

The integrated environment that the MAB offers is based on a Transport Abstraction Layer (TAL), which takes care of message exchanges. Messages have XML format that ensure flexibility and adaptability of the ASSET solution.

The concept of the Media ASSET Bus is illustrated in Figure 2. Different ASSET components and products are interconnected via software adapters on top of the MAB SDK. § The Structural and Control data model, which embraces all data dedicated to the system description (services, functions, security and access rights, etc.). § A Descriptive metadata model, which provides the description of essences available within the framework. § A Content Management metadata model, which describes the location of the media assets and their possible relationships.

MAB Transport Abstraction Layer

Recorder

A. Structural and Control data model

The information stored in the Structural and Control data model is distributed among several common services. The private API provided by the common services allows the creation and update of the data describing the past, present and eventually future state of the framework. For example, the session common service manages the information regarding the past and still active sessions, created by applications to access the framework. The Structural and Control data model is strictly designed to the ASSET framework and embraces the global description of the system and resources.

B. Descriptive metadata model

Almost every broadcaster or production company may have its own workflow and its own proprietary set of metadata describing essences, workflows and processes. Hence, it would not be possible to introduce a descriptive data model coping with these different requirements. As a result, we distinguished technical metadata (e.g. compression type, image size, etc.) from the other descriptive metadata. Some technical metadata, which are required for the ASSET framework, are handled by the technical metadata common service. The other descriptive metadata are handle by descriptive metadata public and function services, based on a default model, which is not compulsory but may guide developer implementation. DMS-1 [START_REF]A guide to MXF Descriptive Metadata Schemes and their application[END_REF][5] is proposed as the default descriptive metadata model.

C. Content Management metadata model

The goal of the Content Management metadata model is to address the need of describing the location and the relationships between files and Media assets. For example, a media asset may have several representations (e.g. same clip with different compression types) each having different structures (e.g. a Media asset may be composed of one physical file or structured as a collection of audio, video and metadata files).

IV. CONTENT EXCHANGE

A. Content Exchange Overview

Associations of public broadcasters like the EBU-SMPTE Task Force [START_REF] Hoffman | Networks and Transfer Protocols[END_REF] have highlighted the requirements to exchange media content in digital television environments, using non-proprietary formats. Different aspects for interoperability were identified. Some of them are:

§ multiple users accessing simultaneously and independently the same content; § various and adaptable speed transfer across scalable network areas; § common container for data and metadata organized in data models; § simple, direct and eventually partial access to the content through standardized network protocols and interfaces; § unified formats for manipulating, managing, storing, sharing and distributing essences and metadata. Emerging content exchange technologies shall satisfy these requirements.

Recently, the Pro-MPEG Forum [START_REF]Pro-MPEG[END_REF] and the Advanced Authoring Format (AAF) Association [8] have developed an open standard that ensures the interoperability among the different vendor systems involved in production environments.

B. MXF -Material eXchange Format

The Material eXchange Format [START_REF]Material eXchange Format (MXF)[END_REF][9] is an Open Standard file format for the interchange of audio-visual materials and associated metadata. This format is compression scheme independent and therefore facilitates the integration of systems using MPEG, DV or other compression strategies, even yet unspecified. This format has actually been designed to address the interoperability requirements and has naturally been applied in the ASSET project. MXF is used for file interchanges within the ASSET framework as well as for the export/import of both essences and metadata, to/from products or applications external to an ASSET framework.

V. DEMONSTRATION PLATFORM A simple demonstration platform is currently under development for IBC 2003. Its goal is to assess and validate the quality of the services and concepts introduced by the ASSET solution. This demonstrator will be a deployment example of the ASSET solution in a common example of TV production, where devices and applications are integrated in a unified system. The planned demonstrator does not focus on a particular workflow, but on how functionalities provided by the framework are supported and how interoperability and connectivity is achieved. The demonstrator uses a client and several products of different manufacturers to emulate simple workflows of a news platform. The client is a media control application used to control ingest, archive, delete or play media content between connected devices. The products are a video server, which allows ingest and playout of clips, an online storage system (repository) and an archive server (nearline storage).

Technical descriptive metadata and content management metadata are stored internally using ASSET common services.

In the demonstration platform, contents can be ingested into the framework via the A/V feed of a video server. Media asset may then be exchanged (e.g. for archiving) using the MXF file format. Descriptive metadata are extracted during the ingest phase and can be retrieved by the system through the ASSET agent of the online storage system. They are actually not permanently stored in a Media Asset Management system (as they should), in order to simplify the demonstration platform.

Using the framework within the above scenario provides a straightforward integration and collaboration of various proprietary applications and devices. The exchange of asset media and metadata becomes transparent through the aid of MXF.

The ASSET demonstrator may also serve as a reference system where application providers, administrators, and integrators are able to test and verify the implemented functionality against the specifications and the requirements.

VI. CONCLUSION

This paper gives an overview of the project approach and describes the work under development in the IST ASSET project. The software architecture is outlined and its components presented. APIs will be made available to manufacturers and applications providers, so that interconnection between equipment and media applications is greatly improved in digital TV environments. The partners have already defined the software architecture, concepts and demonstration scenario and are now working towards the development of the prototype that shall demonstrate the effectiveness of the ASSET solution.

Fig. 2 -

 2 Fig. 2 -Media ASSET Bus

Figure 3 Fig. 3 -

 33 Fig. 3 -ASSET demonstration scenario

ASSET Public API Media ASSET Bus API

  illustrates the different components of the ASSET architecture.

		Application & Business Logic Layer
	ASSET Compliant Application	ASSET Aggregated	ASSET Aggregated
	ASSET Services Library	Service		Service
					ASSET Framework
	Comm on Services • Service Repository • Security • Notification • Debug/logging • Management • Session • Transaction • License	ASSET Private API	ASSET Public Service ASSET Function Service	ASSET Public Service ASSET Function Service	ASSET Public Service ASSET Function Service
	ASSET Proxy	ASSET Agent		ASSET Agent
	Legacy Protocol	ASSET Compliant Product	ASSET Compliant Product
	Legacy Product
					Product Layer
	Fig. 1 -ASSET Architecture
	Adding new applications or products to the framework
	simply requires the writing of a small software adapter to
	conform either to the ASSET Public API or to the Media
	ASSET Bus API.

  Video Server output are considered as two system-wide logical output ports). At the Application and Business Logic layer, three components are introduced: § The ASSET Compliant Applications are the top level ASSET software components. They use the ASSET Public API to access services provided by the ASSET Framework and optionally, by ASSET aggregated services. § The ASSET Services Library is a software component included in (or linked with) an application, which makes it compliant to the ASSET framework and gives it access to the ASSET public services. § The ASSET Aggregated Services implement additional business logic on top of public services (or even other aggregated services). They register in the framework as new services available for ASSET compliant applications (e.g. complex workflows may be specified as aggregated services and then, be available for other connected applications or aggregated services). At the product layer, we call product a manageable hardware or software component that implements one or several common functions (e.g. most of the Video Server products implement a Recorder function, a Player function and a Storage function) and logical components (logical ports, repositories, etc.). Two ways exist to make a product compatible with the ASSET framework: § An ASSET Compliant Product is a product that is managed by the framework through a built-in ASSET Agent. § A Legacy Product is a product that has not (or cannot have) a built-in ASSET agent. The ASSET framework can nonetheless managed such a product through an external software module called an ASSET Proxy (e.g. a VTR cannot include a built-in ASSET agent and has to be connected through an ASSET Proxy). Products communicate with the framework using the API provided by the Media ASSET Bus, which is introduced in the next subsection.

They expose a private API that can be only used by ASSET Public Services. § The ASSET Function Services provide an abstraction of functionalities (encoder, recorder, player, etc.) to the ASSET public services. They hide the specificities of the different interconnected products (e.g. for a public service, a VTR output and a


Cristina Bazgan

Florian Jamain

Daniel Vanderpooten

Approximate Pareto sets of minimal size for multi-objective optimization problems

Keywords: Multi-objective optimization, Pareto set, non-dominated points, approximation algorithm, greedy algorithm

Approximate Pareto sets of minimal size for multi-objective optimization problems

Introduction

In multi-objective optimization, in opposition to single objective optimization, there is typically no optimal solution i.e. one that is best for all the objectives. Therefore, the standard situation is that any solution can always be improved on at least one objective. The solutions of interest, called efficient solutions, are these such that any solution which is better on one objective is necessarily worse on at least one other objective. In other words, a solution is efficient if its corresponding vector of objective values is not dominated by any other vector of objective values corresponding to a feasible solution. These vectors, associated to efficient solutions, are called non-dominated points. For many multi-objective optimization problems, one of the main difficulties is the large cardinality of the set of nondominated points (or Pareto set). Indeed, it is well-known, in particular, that most multi-objective combinatorial optimization problems are intractable, in the sense that they admit families of instances for which the number of non-dominated points is exponential in the size of the instance [START_REF] Ehrgott | Multicriteria Optimization[END_REF]. Thus, instead of producing the full set of non-dominated points, we may prefer to provide an approximation of this set. This idea is represented by the concept of an ε-Pareto set, which is a set P ε of solutions that approximately dominates every other solutions, i.e. such that for every solution s, it contains a solution s ′ that is better within a factor 1+ε than s in all the objectives. The existence of ε-Pareto sets of polynomial size is well-known [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF] and polynomial time algorithms that produce ε-Pareto sets have been developed and improved for many multi-objective optimization problems, including Multi-objective 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], Multi-objective Knapsack [START_REF] Erlebach | Approximating multiobjective knapsack problems[END_REF][START_REF] Bazgan | Solving efficiently the 0-1 multi-objective knapsack problem[END_REF]. However, note that there may exist many ε-Pareto sets, some of which can have very small size and some others very large size. An interesting problem Email addresses: bazgan@lamsade.dauphine.fr (Cristina Bazgan), florian.jamain@lamsade.dauphine.fr (Florian Jamain), vdp@lamsade.dauphine.fr (Daniel Vanderpooten) introduced by [START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF] and continued in [START_REF] Diakonikolas | Small approximate Pareto sets for biobjective shortest paths and other problems[END_REF] is the efficient construction of ε-Pareto sets of size as small as possible. This paper focuses on the same issue.

In the following section, we define the basic concepts, formalize the problem and recall some results of previous related works. Then, in section 3, we mainly propose a new polynomial time 3-approximation algorithm of the size of a smallest ε-Pareto set for the bi-objective case. In section 4, we analyze the performance of the greedy algorithm when the points of the objectives space are given explicitly in the input and the number of objectives is three, answering an open question raised in [START_REF] Koltun | Approximately dominating representatives[END_REF]. We conclude with some possible extensions to this work.

Preliminaries

In this paper, we consider multi-objective optimization problems where we try to minimize several objectives, i.e. min x∈S { f 1 (x), . . . , f p (x)}, where f 1 , . . . , f p are p ≥ 2 objective functions and S is the set of feasible solutions. In the case where some or all objective functions are to be maximized, our results are directly extendable.

We distinguish the decision space X which contains the set S of feasible solutions of the instance and the criterion space Y ⊆ R p which contains the criterion vectors or simply points. We denote by Z = f (S ) ⊆ Y the set of the images of feasible solutions called feasible points.

We denote by y i the coordinate on criterion f i of a point y ∈ Y for i = 1, . . . , p. We say that a point y dominates another point y ′ if y is at least as good as y ′ in all the objectives, i.e. y i ≤ y ′ i for all i = 1, . . . , p. A feasible solution x ∈ S is called efficient if there is no other feasible solution x ′ ∈ S such that f (x) f (x ′ ) and f (x ′ ) dominates f (x). If x is efficient, z = f (x) is called a non-dominated point in the criterion space. We denote by P the set of non-dominated points, called Pareto set.

Given a constant c ≥ 1, a point y c-dominates another point y ′ if y is at least as good as y ′ up to a factor of c in all the objectives, i.e. y i ≤ cy ′ i . For any rational ε > 0, an ε-Pareto set P ε is a subset of feasible points such that for all z ∈ P, there exists z ′ ∈ P ε such that z ′ (1 + ε)-dominates z. In the context of ε-Pareto sets, the central relation is the (1 + ε)-dominance relation, denoted by ε .

For a given instance I, there may exist several ε-Pareto sets, and these may have different sizes. It is shown in [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF] that, for every classical multi-objective optimization problem, an ε-Pareto set of size polynomial in the input size and 1/ε always exists. Moreover its computation is related to the computation of the following routine GAP δ .

Given an instance I of a given problem, a point y and a rational δ ≥ 0, the routine GAP δ (y) either returns a feasible point that dominates y or reports that there does not exist any feasible point z such that z i ≤ y i 1+δ for all i = 1, . . . , p. We say that routine GAP δ (y) runs in polynomial time (resp. fully polynomial time when δ > 0) if its running time is polynomial in |I| and |y| (resp. |I|, |y|, |δ| and 1/δ). An ε-Pareto set is computable in polynomial time (resp. fully polynomial time) if and only if the routine GAP δ runs in polynomial time (resp. fully polynomial time) [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF].

Since an ε-Pareto set of polynomial size can still be quite large, Vassilvitskii and Yannakakis investigate in [START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF] the determination of ε-Pareto sets of minimal size. These authors also propose generic algorithms to deal with this problem. An algorithm is called generic if it does not depend on any particular problem and makes use of general purpose routines for which only the implementation is specific to the problem (GAP δ is such a general purpose routine). In such algorithms it is only required to have bounds on the minimum and maximum values of the objective functions. Assuming in the following that the objective functions take positive rational values whose numerators and denominators have at most m bits, any feasible point has a value between 2 -m and 2 m and moreover the difference between the values of any two solutions is at least 2 -2m for any criterion. From [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF], opt ε is polynomial in the input size and 1/ε.

In order to use generic algorithms, Diakonikolas and Yannakakis introduced in [START_REF] Diakonikolas | Small approximate Pareto sets for biobjective shortest paths and other problems[END_REF] two other general purpose routines called Restrict δ and DualRestrict δ for the bi-objective case.

Given an instance I, a bound b and a rational δ ≥ 0, the routine Restrict δ ( f 1 , f 2 ≤ b) either returns a feasible point z satisfying z 2 ≤ b and z 1 ≤ (1 + δ). min{ f 1 (x) : x ∈ S and f 2 (x) ≤ b} or correctly reports that there does not exist any feasible point z such that z 2 ≤ b.

Given an instance I, a bound b and a rational δ ≥ 0, the routine DualRestrict δ ( f 1 , f 2 ≤ b) either returns a feasible point z satisfying z 2 ≤ b(1+δ) and z 1 ≤ min{ f 1 (x) : x ∈ S and f 2 (x) ≤ b} or correctly reports that there does not exist any feasible point z such that z 2 ≤ b.

We say that routine

Restrict δ ( f 1 , f 2 ≤ b) or DualRe- strict δ ( f 1 , f 2 ≤ b)
( f 1 , f 2 ≤ b) and DualRestrict δ ( f 2 , f 1 ≤ b ′ )
are polynomially equivalent as proved in [START_REF] Diakonikolas | Small approximate Pareto sets for biobjective shortest paths and other problems[END_REF].

In the routines considered in this paper we assume that the error δ is a rational number, otherwise it is approximated from below by a rational number. We denote by P * ε a smallest ε-Pareto set and by opt ε its cardinality. It follows from [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF] that opt ε is polynomial in the input size and 1/ε. We are interested in generic algorithms that compute in polynomial time an ε-Pareto set of minimal size. For the biobjective case, a generic algorithm that computes an ε-Pareto set of size at most 3opt ε was established in [START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF] using routines GAP δ . Moreover, if the routine GAP δ runs in polynomial time (resp. fully polynomial time) then the algorithm also runs in polynomial time (resp. fully polynomial time). Then, it is shown in [START_REF] Diakonikolas | Small approximate Pareto sets for biobjective shortest paths and other problems[END_REF] that an ε-Pareto set of size at most 2opt ε is computable in polynomial time if there exists routines Restrict δ computable in polynomial time for both objectives. These approximation results are tight for the class of problems admitting such routines. An algorithm that computes an ε-Pareto set of size at most k.opt ε is called a k-approximation algorithm.

Two objectives

We first present a hardness result for the Bi-objective Knapsack problem then we propose a new generic algorithm that approximates the size of a smallest ε-Pareto set to a factor 3, which is much simpler and, in some cases, more efficient than the one presented in [START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF].

Approximation hardness for Bi-objective Knapsack

Diakonikolas and Yannakakis [START_REF] Diakonikolas | Small approximate Pareto sets for biobjective shortest paths and other problems[END_REF] showed that the size of a smallest ε-Pareto set of Bi-objective Shortest Path and Biobjective Spanning Tree cannot be approximated within a factor better than 2 in polynomial time, unless P = NP. These results are tight since these two problems admit a routine Restrict δ that runs in polynomial time, and thus an ε-Pareto set of size at most 2opt ε is computable in polynomial time as shown in [START_REF] Diakonikolas | Small approximate Pareto sets for biobjective shortest paths and other problems[END_REF]. Vassilvitski and Yannakakis [START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF] showed that the size of a smallest ε-Pareto set of an artificial variant of Knapsack, called Biobjective 2-Type-Knapsack, cannot be approximated within a factor better than 3 in polynomial time, unless P = NP. This result is also tight since this problem has a routine GAP δ that runs in polynomial time, and thus an ε-Pareto set of size at most 3opt ε is computable in polynomial time as shown in [START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF].

In this part, we investigate the status of the classical version, called Bi-objective Knapsack, with as input a set Q of items, a capacity c and for each item i two values v 1 (i), v 2 (i) and a weight w(i). Values and weights are positive rationals. A solution is a nonempty subset

Q ′ of items with total values v 1 (Q ′ ) = i∈Q ′ v 1 (i), v 2 (Q ′ ) = i∈Q ′ v 2 (i) and a total weight w(Q ′ ) = i∈Q ′ w(i) ≤ c.
The goal is to maximize the values. First, note that the size of a smallest ε-Pareto set of Bi-objective Knapsack is approximable in polynomial time to a factor 3 since this problem admits an FPTAS, which is equivalent to the existence of a polynomial time routine GAP δ [START_REF] Erlebach | Approximating multiobjective knapsack problems[END_REF]. We prove that the size of a smallest ε-Pareto set of Bi-objective Knapsack is not approximable in polynomial time within a factor better than 3, if P NP.

Theorem 1. For Bi-objective Knapsack the size of a smallest ε-Pareto set cannot be approximated within a factor better than 3 in polynomial time, unless P = NP.

Proof : We construct a gap-preserving reduction from the Partition problem. Thus, from any instance I of Partition, we construct an instance I ′ of Bi-objective Knapsack such that if the answer of I is 'yes' then the size of the smallest ε-Pareto set of I ′ is 1 and if the answer of I is 'no' then the size of the smallest ε-Pareto set of I ′ is 3. Recall that in Partition, the input is a set N of n positive integers a 1 , . . . , a n , and we have to determine if it is possible to partition N into two subsets with equal sum. Starting with such an instance we construct an instance of Bi-objective Knapsack as follows. Let b = n i=1 a i /2. For each i = 1, . . . , n, we have one item i with values v 1 (i) = v 2 (i) = a i and weight w(i) = a i . In addition, we have two special items α and

β with v 1 (α) = (1 + ε)b, v 2 (α) = 0, w(α) = b and v 1 (β) = 0, v 2 (β) = (1 + ε)b, w(β) = b. The capacity of the knapsack is b.
Note that if a solution contains a special item, it cannot contain any other item. Let z α and z β be the points corresponding to the solution with special item α and β respectively. Consider now solutions without special items. The corresponding points having the same value on each criterion, let z * be the point with the largest value v * on each criterion. z * dominates all other such points.

If I is a 'yes' instance, we have v * = b. Thus, z * (1 + ε)dominates both z α and z β , and {z * } is an ε-Pareto set. If I is a 'no' instance, we have v * < b. Thus z α and z β must make part of any ε-Pareto set and {z * , z α , z β } is a smallest ε-Pareto set. ✷ Remark that we can generalize the previous result, proving that for p-objective Knapsack with p ≥ 2 the size of a smallest ε-Pareto set cannot be approximated within a factor better than p + 1 in polynomial time, unless P = NP.

A new 3-approximation algorithm

We propose in this section a new 3-approximation algorithm, based on another routine called SoftRestrict δ .

Given a positive rational bound b and a parameter δ > 0, the routine SoftRestrict δ ( f 1 , f 2 ≤ b) either returns a feasible point z satisfying z 2 ≤ (1 + δ)b and z 1 ≤ (1 + δ). min{ f 1 (x) : x ∈ S and f 2 (x) ≤ b} or correctly reports that there does not exist any feasible point z such that z 2 ≤ b.

We say that a routine SoftRestrict δ ( f 1 , f 2 ≤ b) runs in polynomial time (resp. fully polynomial time when δ > 0) if its running time is polynomial in |I| and |b| (resp. |I|, |b|, |δ| and 1/δ).

Remark that a routine SoftRestrict δ ( f 1 , f 2 < b), with a strict constraint, can easily be simulated by a routine SoftRe-

strict δ ( f 1 , f 2 ≤ b ′ ) using b ′ = b -2 -2m .
Such a routine was proposed for several problems. For instance, for the Bi-objective Spanning Tree problem, the running time of the routine presented in [START_REF] Hong | A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem[END_REF] is O(mn 5 τ(⌊(n -1)/δ⌋, ⌊(n -1)/δ⌋)) where n is the number of vertices in the graph, m the number of edges in the graph and τ(a, b) is the time to multiply polynomials of maximum degrees less than or equal to a and b. For a Bi-objective Single Machine Scheduling problem, the running time of the routine presented in [START_REF] Cheng | Bicriterion single machine scheduling with resource dependent processing times[END_REF] is

O(n 5 R/(δ 3 L))
where n is the number of jobs, L and R are respectively lower and upper bounds on the first coordinate of an optimal solution. For Bi-objective Bipartite Matching, the running time of the routine presented in [START_REF] Grandoni | New approaches to multiobjective optimization[END_REF] is O(m O(1/δ 2 ) ) where m is the number of edges in the graph.

Our approximation algorithm has the same approximation ratio as the algorithm presented in [START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF] but is much simpler, both in its description and in its proof, owing to the use of the routine SoftRestrict δ instead of GAP δ . Its running time is comparable to the one of [START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF] and better under some conditions.

Before presenting and analyzing this new 3-approximation algorithm, we first compare the two routines GAP and SoftRestrict.

Proposition 1. The routines SoftRestrict and GAP are polynomially equivalent.

Proof : We first show that we can answer to GAP δ (y) us-

ing SoftRestrict δ ( f 1 , f 2 ≤ y 2 /(1 + δ)). Indeed, if SoftRe- strict δ ( f 1 , f 2 ≤ y 2 /(1 + δ)) returns NO or returns a feasible point z with z 1 > y 1 , we return NO and if SoftRestrict δ ( f 1 , f 2 ≤ y 2 /(1 + δ)) returns a feasible point z with z 1 ≤ y 1 we return z.
We give in the following an algorithm that computes the function SoftRestrict

δ ( f 1 , f 2 ≤ b) using a polynomial num- ber of calls to GAP δ ′ where δ ′ = √ 1 + δ -1. We first call GAP δ ′ ((1 + δ ′ )2 m , (1 + δ ′ )b). If it returns NO, then we also re- turn NO for SoftRestrict δ ( f 1 , f 2 ≤ b).
Otherwise, we partition the objective space by defining intervals, on the first objective, from 2 -m /(1 + δ ′ ) to 2 m such that the ratio between the upper and lower bounds of each interval is 1 + δ ′ . We perform a binary search on the upper bounds of the previous intervals calling GAP δ ′ (a, (1 + δ ′ )b) for some a until one finds a value a * such that (i) GAP δ ′ (a * (1 + δ ′ ), (1 + δ ′ )b) returns a feasible point z * and (ii) GAP δ ′ (a * , (1 + δ ′ )b) returns NO. Then we return z * .

The number of subdivisions on the first coordinate is 2m/ log(1 + δ ′ ) ≈ Θ(4m/δ ′ ). Hence, the number of calls to

GAP δ ′ is Θ(log(m/δ ′ ))=Θ(log(m/δ)). ✷ Corollary 1.
Consider the class of bi-objective problems that possess a fully polynomial time routine SoftRestrict δ with δ > 0 for both objectives. Then, for any ε > 0, there is no polynomial time generic algorithm using SoftRestrict δ that computes an ε-Pareto set of size less than or equal to 3opt ε .

Proof : Follows from Proposition 1 and the fact that the same result holds for the routine GAP δ [START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF]. ✷ Algorithm description. We first describe briefly the idea of the algorithm. We compute f min 1 and f min 2 which represent lower bounds on the minimum values on the first and second objectives using SoftRestrict δ . The algorithm iteratively generates a sequence of points r 1 , q 1 , . . . , r s , q s . Points q 1 , . . . , q s are selected in decreasing order according to f 1 and increasing order according to f 2 . Point q 1 is selected so as to (1 + ε)-dominate the feasible points that have an optimal second coordinate while getting the best possible value on f 1 . The algorithm stops when it generates a point q s that (1 + ε)-dominates the feasible points Algorithm 1: Algorithm SoftGreedy input : An instance of a bi-objective problem for which routines SoftRestrict

δ ( f 1 , f 2 ≤ b) and SoftRestrict δ ( f 2 , f 1 ≤ b) are available output : An ε-Pareto set of size at most 3opt ε 1 f min 1 ← f 1 (SoftRestrict δ ( f 1 , f 2 ≤ 2 m ))/(1 + δ); f min 2 ← f 2 (SoftRestrict δ ( f 2 , f 1 ≤ 2 m ))/(1 + δ); 2 r 1 ← SoftRestrict δ ( f 2 , f 1 ≤ 2 m ); 3 f 2 1 ← 1+ε (1+δ) 2 r 1 2 ; 4 q 1 ← SoftRestrict δ ( f 1 , f 2 ≤ f 2 1 ); 5 f 1 1 ← q 1 1 /(1 + ε); 6 Q ← {q 1 }; 7 i ← 1; 8 while f 1 i > f min 1 do 9 i ← i + 1; 10 r i ← SoftRestrict δ ( f 2 , f 1 < f 1 i-1 ); 11 f 2 i ← 1+ε 1+δ max{ f 2 i-1 , r i 2 /(1 + δ)}; 12 q i ← SoftRestrict δ ( f 1 , f 2 ≤ f 2 i ); 13 if q i 1 > r i 1 then 14 q i ← r i ; 15 f 1 i ← q i 1 /(1 + ε); 16 Q ← Q ∪ {q i }; 17 return Q;
that have a first coordinate equal to f min 1 . Routines SoftRestrict δ ( f 2 , f 1 ≤ b) and SoftRestrict δ ( f 1 , f 2 ≤ b) are alternatively used to construct points r i and points q i respectively. Point r i is a point with a smallest second coordinate that we can determine with the routine SoftRestrict δ that is not (1 + ε)/(1 + δ)dominated by the points q j with j < i. Point q i is a point with a smallest first coordinate that we can determine with routine SoftRestrict δ that (1 + ε)-dominates point r i . A formal description of this algorithm is given in Algorithm 1.

In order to obtain a 3-approximation algorithm, we consider in the following that δ ≤ 3 √ 1 + ε -1. Before analyzing this algorithm, we illustrate its behavior in Figure 1 where 3 points q 1 , q 2 , q 3 are selected by Algorithm 1 in order to cover the part of the objective space with first objective value at least f 1 3 , whereas only one point, p * 1 , is sufficient. Algorithm analysis. We show now that Algorithm 1 produces a 3-approximation of the size of a smallest ε-Pareto set. Let Q = {q 1 , . . . , q s } and R = {r 1 , . . . , r s } be the sets of feasible points produced by the algorithm. We show in the following that set Q is an ε-Pareto set, then that its size is at most three times the size of P * ε , an ε-Pareto set of minimal size. The proof is essentially the same as the one in [START_REF] Diakonikolas | Small approximate Pareto sets for biobjective shortest paths and other problems[END_REF] for the 2-approximation algorithm. We first show some preliminarily results regarding points in Q and R. Lemma 1. For all i = 2, . . . , s we have (i) r i 1 < q i-1 1 (1 + δ)/(1 + ε) and (ii) for each feasible point z with z 1 < q i-1

1 /(1 + ε), we f 2 f 1 f 2 1 r 1 q 1 f 1 1 r 2 f 2 2 p * 1 q 2 f 1 2 r 3 (1 + δ) f 2 2 q 3 (1 + δ) f 2 1 f 1 3 f 2 3 (1 + δ) f 2 3 p * 1 1 1+ε p * 1 2 1+ε f min 2 f min 1 . . .
+ δ = 3 √ 1 + ε have z 2 ≥ max{ f 2 i-1 , r i 2 /(1 + δ)}.
Proof : This results from the definition of the routine SoftRestrict δ and steps 10-12 and 15 of the algorithm. ✷ Lemma 2. For all i = 1, . . . , s we have (i)

q i 2 ≤ (1 + δ) f 2 i and (ii) for each feasible point z with z 2 ≤ f 2 i , we have z 1 ≥ q i 1 /(1 + δ).
Proof : This results from the definition of the routine SoftRestrict δ and steps 10-12 of the algorithm. ✷

We can now prove the following result.

Proposition 2. Set Q is an ε-Pareto set.

Proof : We show that the points in Q cover all the feasible points by partitioning the range of feasible values on f 1 . More precisely, we show that: (i) Point q 1 (1 + ε)-dominates all the feasible points with an f 1 value greater than or equal to q 1 1 /(1 + ε). (ii) For each i = 2, . . . , s point q i (1 + ε)-dominates all the feasible points that have their f 1 value in the interval q i 1 /(1 + ε), q i-1 1 /(1 + ε) . (iii) There is no feasible point with a f 1 value smaller than q s 1 /(1 + ε). (i) Let z be a feasible point with z 1 ≥ q 1 1 /(1 + ε). We need to show that z is (1 + ε)-dominated by q 1 , i.e. that z 2 ≥ q 1 2 /(1 + ε). From steps 2-4 we get where q 1 2 ≤ r 1 2 (1+ε)/(1+δ) ≤ f min 2 (1+ε) and thus q 1 2 /(1

+ ε) ≤ f min 2 ≤ z 2 . (ii) Let z be a feasible point satisfying q i 1 /(1 + ε) ≤ z 1 < q i-1 1 /(1 + ε). We need to show that z is (1 + ε)-dominated by q i , i.e. that z 2 ≥ q i 2 /(1 + ε). From Lemma 1-(ii) we have z 2 ≥ max{ f 2 i-1 , r i 2 /(1 + δ)}. Furthermore from Lemma 2-(i) we have q i 2 ≤ (1 + δ) f 2 i . Hence, from the definition of f 2 i (step 11), we get q i 2 ≤ max{ f 2 i-1 , r i 2 /(1 + δ)} ≤ (1 + ε)z 2 . (iii) The stopping condition of the algorithm (step 8) is f 1 s = q s 1 /(1 + ε) ≤ f min 1 . ✷
We show now that the size of Q is at most three times the size of an optimal ε-Pareto set.

Proposition 3. Set Q is such that |Q| ≤ 3opt ε .
Proof : Let P * ε = {p * 1 , . . . , p * k } be an optimal ε-Pareto set, where its points p * i for i = 1, . . . , k are in increasing order of their coordinates on f 2 and decreasing order of their coordinates on f 1 . We have to show that |Q| ≤ 3k. For this purpose, we show by induction on i that if the algorithm selects a feasible point q 3i-2 then there must exist a point p * i in P * ε , if the algorithm selects a point q 3i-1 then p * i 1 (1 + δ) ≥ q 3i-1 1 and if the algorithm selects a point q 3i then p * i 1 > (1 + δ)q 3i 1 . Initialization (i = 1). The first statement trivially holds. To prove the second statement we first show that p * 1 2 ≤ f 2

2

. Since the feasible point r 1 must be (1 + ε)-dominated by a point of P * ε and in particular by point p * 1 , we have p * 1 2 ≤ r 1 2 (1+ε). From the definitions of f 2 1 and f 2 2 (step 11) and using that δ

≤ 3 √ 1 + ε-1, we have r 1 2 (1 + ε) = f 2 1 (1 + δ) 2 ≤ f 2 2 . Using that p * 1 2 ≤ f 2 2 and Lemma 2-(ii) we obtain p * 1 1 (1 + δ) ≥ q 2 1 .
Since we have q 3 1 ≤ r 3 1 (steps 13 and 14) Lemma 1-(i) implies that q 3 1 < q 2 1 (1+δ)/(1+ε), and so that the third statement is a consequence of the second one, considering that δ ≤ 3 √ 1 + ε -1. Induction step. Assume the result is true until index i -1, we prove it for index i. First, if the algorithm selects a point q 3i-2 , we show that P * ε contains a point p * i . By the termination condition of the algorithm (step 8), we have

q 3i-3 1 > (1 + ε) f min 1
and by the induction hypothesis that p * i-1

1 > (1 + δ)q 3i-3 1 , it follows that p * i-1 1 > (1+δ)(1+ε) f min
1 . Thus, point p * i-1 does not (1 + ε)-dominate the feasible points that have a minimum first coordinate, and so P * ε must contain another point p * i . To prove the second statement we first show that p * i 2 ≤ f 2 3i-1

. Since the feasible point r 3i-2 must be (1 + ε)-dominated by a point of P * ε and in particular by point p * i , we have

p * i 2 ≤ r 3i-2 2 (1 + ε). From the definitions of f 2 3i-2
and f 2 3i-1 (step 11) and using that δ

≤ 3 √ 1 + ε -1, we have r 3i-2 2 (1 + ε) ≤ f 2 3i-2 (1 + δ) 2 ≤ f 2 3i-1 . Using that p * i 2 ≤ f 2 3i-1
and Lemma 2-(ii) we obtain p * i 1 (1 + δ) ≥ q 3i-1 1 . Since we have q 3i 1 ≤ r 3i 1 (steps 13 and 14) Lemma 1-(i) implies that q 3i 1 < q 2i-1 1 (1 + δ)/(1 + ε), and so that the third statement is a consequence of the second one, considering that δ

≤ 3 √ 1 + ε-1. ✷
Combining the previous results, we obtain the main result of this section.

Theorem 2. Algorithm 1 computes an ε-Pareto set of size less than or equal to 3opt

ε using O(opt ε ) routine calls to SoftRestrict δ , when δ ≤ 3 √ 1 + ε -1.

Proof :

The result is a direct consequence of Propositions 2 and 3. Since the algorithm uses 2 |Q| times the routine SoftRestrict δ , the number of routine calls is bounded by 6opt ε . ✷

Comparison to existing algorithms. For the class of problems admitting a routine GAP that runs in polynomial time, the algorithm of Vassilvitski and Yannakakis presented in [START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF] was the only one ensuring some guarantee on the size of the returned ε-Pareto set. This algorithm, called ZIGZAG is a generic algorithm based on the routine GAP, that establishes a 3approximation of the size of a smallest ε-Pareto set and it needs O(opt ε • log(m/ε)) routine calls. Since algorithm ZIGZAG and our algorithm run in polynomial time for the same class of problems and give the same approximation ratio of a smallest ε-Pareto set we can compare them with regard to their running times. The running time of a generic algorithm is defined as the product between the number of routine calls and the running time of the routine called. This way, the running time of algorithm

ZIGZAG is O(opt ε • log(m/ε)) • T GAP δ with δ = 4 √ 1 + ε -1 and the running time of our algorithm Soft- Greedy is O(opt ε ) • T SoftRestrict δ with δ = 3 √
1 + ε -1 where T GAP δ and T SoftRestrict δ are the running times of the routines GAP δ and SoftRestrict δ respectively.

The running times of algorithms SoftGreedy and ZIGZAG are comparable since we can solve the routine SoftRestrict δ using Θ(log(m/ε)) calls to GAP δ ′ with δ ′ = √ 1 + δ -1 (see the proof of Proposition 1). Moreover, if we can solve faster the routine SoftRestrict δ , the running time of algorithm SoftGreedy will be smaller than the one of algorithm ZIGZAG. Especially, if the best known algorithm to solve GAP δ solves SoftRestrict δ in the same time, we gain the time of the binary searches. It is the case for Bi-objective Spanning Tree since the algorithm in [START_REF] Hong | A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem[END_REF] that solves SoftRestrict δ is the best known to solve GAP δ .

More than two objectives

Computing small ε-Pareto sets for problems with p ≥ 3 objectives raises specific difficulties.

A first type of difficulties is related to the power or availability of the routines. In [START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF], Vassilvitski and Yannakakis showed that any generic algorithm based on routine GAP δ cannot establish a c-approximation of the size of a smallest ǫ-Pareto set for any constant c. Using SoftRestrict δ instead of GAP δ leads to the same result since the two routines are polynomially equivalent (see Proposition 1, whose proof for 2 objectives can be generalized straightforwardly for p objectives).

Therefore, in order to obtain stronger results, it is necessary to resort to routines involving less tolerance, such as the extended versions, for p objectives, of Restrict δ or DualRestrict δ . First remark that extended Restrict δ is more demanding than extended DualRestrict δ since the tolerance δ is represented only once in the objective to be minimized in Restrict δ whereas it is present in the p -1 constraints in DualRestrict δ . This is confirmed by known results [START_REF] Grandoni | New approaches to multiobjective optimization[END_REF], where it is shown that, for p ≥ 3, there is no polynomial-time routine Restrict δ for classical problems like Multi-objective Shortest Path, Multiobjective Spanning Tree, Multi-objective Perfect Matching, whereas, for instance, there exists a polynomial-time routine DualRestrict δ for Multi-objective Spanning Tree. Therefore, an interesting problem is to devise a generic procedure to generate an ε-Pareto set of smallest size for a p-criteria problem, using DualRestrict δ .

A second type of difficulties is related to the way of exploring objective spaces with more than two objectives. It should be noticed that, in the bi-objective case, non-dominated points can be sorted such that their objective values are increasing in one objective and decreasing in the other objective. This order is used in algorithms generating small ε-Pareto sets, including our algorithm SoftGreedy. The non-existence of such an order for p ≥ 3 makes the exploration of the objective space much more difficult.

Owing to the previous difficulties, we focus in this section on the simple case where the feasible points are given explicitly in the input. In this case, we can easily filter out the dominated points and thus we consider in the following that the input contains non-dominated points only.

In this context, when p = 3, the problem of finding an ε-Pareto set of smallest size is c-approximable, for some constant c [START_REF] Koltun | Approximately dominating representatives[END_REF]. Moreover, for any number of criteria, there exists an O(log n)-approximation since our problem reduces to Set Cover, for which the greedy algorithm provides an O(log n)approximation. An interesting open question, raised by Koltun and Papadimitriou in [START_REF] Koltun | Approximately dominating representatives[END_REF], is to known whether the greedy algorithm performs better on the very specific instances of our problem. We provide an negative answer in Theorem 3. Recall that the greedy algorithm iteratively selects the point that covers the largest number of non-covered points.

Note that for 2 criteria, the greedy algorithm gives a 2approximation, but it is not really satisfying because the algorithm of Diakonikolas and Yannakakis [START_REF] Diakonikolas | Small approximate Pareto sets for biobjective shortest paths and other problems[END_REF] finds an optimal solution when the points are given explicitly in the input. Theorem 3. For p ≥ 3 objectives, when the feasible points are given explicitly in the input, the solution set produced by the greedy algorithm for Set Cover has a size Θ(log n) • opt ε in the worst case.

Proof : We prove the result for p = 3. The result clearly extends to p ≥ 4 since we can consider the same points extended with the last p -3 coordinates to 0. In order to prove it, we give a family of instances where the algorithm produces a Θ(log n)approximation. Let a, b, c be three nonnegative integers, n = 2 ℓ and consider N = 2 ℓ + ℓ -3 = n + log n -3 non-dominated points in the criterion space, defined as follows.

For all i = 1, . . . , log n -

1 let z i = ( a (1+ε) i/(log n-1) , b (1+ε) i/(log n-1) , c(1 + ε) i-1 log n-1 +1 ), Γ i be a set of n 2 i+1
points lying uniformly on the line from (a, b (1+ε andΓ ′ i be a set of n 2 i+1 points lying uniformly on the line from ( Note that if the coordinates of points z i are not rational, we approximate its coordinates from below by rational ones. Moreover, if the coordinates of points in Γ ∪ Γ ′ are not rational, we approximate its coordinates from above by rational ones.

) (i-1)/(log n-1)+1 -1, c(1 + ε) i-1 log n-1 ) to (a(1 + ε), b (1+ε) i/(log n-1)+1 , c(1 + ε) i-1 log n-1 ) if i log n -1 and be the singleton {(a, b (1+ε) (i-1)/(log n-1)+1 -1, c(1 + ε) i-1 log n-1 )} if i = log n -1,
a (1+ε) (i-1)/(log n-1)+1 -1, b, c(1 + ε) i-1 log n-1 ) to ( a (1+ε) i/(log n-1)+1 , b(1 + ε), c(1 + ε) i-1 log n-1 ) if i log n -
Let ξ = ∪ i {z i } and Γ = ∪ i Γ i , Γ ′ = ∪ i Γ ′ i . We can set a, b, c sufficiently large to have the following (1 + ε)-dominance relations:

(i) for any z i , z j ∈ ξ, z i ε z j (ii) for any i, j = 1, . . . , log n -1, for any z ∈ Γ j ∪ Γ ′ j , z i ε z if and only if i = j (iii) for any z, z ′ ∈ Γ, z ε z ′ (iv) for any z, z ′ ∈ Γ ′ , z ε z ′ (v) for any z ∈ Γ, z ′ ∈ Γ ′ , z ε z ′ and z ′ ε z

We show in the following that the greedy algorithm selects the points z i , i = 1, . . . , log n -1 in this order. The proof is by induction on i.

Initialization (i=1). Note that |Γ| = |Γ ′ | = n 2 -1. From (v) it follows that any point in Γ ∪ Γ ′ (1 + ε)-dominates at most n 2 + log n -2 points. From (i) and (ii) point z i (1 + ε)-dominates exactly the points in ξ ∪ Γ i ∪ Γ ′ i , where |ξ ∪ Γ i ∪ Γ ′ i | = n 2 i + log n -1. In particular point z 1 (1 + ε)-dominates n 2 + log n -1 points. Therefore, point z 1 is the first point selected by the greedy algorithm.

Induction step. Assuming that the first i -1 points selected by the greedy algorithm are z 1 , . . . , z i-1 , we prove that the next one is point z i . The points (1+ε)-dominated by {z 1 , . . . , z i-1 } are exactly the points in ξ ∪ (∪ i-1 j=1 (Γ j ∪ Γ ′ j )). Therefore, any point in Γ ∪ Γ ′ (1 + ε)-dominates exactly | ∪ log n-1 j=i (Γ j ∪ Γ ′ j )| = n 2 i -1 points that are not already covered. Point z i exactly (1 + ε)dominates, among the non-covered points, the points in Γ i ∪ Γ ′ i where |Γ i ∪ Γ ′ i | = n 2 i . Thus point z i is selected by the greedy algorithm at step i.

Observe now, that the first point of Γ 1 (1 + ε)-dominates all the points in ξ. Thus, from (iii) and (iv), it follows that a set constituted by the first point of Γ 1 and any point in Γ ′ (1 + ε)dominate the N points. Therefore, the greedy algorithm returns a set of points of size log n -1 while an optimal set of points contains only two points. ✷

Conclusions

We investigated the problem of computing small ε-Pareto sets for multiobjective problems. While the situation is clear for bi-objective problems, it remains challenging for problems involving at least three objectives. In this latter case, even when the points are given explicitly in the input, it is NP-hard to determine an ε-Pareto set of minimal size, but there exists a 100approximation of the size of a smallest ε-Pareto set [START_REF] Koltun | Approximately dominating representatives[END_REF]. A natural open question is to narrow the large gap between lower and upper bounds.

Figure 1 :

 1 Figure 1: Illustration of Algorithm 1 with 1 + δ =

  1 and be the singleton {(

a

  (1+ε) (i-1)/(log n-1)+1 -1, b, c(1 + ε) i-1 log n-1 )} if i = log n -1.

  runs in polynomial time (resp. fully polynomial time when δ > 0) if its running time is polynomial in |I| and |b| (resp. |I|, |b|, |δ| and 1/δ). Routines Restrict δ

Acknowledgments

This work was supported by the French ANR project ANR-09-BLAN-0361 "GUaranteed Efficiency for PAReto optimal solutions Determination (GUEPARD)".