Pierre-Emmanuel Arduin
email: pierre-emmanuel.arduin@lamsade.dauphine.fr

Michel Grundstein
email: mgrundstein@mgconseil.fr

Elsa Negre
email: elsa.negre@lamsade.dauphine.fr

Camille Rosenthal-Sabroux
email: camille.rosenthal-sabroux@lamsade.dauphine.fr

Formalizing an empirical model: a way to enhance the communication between users and designers

This paper introduces a formalization of the Data, Information, Tacit and Explicit Knowledge process (DITEK) empirical model. This formalization reduces the gap between empirical and formal worlds, what led us to consider it as an opportunity to enhance the communication between users and designers of digital information systems. Notably, the designer will be aware of the role of the user as a component of the Enterprise's Information and Knowledge System (EIKS), defined in this paper.

We highlight how having two models, empirical and formal, for the same concept can constitute an outline in order (i) to enhance the communication between users and designers of digital information systems, (ii) to regard users as components of the EIKS, and (iii) to promote information systems' innovative design.

I. INTRODUCTION

Many people associate the term Knowledge Management (KM) with some kind of technological term. It is very often reduced to simple IT-based systems, which offer basic functionality to share the documents and informations among the employees of the company. It is based on a wrong assumption that knowledge can be gathered and managed in the same manner as informations -processed, transferred and stored. Knowledge can be very often mistaken with information. What is the difference then?

In the following, we introduce, Section II, the three postulates on which our researches rely on. Then, Section III, we present the user-centered Enterprise's Information and Knowledge System (EIKS) concept. Section IV details the differences between the concepts of data, information, tacit and explicit knowledge within DITEK and its formalized model is proposed. After discussion, Section V, the last section concludes this paper and presents our future work.

To do that research we have three motivations: First, we want to consolidate the Data, Information, Tacit and Explicit Knowledge process (DITEK) empirical model. We can insure that this empirical model is consistent and not ambiguous and can be described more precisely. Second, with a formalized model we improve the communication between people who work on a socio-technical and IT world. Usually these two worlds do not understand each others. Third, the formalized model can improve the commensurability of interpretative frameworks between users and designers.

II. OUR THREE FUNDAMENTAL POSTULATES: RELATED

WORKS

For us, knowledge has to be considered as a crucial resource. [START_REF] Stewart | Brain power: how intellectual capital is becoming America's most valuable asset[END_REF] pointed out the necessity of considering company's knowledge as an essential resource and has announced a new challenge: "The challenge is to find out what you have -and use it". He even notices the fatal effects of "contents" oriented processes which were not subjected to advisability studies: "Companies waste billions on knowledge management because they fail to figure out what knowledge they need, or how to manage it." [START_REF]The wealth of knowledge: Intellectual capital and the twenty-first century organization[END_REF].

KM is often looked from a technological viewpoint, which leads to consider knowledge as an object and disregard the importance of people. To avoid this, in 2001, the CCRC ECRIN Working Group defines KM as follows: "KM is the management of the activities and the processes that enhance the utilization and the creation of knowledge within an organization, according to two strongly interlinked goals, and their underlying economic and strategic dimensions, organizational dimensions, socio-cultural dimensions, and technological dimensions: (I) a patrimony goal, and (II) a sustainable innovation goal.".

Our work relies on this definition of KM and on three postulates [START_REF] Rosenthal-Sabroux | A global vision of information management[END_REF]: (A) Knowledge is not an object, (B) Knowledge is linked to the action, and (C) Company's knowledge includes two main categories of knowledge. These postulates are defined below.

A. Knowledge is not an object

When [START_REF] Polanyi | Sense-giving and sense-reading[END_REF] introduces the concepts of sense-giving and sense-reading, we simply observe that we continuously appropriate information which is not ours. As the authors of this paper, we have got tacit knowledge that we have structured into information during a process of sense-giving. As the readers Fig. 1. Tacit knowledge transfer of this paper, you have interpreted this information perceiving forms and colors, integrated words, data, during a process of sense-reading, possibly creating new tacit knowledge for you (see Figure 1). A person P 1 creates information when he/she structures his/her tacit knowledge and externalizes it. A person P 2 possibly creates new tacit knowledge when he/she perceives some data from this information and internalizes it. Knowledge is thus the result of the interpretation by someone of information, this interpretation is done through an interpretative framework [START_REF] Tsuchiya | Improving knowledge creation ability through organizational learning[END_REF].

If the probability that two people will give the same meaning to the same information is high, it is said that their interpretative frameworks have a strong commensurability or are commensurable. On the contrary, if this probability is low, it is said that their interpretative frameworks have a low commensurability or are incommensurable. Many of our studies aim at setting a mean to measure this commensurability.

So knowledge lies in the interaction between an interpretative framework (incorporated within the head of an individual, or embedded into an artifact) and data. This postulate is based on the theories that deal with the construction of tacit individual knowledge. According to this research, the tacit knowledge, which lies within one's brain, is the result of the meaning one allocates -through one's interpretative frameworks -to the data that one perceives as part of all the information received. This individual knowledge is tacit and it may or may not be expressed. It becomes collective knowledge as soon as it is shared by other individuals, whose interpretative frameworks are "commensurable", i.e. there is a minimal common level of interpretation, which is shared by all members of the organization.

B. Knowledge is linked to the action [START_REF] Newell | Managing Knowledge: Critical Investigations of Work and Learning[END_REF] pointed out the limitations of technological systems which can "reinforce existing functional and geographical boundaries" ( [START_REF] Newell | Managing Knowledge: Critical Investigations of Work and Learning[END_REF], p.94) within an organization and its intranet. Knowledge cannot be handled as an object otherwise all the tacit dimension will be neglected. That is notably the reason why [START_REF] Walsham | Knowledge management: The benefits and limitations of computer systems[END_REF] and [START_REF] Wilson | The nonsense of 'knowledge management[END_REF] highlight that knowledge cannot be separated from its owner which is an individual. For them, whatever investments in data bases or information technologies, if individuals are not managed, knowledge is not fully managed.

From a business perspective, knowledge is created through action. Knowledge is essential for the functioning of business and projects processes, and is finalized through their activities.

Hence, one has to be interested in the activities of the actors engaged in the processes contained in the company's missions. This vantage point is included in the use of the concept of knowledge, which cannot be separated from the individual placed within the company, his/her actions, decisions and relations with the surrounding systems (people and artifacts) [START_REF] Rosenthal-Sabroux | A global vision of information management[END_REF].

C. Company's knowledge includes two main categories of knowledge

If [START_REF] Polanyi | Personal Knowledge: Towards a Post Critical Philosophy[END_REF] was the first to consider the existence of tacit knowledge when he said: "we can know more than we can tell", [START_REF] Nonaka | The knowledge-Creating Company[END_REF] pointed out the duality explicit/tacit as inherent to every individual and every organization. According to them, explicit knowledge being only the tip of the iceberg, tacit knowledge should not be neglected. [START_REF] Dermott | Why information technology inspired but cannot deliver knowledge management[END_REF] goes deeper with the idea of "knowledge revolution", which is inspired for him by the information systems, but need human systems to be realized ( [START_REF] Dermott | Why information technology inspired but cannot deliver knowledge management[END_REF], p.116). Within a company, knowledge consists in explicit knowledge on the one hand, composed of all tangible elements (we call it "know-how"), and on the other hand tacit knowledge, which includes intangible knowledge (we call it "skills"). The tangible elements are formalized in a physical form (databases, procedures, plans, models, algorithms, analysis and synthesis documents) and/or are embedded in automated management systems, conception and production systems, and in products. The intangible elements are inherent to the individuals who bear them, either as collective knowledge (the "routines" -non-written individual or collective action procedures) or as personal knowledge (skills, crafts, "job secrets", historical and contextual knowledge, environmental knowledge, competitors, technologies, socio-economic factors, etc).

Our researches based on these three postulates lead us to expand the concept of Information System into the one of Enterprise's Information and Knowledge System.

III. ENTERPRISE'S INFORMATION AND KNOWLEDGE SYSTEM -EIKS

Enterprise's Information and Knowledge System (EIKS) consists mainly in a set of individuals and digital information systems (Figure 2). EIKS rests on a socio-technical context, which consists of individuals in interaction among them, with machines, and with the very EIKS. It includes:

• A Digital Information Systems (DIS), which is artificial system, the artifact designed from information and communication technologies (ICT)

• An Information System (IS), constituted by individuals who, in a given context, are processors of data to which they give a sense under the shape of information. This information, depending of the case, is passed on, remembered, treated, and diffused by them or by the DIS.

• A Knowledge System (KS), consisting of tacit knowledge embodied by the individuals, and of explicit knowledge formalized and codified on any shape of supports (documents, video, photo, digitized or not). Under certain conditions, digitized knowledge is susceptible to be stored, processed and spread with the DIS. In that case, knowledge is no more than information.

We insist on the importance to integrate the individual as a user and a component of the EIKS as [START_REF] Chua | Enhancing collaborative knowledge management systems designs[END_REF] highlighted in their study on Collaborative Knowledge Management System (CKMS) design. They emphasized that "One of the most important components of CKMS is the knowledge workers, who are also the users of the system, and the workspaces they are associated with" (p.172). In fact, relying on our assumptions, we argue that knowledge resides primarily in the heads of individuals, and in the social interactions of these individuals.

EIKS highlights the importance to distinguish data, information, tacit and explicit knowledge. That is described below in Data, Information, Tacit and Explicit Knowledge process (DITEK).

IV. DATA, INFORMATION, TACIT AND EXPLICIT KNOWLEDGE PROCESS -DITEK

A. The empirical model

Numerous authors analyzed the notions of data, information and knowledge. Let us quote notably [START_REF] Davenport | Working Knowledge: How Organizations Manage What They Know[END_REF], [START_REF] Sena | Intellectual capital and knowledge creation: Towards an alternative framework[END_REF], [START_REF] Amin | Architectures of Knowledge: Firms, Capabilities, and Communities[END_REF], [START_REF] Laudon | Management Information Systems: Managing the Digital Firm[END_REF]. Besides, [START_REF] Snowden | The social ecology of knowledge management[END_REF] makes the following synthesis: "The developing practice of knowledge management has seen two different approaches to definition; one arises from information management and sees knowledge as some higher-level order of information, often expressed as a triangle progressing from data, through information and knowledge, to the apex of wisdom. Knowledge here is seen as a thing or entity that can be managed and distributed through advanced use of technology... The second approach sees the problem from a sociological basis. These definitions see knowledge as a human capability to act." ( [START_REF] Snowden | The social ecology of knowledge management[END_REF]).

The dominant positivism approach of KM is implicit in the DIKW (Data-Information-Knowledge-Wisdom) hierarchy model. This model induced numerous computers and information researches. For example, [START_REF] Rowley | The wisdom hierarchy: representations of the dikw hierarchy[END_REF] revisiting the DIKW hierarchy by examining the articulation of the hierarchy in a number of widely read textbooks in information systems and knowledge management preferably published in 2003 and later, noted that "there is a consensus that data, information and knowledge are to be defined in terms of one another, although data and information can both act as inputs to knowledge; the tangle of concepts can be explored at two levels -the relationship between data and information, and the relationship between information and knowledge" ( [START_REF] Rowley | The wisdom hierarchy: representations of the dikw hierarchy[END_REF]) and she raised the question: "Is there a sharp divide between data, information and knowledge, or do they lie on a continuum with different levels of meaning, structure and actionability occurring at different levels?" ( [START_REF] Rowley | The wisdom hierarchy: representations of the dikw hierarchy[END_REF]).

In fact, we think that, beyond all these studies, we have to position our thoughts in the contextual field where the notion of data, information, and knowledge are used: in our case, the field of enterprises and more generally organizations. That leads to conceive how the transformation process should be, constructing the empirical model of DITEK, which is described below.

1) From data to information, and tacit and explicit knowledge: the DITEK empirical model: Relying on the theories and assumptions set out above, we elaborated a model that attempt to describe the transformation process from data to information, and from information to tacit and explicit knowledge. This model, called DITEK empirical model [START_REF] Grundstein | New Research on Knowledge Management Models and Methods[END_REF], describes at a first level the relationship between data and information, and at a second level the relationship between information, and tacit and explicit knowledge. Contrary to the idea of continuum between the concepts of data, information, and knowledge induced by the DIKW hierarchical model, DITEK empirical model shows a discontinuity between these concepts. In DITEK empirical model, by analogy with mental model ( [START_REF] Jones | Mental models: an interdisciplinary synthesis of theory and methods[END_REF]), we highlight the function of interpretative framework as a filter that provides the mechanism through which data aggregated in a new information are filtered and processed by individual's tacit knowledge.

a) The first level: from data to information: At a first level, we have to consider the relationship between data and information. This level must be thought as a basic process where data are discrete raw elements perceived, gathered, and selected by a person before to be aggregated, supplemented, and organized into information. Let's describe the transformation process (see Figure 3). At time T 0 , a sender P 1 is acting in specific context and situation. P 1 possesses pre-existing interpretative frameworks, previous tacit knowledge, and intentions. In an information creation phase, P 1 , has direct access to a set of data outside himself. Then, P 1 according to a sense-reading process -that depends of his pre-existing interpretative frameworks activated depending of his context, his situation, and his intentions, selects some of these data that take sense for him. At the same time, a sense-giving process using P 1 's previous tacit knowledge enables P 1 to aggregate, supplement and organize selected data into information I(P 1 ,T 0 ). Once created this information becomes a static object independent from P 1 , and time. It is this information that is passed-on by the individuals or by means of the digital information system (DIS) where it is stored, treated and transmitted as a stream of digital data. During this process, P 1 's pre-existing interpretative frameworks are not changing; previous tacit knowledge can be reorganized and modified into new tacit knowledge that can change intentions.

b) The second level: from information to tacit and explicit knowledge: At a second level, we have to consider the relationship between information, and tacit and explicit knowledge. This level is in rupture with the first one, it presupposes that information already exists whatever are time and context in which it was created. Let's describe the transformation process (see Figure 4 and5).

At time T n , a later stage of the first level process, when P 2 perceives the information I(P 1 ,T 0 ) during a reception, selfreflection and observation phase (see Figure 4), this information is captured by P 2 , who is in different context and situation than P 1 who elaborates it. P 2 has his own intentions. Then, P 2 according to a sense-reading process interprets this information, filtering data through his pre-existing interpretative frameworks activated depending of his context, his situation, and his intentions. At the same time, a sense-giving process that uses P 2 's previous knowledge operates, and engenders new tacit knowledge. That's the way that changes P 2 's preexisting interpretative frameworks, and enriches P 2 's previous tacit knowledge enabling P 2 to understand his situation, identify a problem, find a solution, decide, and act. The results of this process are modified interpretative frameworks, and new tacit knowledge. The process of transformation of information into tacit knowledge is a process of construction of knowledge. Created knowledge, can be very different from one individual to another when the commensurability of their interpretative frameworks is small, whatever are the causes of it. There are large risks that the same information takes different senses for each of them, and consequently generates a construction of different tacit knowledge in the head of the decision process stakeholders. Unlike the information, knowledge is dynamic. Once constructed it cannot be considered as an object independent from the individual who built it, or the individual who appropriates it to make a decision and to act.

Later on, at time T n+1 , when P 2 as a sender communicates with a receiver P 3 , during a tacit knowledge articulation phase (see Figure 5), a sense-giving process enables P 2 to articulate a part of his new tacit knowledge into explicit knowledge that is no more than information I(P 2 ,T n+1 ) for P 3 .

As a result one can understand the importance to clearly distinguish static factual information, which allows describing the context and the situation that raise a problem, from the cognitive process engendered by the interpretative frameworks and the tacit knowledge possesses by the individual who processes this information to learn and get knowledge he needs to carry out his tasks. Consequently, paraphrasing [START_REF] Kautz | Towards an integrated model of knowledge sharing in software development: Insights from a case study[END_REF] if technology provides the possibility of making information available across time and space, we always have to keep in mind the role of individual in the knowledge sharing process, but we do also pay attention to how individual uses technology to share knowledge. Our approach of KM induces to consider tacit and explicit knowledge as the outcome of a sense-giving process that involves people engaged in actions. It mainly

B. The formalized model

As presented previously, the DITEK empirical model describes the relationship between data and information, and between information and knowledge (tacit and explicit). In this section, it is presented as a mathematical model (based on [START_REF] Grundstein | New Research on Knowledge Management Models and Methods[END_REF]). We agree with the idea that a mathematical model is a description of an observation using mathematical concepts and language. A such model may help to explain this observation and to study the effects of different components, and to make predictions about behavior. In general, mathematical models may include logical models, as far as logic is taken as a part of mathematics. In many cases, the quality of a scientific field depends on how well the mathematical models developed on the theoretical side agree with results of repeatable experiments. Lack of agreement between theoretical mathematical models experimental measurements often leads to important advances as better theories are developed.

In our formalized model, which is a "translation" of our empirical model (no updates, no deletions, no adds), we distinguish events, actors and actions. This work relies on the research work of [START_REF] Szymczak | Data, knowledge and information: Ditek process[END_REF]. We illustrate our formalized model with a toy example dealing with a class of children who already know the numbers and learn how to add them. Each formula is illustrated through an extract of the global example which is detailed at the end of this section.

1) Events: SET OF MOMENTS OF EVENTS

The finite set of moments of events is T = t 0 , t 1 , t 2 , ... where each moment t i , ∀i ∈ N represents an event of reception of data or information or creation of information in some environment (e.g. company). These moments can take place in a same time, however in the model we always distinguish the order of these events. For independent actions (e.g. creating new knowledge by different individuals) we do not loose generality, on the other hand actions which are dependent do not take place at the same moment.

In our example, when t = 0: the teacher starts his/her explanations about addition creating information, when t = 1: the children are listening, receiving this information and trying to understand.

MULTISET OF DATASETS RECEIVED IN CERTAIN MOMENTS

The multiset of datasets received in certain moments is D = {d t , t ∈ T D ⊆ T }. The elements of a multiset do not need to be unique. The same data can be received by different people at different moments. Normal set would not be able to model the redundancy of the elements.

In our example, at moment t = 0, d 0 = ∅ because no data have been received by the children. At time t = 1, d 1 contains data received by the children when the teacher explains, such as d 1 = {Reminder of numbers, + operator, ...}.

MULTISET OF INFORMATIONS CREATED OR RECEIVED IN CERTAIN MOMENTS

The multiset of informations created or received in certain moments is I = {i t , t ∈ (T IC ∪ T IR ) ⊆ T } where T IR are moments of informations reception and T IC are moments of informations creation.

In our example, at moment t = 0, i 0 contains informations created by the teacher when he/she is explaining (speech, illustrations, movements,...) such as i 0 = {"Good morning", ..."Addition relies on + operator", ..., < 1 + 1 > (written on the blackboard), ...}.

CONSTRAINTS

We define some constraints to ensure that two events do not take place at the same time (constraint C 1 ) and that in each moment some event takes place (Constraint C 2 ).

C 1 : T D ∩ T IR = ∅, T D ∩ T IC = ∅, T IC ∩ T IR = ∅ C 2 : T D ∪ T IR ∪ T IC = T .

2) Actors: NUMBER OF PERSONS

The number of all the people in the environment (e.g. company) is the given number: n ∈ N * .

In our example, there are 20 children and 1 teacher, so n = 21.

FAMILY OF SETS OF INDIVIDUALS'INTERPRETATIVE FRAME-

WORKS

The family of sets of individuals'interpretative frameworks is defined as F = {F m,t , m ∈ N * , m ≤ n, t ∈ T } where each person has a set of interpretative frameworks. This set F m,t evolves in time (when an individual takes part in events of information reception), this is the reason why it is identified not only by a person m it belongs to, but also by a certain moment t.

In our example, for Peter (m = 5) who is known to have notably visual abilities to understand things, at the moment t = 0, F 5,0 = {visual abilities, ...}. Listening and watching the explanations of the teacher leads him to understand additions so that, at the moment t = 1, F 5,1 = F 5,0 ∪ {ability to understand additions}.

SET OF TACIT KNOWLEDGE OF INDIVIDUALS

The set of tacit knowledge of individuals is defined as

K = {k m,t , m ∈ N * , m ≤ n, t ∈ T }.
Similarly to interpretative frameworks, the state of individuals'knowledge k m,t also depends on a certain person m and moment in time t.

In our example, for Peter (m = 5) and John (m = 6) who notably known numbers and animals, at the moment t = 0, k 5,0 = k 6,0 = N ∪ {animals}. Listening and watching the explanations of the teacher leads them to understand or not additions so that, at the moment t = 1, for Peter who has understood k 5,1 = k 5,0 ∪ {+}, whereas for John who has not understood k 6,1 = k 6,0 .

SET OF CIRCUMSTANCES

Circumstances are context, situation and intentions of the individual. The set of circumstances is C = {c m,t , m ∈ N * , m ≤ n, t ∈ T }. This set contains all the circumstances c m,t of the event in certain time t connected with certain individual m.

In our example, Peter (m = 5) is known to be more attentive than John (m = 6), at the moment t = 0, c 5,0 = {attentive, ...} and c 6,0 = {non-attentive, ...}. Of course, circumstances will evolve during the lesson.

FAMILY OF SETS OF INDIVIDUALS

Let P be the family of sets P m,t , m ∈ N * , m ≤ n, t ∈ T , where P m,t represents the individual in general and is defined as follows: P m,t = {F m,t , k m,t , c m,t }. This set P m,t is made in order to simplify notation and emphasize, that in some actions all the three crucial elements (interpretative framework F m,t , tacit knowledge k m,t and circumstances c m,t ) of individual are involved.

In our example, for Peter (m = 5), at the moment t = 0, P 5,0 = {F 5,0 , k 5,0 , c 5,0 } = {{visual abilities, ...}, {N ∪ {animals}}, {attentive, ...}}.

SET OF MOMENTS WHEN INDIVIDUALS WERE INVOLVED IN ACTION

Let T m ⊆ T, m ∈ N * , m ≤ n represent a set of moments when the m th person was involved in action. ∀m i , m j ∈ N * , m i ≤ n, m j ≤ n, m i = m j , T mi ∩ T mj = ∅ and ∪ n m k =1 T m k = T . Constraints above guarantee that in certain moment of time only one person is involved in event (action).

In our example, for Peter (m = 5), T 5 are the moments when Peter is involved in an action, such as when the teacher is speaking, he is listening and watching.

3) Actions: In this subsection, we distinguish the three possible actions: 1. Converting data to information and creation of information, 2. Reception of information and 3. Transfer of information. For each one, we define some functions and we explain its roll-out. = {F m,t , knowledge d (D t , P m,t ), c m,t+1 }, t ∈ T D ∩ T m and creates information based on it in moment t + 1 such as i t+1 = inf ormation(P m,t+1 ), t + 1 ∈ T IC ∩ T m . In this case, the state of individual is changed only with regard to circumstances, i.e., P m,t+2 = {F m,t+1 , k m,t+1 , c m,t+2 }.

In time t individual m is acting in the specific circumstances, has a certain state of interpretative framework and knowledge, which together are denoted as P m,t . In an information creation phase, individual has direct access to some set of data (processed and prepared, data preparation is not a part of the model). The sense-reading process begins, in this process, data is transformed to tacit knowledge of the individual with use of his pre-existing knowledge and set of interpretative frameworks, which are activated by certain circumstances. During this process, pre-existing interpretative frameworks of individual are not changing. Previous tacit knowledge of individual is converted into a new tacit knowledge.

Then, in order to create information the will of an individual is necessary. This will is a part of circumstances. The new information is created based on circumstances, tacit knowledge of the individual and his interpretative frameworks.

In our opinion, interpretative frameworks are necessary to create information as a kind of verification tool. When individual creates the information properly, it has to be created in such a way, that it would be an information source of knowledge for him. The fact whether or not something is information source of knowledge for an individual is connected with individuals' interpretative frameworks, though they are necessary in information creation phase. Once created, information becomes a static object, which is independent from its creator and can be stored, processed and transmitted to other individuals. b) Reception of information: We define two functions: knowledge i and modif ication.

KNOWLEDGE FUNCTION

Let knowledge i : I × P → K be a function that enriches individual's tacit knowledge basing on received information, with use of self reflection and observation.

MODIFICATION FUNCTION

Let modif ication : K × F → F be a function that modifies individual's interpretative frameworks based on new tacit knowledge, created with use of self reflection and observation.

During this action (reception of information), individual m receives information in moment t such as P m,t+1 = {modif ication(knowledge i (i t , P m,t ), F m,t ), knowledge i (i t , P m,t ), c m,t+1 }, t ∈ T IR ∩ T m .

Received information affects individual's tacit knowledge and interpretative frameworks, transition from moment t (information reception) to moment t + 1 (processing the information is finished) corresponds to observation and self reflection.

According to a sense-reading process, individual interprets the information i t with use of pre-existing interpretative frameworks F m,t activated depending on the circumstances, at the same time sense-giving process uses individual's preexisting knowledge and with use of interpreted information changes it into the new tacit knowledge. During this process also the set of interpretative frameworks is affected (some parts of information can affect it). It is worth to emphasize that the creation of new tacit knowledge and new set of interpretative frameworks are the processes which take place simultaneously. All in all, the results of these processes are modified: interpretative frameworks F m,t+1 , and new tacit knowledge k m,t+1 , which belong to P m,t+1 . c) Transfer of information: In this phase, tacit knowledge is assimilated to explicit knowledge, which is nothing more than information. Thus, we use the function inf ormation : P → I to obtain the information for individual m and the function knowledge i : I × P → K to obtain the knowledge of individual w (m, w ∈ N + , m ≤ n, w ≤ n, m = w).

During this action (transfer of information), knowledge is expressed by individual m in time t such as i t = inf ormation(P m,t ), t ∈ T IC ∩ T m and knowledge is received by individual w in time t + 1 such as P w,t+1 = {modif ication(knowledge i (i t , P w,t ), F w,t ), knowledge i (i t , P w,t ), c w,t+1 }, t + 1 ∈ T IR ∩ T w .

The process shows transfer of knowledge between two people through the information. It is important to distinguish static factual information, which allows describing the context and the situation from the tacit knowledge of the individual who processes this information to learn and get knowledge he needs to carry out his tasks. Knowledge is always connected to a person, it cannot exist separately. It is also important, that knowledge articulated into information from person m in time t can be totally different than knowledge received by person w in time t + 1. The more common set of interpretative frameworks of individuals m and w, the more likely knowledge remains unchanged during the transfer.

4) Detailed example:

Today is a special day for the children who already know the numbers: they will learn how to add them, they will learn the additions. We consider here a class of 20 children and their teacher so that n = 21 is the number of all the people in the environment.

We remind that P m,t = {F m,t , k m,t , c m,t } represents an individual m ∈ [ [1; 21]] in a moment t ∈ T with his interpretative frameworks F m,t , his tacit knowledge k m,t and within certain circumstances c m,t .

The teacher P 1,t = {F 1,t , k 1,t , c 1,t } is a special individual because he already knows not only the numbers, but also how to add them. So that in the considered circumstances and at the beginning of the class, k 1,0 = N ∪ {+} is the set of his tacit knowledge. On the contrary, every children know the numbers and none of them know the additions, so that in the considered circumstances and at the beginning of the class, k m,0 = N, m ∈ [[2 ; 21]] is the set of tacit knowledge for every child.

At the moment t = 0, when he is explaining how to operate additions, the teacher is creating information based on his tacit knowledge, interpretative frameworks and circumstances. He is using the function inf ormation defined above and he is creating the information i 0 = inf ormation(P 1,0 ), the information created by the person 1 (the teacher) at the moment 0 (beginning of the class). The state of the teacher is changed only with regard to the circumstances, i.e.

P 1,1 = {F 1,0 , k 1,0 , c 1,1 }.
The class is now (t = 1) divided into two categories of children: those who understood the information they perceived (m A ∈ A) and those who did not (m B ∈ B), with A ∪ B = [[2 ; 21]]. Here the functions knowledge i and modif ication defined above are used. We remind that the first function enriches individual's tacit knowledge based on received information and the second function modifies individual's interpretative frameworks based on new tacit knowledge. Then for every child m A ∈ A, i.e. for every child having understood the teacher's explanation, his set of tacit knowledge becomes: k m A ,1 = knowledge i (i 0 , P m A ,0 ) = N ∪ {+}. Thus, his set of interpretative frameworks becomes:

F m A ,1 = modif ication(knowledge i (i 0 , P m A ,0 ), F m A ,0 ) = modif ication(k m A ,1 , F m A ,0
). Finally, every child having understood the teacher's explanation can be characterized by:

P m A ,1 = {F m A ,1 , k m A ,1 , c m A ,1 }, ∀m A ∈ A.
Interpretative frameworks, tacit knowledge and circumstances have changed. On the contrary, for every child m B ∈ B, i.e. for every child having not understood the teacher's Fig. 6. Formalizing an empirical model: a way to enhance the communication between users and designers explanation, his set of tacit knowledge will not change: k m B ,1 = knowledge i (i 0 , P m B ,0 ) = N = k m B ,0 . Thus, his set of interpretative frameworks will not change also:

F m B ,1 = modif ication(knowledge i (i 0 , P m B ,0 ), F m B ,0 ) = modif ication(k m B ,0 , F m B ,0 ) = F m B ,0 .
Finally, every child having not understood the teacher's explanation can be characterized by:

P m B ,1 = {modif ication(k m B ,0 , F m B ,0 ), k m B ,0 , c m B ,1 } = {F m B ,0 , k m B ,0 , c m B ,1 }, ∀m B ∈ B. The state of this child (m B ∈ B)
is changed only with regard to the circumstances.

V. DISCUSSION

In this section, we discuss the interest of our proposal (Figure 6).

As a first step, we propose to formalize the DITEK empirical model. Indeed, empirical modeling is more addressed to end-users while formal modeling is addressed to designers. Representing the same concepts with two equivalent models which cater to different actors, will help these actors to communicate. Our approach is illustrated Figure 6 where two persons having different interpretative frameworks tend to communicate. The aim for the designer is to design a digital information system relevant for the user. For that, the user has to explicit, at best, his expectations. Indeed, the user easily uses an empirical model to express his/her needs whereas the designer easily requires a formalized model to design a digital information system (DIS). Thus, our proposition of formalizing an empirical model leads these two persons not only to easily communicate but also to better understand each other. Therefore, the designer is able to design a DIS as closely as possible to the user's expectations. De facto, it enhances the interaction between the user and the system because it is relevant for his needs.

Finally, reducing the gap between empirical model and formal model is a way to enhance not only communication between users and designers, but also interaction between users and DIS. In our point of view, it constitutes a more innovative design.

In a second step, we include users into the EIKS. There-fore, we consider users, with their tacit knowledge and their interpretative frameworks, as components of the EIKS.

From these two previous points: (i) representing the same concepts with two equivalent models enhances the communication between users and designers, and (ii) considering users as components of the EIKS, we believe that formalizing an empirical model is an important step to a more innovative design of DIS.

VI. CONCLUSION AND FUTURE WORK

The area of knowledge management in companies will not be replaced by strictly technological process for a very long time (until we will be able to read people's minds and copy their thoughts and ways of thinking, what the author hopes will never happen). It is very important to be aware of the processes connected with conversions between data, information and knowledge. DITEK presents these connections and allows on its basis to develop knowledge management strategies.

In this paper, we first present the three postulates that are the base of our researches. Then we introduce the usercentered EIKS concept. EIKS highlights the importance to distinguish data, information, tacit and explicit knowledge that is described in Data, Information, Tacit and Explicit Knowledge process (DITEK). The DITEK's formal model insures that the DITEK's empirical model is consistent and not ambiguous. We are well-aware, in the real world, with the formalized model, sometimes we do not have data for all the sets which may be empty.

Formalizing, particularly interpretative frameworks, tacit knowledge, and circumstances for several individuals, could sensitize to the diversity of individual understandings and could lead to their comparisons. In others words, this work in progress is a first step for measuring the commensurability of interpretative frameworks.

Fig. 2 .

 2 Fig.2. The enterprise's information and knowledge system (EIKS)

Fig. 3 .

 3 Fig. 3. DITEK empirical model level 1: From data... to information

  a) Converting data to information and creation of information: We define two functions: knowledge d and inf ormation.KNOWLEDGE FUNCTIONLet knowledge d : D × P → K be a function that enriches individual's tacit knowledge with the data (sense-reading process), the result of the function is knowledge of the individual enriched with received data.INFORMATION FUNCTIONLet inf ormation : P → I be a function that creates information based on individual's tacit knowledge, interpretative frameworks and circumstances. m receives data in moment t such as P m,t+1


Cristina Bazgan
email: bazgan@lamsade.dauphine.fr

Sonia Toubaline
email: toubaline@lamsade.dauphine.fr

Daniel Vanderpooten

Complexity of determining the most vital elements for the 1-median and 1-center location problems

Keywords: most vital edges and nodes, 1-median, 1-center, complexity, approximation

Complexity of determining the most vital elements for the p-median and p-center location problems

Cristina Bazgan, Sónia Toubaline, Daniel

Introduction

For problems of security or reliability, it is important to assess the ability of a system to resist to a destruction or a failure of a number of its entities. This amounts to identifying critical entities which can be determined with respect to a measure of performance or a cost associated to the system. In this paper we focus on simple location problems. Consider for instance the following problem. We aim at locating one hospital or one supermarket in order to serve n areas. Each area is characterized by a population which represents a potential demand.

The areas are connected by roads with a given distance. The objective for locating this hospital or supermarket is not the same. Indeed, for the hospital, we aim at finding the location that minimizes the maximum distance weighted by population from the hospital to all areas while for the supermarket we aim at finding the location that minimizes the total weighted distance from the supermarket to all areas. However, there may occur incidents such as works on road or floods that make some roads inaccessible. In this case several problems may arise. We can aim at detecting the critical roads whose failure causes the largest increase in the weighted distance. Alternatively, wa can aim at determining the maximum number of damaged roads which still ensures a certain quality of service level. Modeling the considered network by a weighted connected graph with distances on edges and weights on nodes, where roads are edges and areas are nodes, these problems consist either of finding among all subset of edges or nodes, a subset whose removal from the graph generates the largest increase in the total or maximum weighted distance or of determining a subset of edges or nodes of minimal cardinality such that, when we remove this subset from the graph, the total or maximum weighted distance is at least as large as a specified threshold. In the literature these problems are referred respectively to as the k most vital edges/nodes and the min edge/node blocker problems.

The k most vital edges/nodes and min edge/node blocker versions have been studied for several problems, including shortest path, minimum spanning tree, maximum flow, maximum matching and independent set. The k most vital edges problem with respect to shortest path was proved NP -hard [START_REF] Bar-Noy | The complexity of finding most vital arcs and nodes[END_REF]. Later, k most vital edges/nodes shortest path (and min edge/node blocker shortest path, respectively) were proved not 2-approximable (not 1.36-approximable, respectively) if P = NP [START_REF] Khachiyan | On short paths interdiction problems : total and node-wise limited interdiction[END_REF]. For minimum spanning tree, k most vital edges is NP-hard [START_REF] Frederickson | Increasing the weight of minimum spanning trees[END_REF] and O(log k)-approximable [START_REF] Frederickson | Increasing the weight of minimum spanning trees[END_REF]. In [START_REF] Wood | Deterministic network interdiction[END_REF] it is proved that k most vital edges maximum flow is NP -hard. For maximum matching, min edge blocker is NP -hard even for bipartite graphs [START_REF] Zenklusen | Blockers and transversals[END_REF], but polynomial for grids and trees [START_REF] Ries | Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid[END_REF]. In [START_REF] Bazgan | Complexity of most vital nodes for independent set in graphs related to tree structures[END_REF], the k most vital nodes and min node blocker versions with respect to independent set for bipartite graphs remain polynomial on the unweighted graphs and become NP -hard for weighted graphs. For bounded treewidth graphs and cographs these versions remain polynomial [START_REF] Bazgan | Complexity of most vital nodes for independent set in graphs related to tree structures[END_REF]. Concerning the approximation on bipartite weighted graphs, k most vital nodes with respect to independent set has no ptas [START_REF] Bazgan | Complexity of most vital nodes for independent set in graphs related to tree structures[END_REF].

In this paper the k most vital edges (nodes) and min edge (node) blocker versions for the 1-median and 1-center problems are studied.

After introducing some preliminaries in Section 2, we prove in Section 3 that k Most Vital Edges (Nodes) 1-median (1-center) and Min Edge (Node) blocker 1-median (1-center) are not constant approximable for some constants, unless P=NP. Final remarks are provided in Section 4.

Basic concepts and definitions

Consider G = (V, E) a connected weighted graph with |V | = n and |E| = m. Let d vivj be the distance between v i and v j for (v i , v j ) ∈ E and w vi be the weight associated to node v i for i = 1, . . . , n (w vi represents the demand occurring at node v i ). Denote by d(v i , v j ) the minimum distance between two nodes v i and v j of G. The 1-median (respectively 1-center) problem consists of locating the median (respectively the center) of a graph G, that is the node v which minimizes the total weighted distance (respectively the maximum weighted distance) to all nodes of the graph given by vi∈V

w vi d(v, v i ) (respectively max vi∈V w vi d(v, v i )).
Denote by G -R the graph obtained from G by removing the subset R of edges or nodes.

We consider in this paper the k most vital edges (nodes) and min edge (node) blocker versions of the 1-median and 1-center problems. These problems are defined as follows:

k Most Vital Edges 1-median (1-center) Input: A connected graph G = (V, E)

Min Edge blocker 1-median (1-center)

Input: A connected graph G = (V, E) weighted by two functions d : E → N and w : V → N and a positive integer U . Output: An edge blocker S * ⊆ E of minimal cardinality where an edge blocker is a subset of edges such that the value of an optimal solution for the 1-median (1-center) problem in the graph G -S * is greater than or equal to U .

Min Node blocker 1-median (1-center)

Input: A connected graph G = (V, E) weighted by two functions d : E → N and w : V → N and a positive integer U . Output: A node blocker N * ⊆ V of minimal cardinality where a node blocker is a subset of nodes such that the value of an optimal solution for the 1-median (1-center) problem in the graph G -N * is greater than or equal to U .

Given an NPO optimization problem and an instance I of this problem, we use |I| to denote the size of I, opt(I) to denote the optimum value of I, and val(I, S) to denote the value of a feasible solution S of instance I. The performance ratio of S (or approximation factor) is r(I, S) = max val(I,S) opt(I) , opt(I) val(I,S) . The error of S, ε(I, S), is defined by ε(I, S) = r(I, S) -1.

For a function f , an algorithm is an f (n)-approximation, if for every instance I of the problem, it returns a solution S such that r(I, S) ≤ f (|I|).

The notion of a gap-reduction was introduced in [START_REF] Arora | Hardness of approximations[END_REF] by Arora and Lund. A minimization problem Π is called gap-reducible to a maximization problem Π ′ with parameters (c, ρ) and (c ′ , ρ ′ ), if there exists a polynomial time computable function f such that f maps an instance I of Π to an instance I ′ of Π ′ , while satisfying the following properties.

-If opt(I) ≤ c then opt(I ′ ) ≥ c ′ -If opt(I) > cρ then opt(I ′ ) < c ′ ρ ′
Parameters c and ρ are function of |I| and parameters c ′ and ρ ′ are function of

|I ′ |. Also, ρ, ρ ′ ≥ 1.
The interest of a gap-reduction is that if Π is not approximable within a factor ρ then Π ′ is not approximable within a factor ρ ′ .

The notion of an E-reduction (error-preserving reduction) was introduced in [9] by Khanna et al. A problem Π is called E-reducible to a problem Π ′ , if there exist polynomial time computable functions f , g and a constant β such that f maps an instance I of Π to an instance I ′ of Π ′ such that opt(I) and opt(I ′ ) are related by a polynomial factor, i.e. there exists a polynomial p such that opt(I ′ ) ≤ p(|I|)opt(I), -g maps any solution S ′ of I ′ to one solution S of I such that ε(I, S) ≤ βε(I ′ , S ′ ).

An important property of an E-reduction is that it can be applied uniformly to all levels of approximability; that is, if Π is E-reducible to Π ′ and Π ′ belongs to C then Π belongs to C as well, where C is a class of optimization problems with any kind of approximation guarantee (see also [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF]).

NP-hardness of approximation

We first prove that k Most Vital Edges (Nodes) 1-median and k Most Vital Edges (Nodes) 1-center are not constant approximable for some constants, unless P=NP. For this, we construct, in theorems 1 and 2, gap-reductions from Min Vertex Cover restricted to tripartite graphs. This problem is shown NP -hard in [START_REF] Garey | Some simplified NP-complete graph problems[END_REF] where Garey et al. prove that it is NP -hard to find a minimum vertex cover in graphs of maximum degree 3, considering also that these graphs, with the exception of the clique K 4 , are 3-colorable [START_REF] Brooks | On colouring the nodes of a network[END_REF].

Theorem 1. k Most Vital Edges 1-median and k Most Vital Edges 1center are NP-hard to approximate within a factor 7 5ǫ and 4 3ǫ respectively, for any ǫ > 0.

Proof : We first consider k Most Vital Edges 1-median.

Let I be an instance of Min Vertex Cover formed by a graph G = (V, E)

with a tripartition V = V 1 ∪ V 2 ∪ V 3 and |V | = n. We construct an instance I ′ of k Most Vital Edges 1-median consisting of a graph G ′ = (V ′ , E ′ ) with k < n
as follows (see Figure 1). We associate for each node v i ℓ ∈ V i , two nodes v i ℓ,1 and v i ℓ,2 in V ′ and connect them in E ′ , for i = 1, 2, 3 and ℓ = 1, . . . , |V i |. We add for each edge (v i ℓ , v j r ) ∈ E, with i < j, the edge (v i ℓ,2 , v j r,1 ) to E ′ . We also add four nodes

x 1 , x 2 , x ′ 2 , x 3 connected by the path (x 1 , x ′ 2 ), (x ′ 2 , x 2 ), (x 2 , x 3 ). We connect x 1 to v 1 ℓ,1 for ℓ = 1, . . . , |V 1 |, x ′ 2 to v 2 ℓ,1 and x 2 to v 2 ℓ,2 for ℓ = 1, . . . , |V 2 | and x 3 to v 3 ℓ,2 for ℓ = 1, . . . , |V 3 |. We assign a distance 1 to edges (x 1 , x ′ 2 ), (x 1 , v 1 ℓ,1 ), (x ′ 2 , v 2 j,1 ), (x 2 , v 2 j,2 ) and (x ′ 2 , x 3 ) for ℓ = 1, . . . , |V 1 | and j = 1, . . . , |V 2 |, a distance 2 for the edge (x ′ 2 , x 2
) and a distance 0 for all the other edges in E ′ . We set w x1 = 8, w x2 = w x3 = 1 and assign a weight 0 to all other nodes in V ′ . We replace all edges of E ′ , except the edges

(v i ℓ,1 , v i ℓ,2
), for i = 1, 2, 3 and ℓ = 1, . . . , |V i |, by the gadget given in Figure 2. For each edge to be replaced, one chooses indifferently the vertex playing the role of i in Figure 2, except for all edges incident to x 1 for which we take x 1 as i. We show in the following that:

1. opt(I) ≤ k ⇒ opt(I ′ ) ≥ 7 2. opt(I) > k ⇒ opt(I ′ ) ≤ 5
which proves that k Most Vital Edges 1-median is NP -hard to approximate within a factor 7 5ǫ, for any ǫ > 0. First observe that there exists at least one optimal solution of k Most Vital Edges 1-median containing only edges among the edges (v i ℓ,1 , v i ℓ,2 ), for i = 1, 2, 3 and ℓ = 1, . . . , |V i |. Indeed, if a solution contains edges from a gadget corresponding to an initial edge (i, j), it must contain at least n edges from this gadget in order to have a chance to increase the solution value by suppressing communication between i and j. Therefore, since k < n, it is at least as good to select k edges among those which do not belong to the gadgets.

Observe also that G ′ is designed so as to ensure that x 1 will always be the optimal 1-median node. Indeed, since the weight of vertex x 1 is 8 and all edges incident to x 1 have distance 1, any other node would have a total weighted distance of at least 8. In the following, x 1 has always a total distance of at most 7.

1. If there exists a vertex cover V ′ ⊆ V of cardinality less than k in G then consider any set of vertices V ′′ ⊃ V ′ of cardinality k, and remove

S ′′ = {(v i ℓ,1 , v i ℓ,2 ) : v i ℓ ∈ V ′′ } from G ′ . The optimal 1-median node in G ′ -S ′′ is x 1 with a total weighted distance d(x 1 , x 2 ) + d(x 1 , x 3 ) = 3 + 4 = 7. Hence, opt(I ′ ) ≥ 7. x3 x2 x ′ 2 x1 v 3 2,2 v 3 2,1 v 3 1,2 v 3 1,1 v 2 1,2 v 2 1,1 v 2 2,2 v 2 2,1 v 2 3,2 v 2 3,1 v 1 2,2 v 1 2,1 v 1 1,2 v 1 1,1 v 3 2 v 3 1 v 1 2 v 1 1 v v v 1 1 1 1 1 0 V1 V2 V3 8 0 1 1 with w v i ℓ,1 = w v i ℓ,2 = 0 for i = 1, 2,
(v i ℓ,1 , v i ℓ,2 ), for i = 1, 2, 3 and ℓ = 1, . . . , |V i |. The optimal 1- median node in G ′ -S * is x 1 with opt(I ′ ) = d(x 1 , x 2 ) + d(x 1 , x 3 ). Each edge (v i ℓ,1 , v i ℓ,2
) of S * corresponds to a node v i ℓ ∈ V i in the graph G, for i = 1, 2, 3 and ℓ = 1, . . . , |V i |. Let N * be the subset of nodes in G that correspond to edges of S * . Since |N * | = k and opt(I) > k, N * is not a vertex cover in G. Thus, there exists at least one edge (v i ℓ , v j r ) ∈ E which is not covered. This implies in G ′ the existence of a path from x i (or x ′ i ) to x j , with i < j, passing through the gadget corresponding to the edge (v i ℓ,2 , v j r,1 ), enabling a decrease of some shortest path distances. Hence,

• if i = 1 and j = 2 then opt(I ′ ) ≤ 6

• if i = 1 and j = 3 then opt(I ′ ) ≤ 3

• if i = 2 and j = 3 then opt(I ′ ) ≤ 6 Therefore, opt(I ′ ) ≤ 6.

We consider now k Most Vital Edges 1-center. We use the same construction as above. We show that:

1. opt(I) ≤ k ⇒ opt(I ′ ) ≥ 4 2. opt(I) > k ⇒ opt(I ′ ) ≤ 3
which proves that k Most Vital Edges 1-center is NP -hard to approximate within a factor 4 3ǫ, for any ǫ > 0. Similarly as above, there exists at least one optimal solution of k Most Vital Edges 1-center containing only edges among the edges (v i ℓ,1 , v i ℓ,2 ), for i = 1, 2, 3 and ℓ = 1, . . . , |V i |. Moreover, as before, x 1 will always be the optimal 1-center node.

1. If there exists a vertex cover V ′ ⊆ V of cardinality less than k in G then consider any set of vertices V ′′ ⊃ V ′ of cardinality k, and remove

S ′′ = {(v i ℓ,1 , v i ℓ,2 ) : v i ℓ ∈ V ′′ } from G ′ .
The optimal 1-center node in G ′ -S ′′ is x 1 with a maximum weighted distance max{d(x 1 , x 2 ), d(x 1 , x 3 )} = 4. Hence, opt(I ′ ) ≥ 4. 2. Let S * be any solution of k Most Vital Edges 1-center which contains only edges

(v i ℓ,1 , v i ℓ,2 ), for i = 1, 2, 3 and ℓ = 1, . . . , |V i |. The optimal 1-center node in G ′ -S * is x 1 with opt(I ′ ) = max{d(x 1 , x 2 ), d(x 1 , x 3 )}. Each edge (v i ℓ,1 , v i ℓ,2
) of S * corresponds to a node v i ℓ ∈ V i in the graph G, for i = 1, 2, 3 and ℓ = 1, . . . , |V i |. Let N * be the subset of nodes of G corresponding to edges in S * . Since |N * | = k and opt(I) > k, N * is not a vertex cover in G. Thus, there exists at least one edge (v i ℓ , v j r ) ∈ E which is not covered. This implies in G ′ the existence of a path from x i (or x ′ i ) to x j , with i < j, passing through the gadget corresponding to the edge (v i ℓ,2 , v j r,1 ). Hence,

• if i = 1 and j = 2 then opt(I ′ ) ≤ 3 • if i = 1 and j = 3 then opt(I ′ ) ≤ 3
• if i = 2 and j = 3 then opt(I ′ ) ≤ 3 Therefore, opt(I ′ ) ≤ 3.

2

Theorem 2. k Most Vital Nodes 1-median and k Most Vital Nodes 1-center are NP-hard to approximate within a factor 3 2ǫ, for any ǫ > 0.

Proof : We first consider k Most Vital Nodes 1-median.

Let I be an instance of Min Vertex Cover formed by a graph G = (V, E) with a tripartition V = V 1 ∪ V 2 ∪ V 3 and |V | = n. We construct an instance I ′ of k Most Vital Nodes 1-median consisting of a graph G ′ = (V ′ , E ′ ) with k < n as follows (see Figure 3). G ′ is a copy of G to which we add complete graphs K i n with n nodes x 1 i , . . . , x n i for i = 1, 2, 3. We connect each node v i ℓ ∈ V i with each node x r i , for i = 1, 2, 3, ℓ = 1, . . . , |V i | and r = 1, . . . , n. We connect also each node x r i to each node x r i+1 for i = 1, 2 and r = 1, . . . , n. We assign a distance 2 to edges (x r i , x r i+1 ) for i = 1, 2 and r = 1, . . . , n, a distance 1 to edges (x r 1 , v 1 ℓ ) for ℓ = 1, . . . , |V 1 | and r = 1, . . . , n and a distance 0 to all other edges in E ′ . We set w x r 1 = 7 and w x r 2 = w x r 3 = 1 for r = 1, . . . , n, and w v i ℓ = 0 for i = 1, 2, 3, ℓ = 1, . . . , |V i |. We show in the following that:

1. opt(I) ≤ k ⇒ opt(I ′ ) ≥ 6n 2. opt(I) > k ⇒ opt(I ′ ) ≤ 4n
which proves that k Most Vital Nodes 1-median is NP -hard to approximate within a factor 3 2ǫ, for any ǫ > 0. First observe that there exists at least one optimal solution of k Most Vital Nodes 1-median containing only nodes of V . Indeed, if a solution contains nodes from K i n for some i, it must contain all nodes of K i n in order to have a chance to increase the solution value by disconnecting these nodes from the graph. Therefore, since k < n, it is at least as good to select k nodes in V only.

Observe also that G ′ is designed so as to ensure that any node x r 1 for r = 1, . . . , n will always be an optimal 1-median node. Indeed, since the weight of a vertex x r 1 is 7 and all edges incident to x r 1 , except the edges (x r 1 , x j 1 ) for j = 1, . . . , n and j = r have distance at least 1, any other node would have a total weighted distance of at least 7, while any node x r 1 has always a total weighted distance of at most 6. We consider arbitrarily in the following that x 1 1 is the selected optimal 1-median node.

1. If there exists a vertex cover V ′ ⊆ V of cardinality less than k in G then consider any set of vertices V ′′ ⊃ V ′ of cardinality k, and remove V ′′ from G ′ . Taking x 1 1 as the optimal 1-median node in G ′ -V ′′ , we get a total weighted distance

n j=1 (d(x 1 1 , x j 2 ) + d(x 1 1 , x j 3 )) = n j=1 (2 + 4) = 6n. Hence, opt(I ′ ) ≥ 6n. 2. Let N * ⊆ V be any solution of k Most Vital Nodes 1-median which contains only nodes of V . Taking x 1 1 as the optimal 1-median node in G ′ -N * , we get opt(I ′ ) = n ℓ=1 (d(x 1 1 , x ℓ 2 ) + d(x 1 1 , x ℓ 3 )). Since |N * | = k and opt(I) > k, v 1 2 v 1 1 v 3 2 v 3 1 v 2 3 v 2 2 v 2 1 v 3 2 v 3 1 v 1 2 v 1 1 v 2 3 v 2 2 v 2 1 V1 V2 V3 K 1 7 K 2 7 K 3 7 1 1 2 2 0 0 0 0 0 V1 V2 V3 0 0 0 0 0 0 0 0 7 1 1
with wv ℓ = 0 for v ℓ ∈ Vi, i = 1, 2, 3 Fig. 3. Construction of G ′ from G
N * is not a vertex cover in G. Thus, there exists at least one edge (v i , v j ) ∈ E which is not covered. This implies in G ′ the existence of a path from each x r i to each x r j for r = 1, . . . , n, passing through the edge (v i , v j ). Hence,

• if i = 1 and j = 2 then opt(I ′ ) ≤ n ℓ=1 (1 + 3) = 4n • if i = 1 and j = 3 then opt(I ′ ) ≤ n ℓ=1 (2 + 1) = 3n • if i = 2 and j = 3 then opt(I ′ ) ≤ n ℓ=1 (2 + 2) = 4n Consequently, opt(I ′ ) ≤ 4n.
We consider now k Most Vital Nodes 1-center. We use the same construction as above, but we modify the distance associated to the edges (x r 2 , x r 3 ) for r = 1, . . . , n for which we assign a distance 1. We show that:

1. opt(I) ≤ k ⇒ opt(I ′ ) ≥ 3 2. opt(I) > k ⇒ opt(I ′ ) ≤ 2
which proves that k Most Vital Nodes 1-center is NP -hard to approximate within a factor 4 3ǫ, for any ǫ > 0. As previously, we can show that only the nodes of V can be removed. We observe as above that any node x r 1 for r = 1, . . . , n will always be an optimal 1-center node. We consider arbitrarily in the following that x 1 1 is the selected optimal 1-center node.

x ′ 4 x4 x ′ 3 x3 x ′ 2 x2 x ′ 1 x1 v ′ 4 v4 v ′ 3 v3 v ′ 2 v2 v ′ 1 v1 v4 v3 v2 v1 1 1 1 1 1 1 1 1 2 0 2 0 2 0 2 1 5 3 1 0 0 0 0 2n 2 1 1 1 1 1 1 1 with wv ℓ = w v ′ ℓ = 0 for ℓ = 1, . . . , 4
Fig. 4. Construction of G ′ from G with n = 4 nodes edges incident to x 1 have distance at least 1, any other node would have a total weighted distance of at least 2n 2 + 1. In the following, x 1 has always a total distance of at most 2n 2 .

We prove first that opt(

I ′ ) ≤ opt(I). Let V * ⊆ V be a minimum vertex cover of G. Let us consider S * = {(v i , v ′ i ) : v i ∈ V * }.
By removing the edges in S * from G ′ , the optimal 1-median node is x 1 with a total weighted distance

n i=1 w xi d(x 1 , x i ) + n i=1 w x ′ i d(x 1 , x ′ i ) = 2( n-1 i=1 i + n i=1 i) = 2n 2 = U . Hence, opt(I ′ ) ≤ |S * | = opt(I).
When we remove all edges (v i , v ′ i ), for i = 1, . . . , n from G ′ , the optimal 1-median node in the resulting graph is x 1 with value U . Hence, opt(I ′ ) ≤ n. Let S ⊆ E ′ be an edge blocker for G ′ . If S contains an edge (i, e ℓ ij ) or (e ℓ ij , j) from a gadget corresponding to an initial edge (i, j), it must contain at least n + 1 edges from this gadget in order to suppress the communication between i and j, otherwise the value of an optimal solution for the 1-median problem in G ′ -S is the same as in G ′ -(S\{(i, e ℓ ij )}) or G ′ -(S\{(e ℓ ij , j)}). Therefore, since opt(I ′ ) ≤ n, we can consider in the following that S contains only edges among the edges

(v i , v ′ i ), i ∈ {1, . . . , n}. Let us consider N = {v i : (v i , v ′ i )
∈ S} where S is an edge blocker. We prove, by contradiction, that N is a vertex cover in G. Suppose that there exists an edge (v i , v j ) ∈ E such that v i ∈ N , v j ∈ N and i < j. We show in the following that by removing S from G ′ , the value of an optimal solution for the 1-median problem in the remaining graph is strictly less than 2n 2 . Indeed, x 1 is the optimal 1-median node in G ′ -S. Let D(x 1 ) be the total weighted distance

associated to x 1 in G ′ -S. We have D(x 1 ) = n ℓ=1 d(x 1 , x ′ ℓ ) + n ℓ=1 d(x 1 , x ℓ ) = j-1 ℓ=1 d(x 1 , x ′ ℓ ) + d(x 1 , x ′ j ) + n ℓ=j+1 d(x 1 , x ′ ℓ )+ n ℓ=1 d(x 1 , x ℓ ). Then, D(x 1 ) ≤ 2 j-1 ℓ=1 ℓ + d(x 1 , x ′ j ) + 2 n ℓ=j+1 ℓ + 2 n-1 ℓ=1 ℓ = 2 n ℓ=1 ℓ -2j + d(x 1 , x ′ j ) + 2 n-1 ℓ=1 ℓ = 2n 2 -2j + d(x 1 , x ′ j ).
The edge (v i , v j ) being not covered, this implies the existence of a path from x 1 to x ′ j using a subpath from x 1 to x i and joining x i to x ′ j by a subpath passing through the gadget associated to the edge

(v i , v j ). We have d(x 1 , x ′ j ) ≤ 2(i -1) + 1 + 2(j -i) -1 + 1 = 2j -1.
Thus, we have D(x 1 ) ≤ 2n 2 -1 < 2n 2 , contradicting the assumption that S is an edge blocker. Therefore, N is a vertex cover in G such that val(I, N ) = val(I ′ , S). Consequently, ε(I, N ) = val(I,N ) opt(I) -1 ≤ val(I ′ ,S) opt(I ′ ) -1 = ε(I ′ , S), which achieves the proof.

We consider now Min Edge blocker 1-center. We use the same construction as above with U = 2n. As above, G ′ is designed so as to ensure that x 1 will always be the optimal 1-center node.

We show first that opt(I ′ ) ≤ opt(I). Let V * ⊆ V be a minimum vertex cover in G. Let us consider

S * = {(v i , v ′ i ) : v i ∈ V * }.
By removing the edges of S * from the graph G ′ , the optimal 1-center node is x 1 with a maximum weighted distance d(x 1 , x ′ n ) = 2n = U . Hence, opt(I ′ ) ≤ |S * | = opt(I). Let S ⊆ E ′ be an edge blocker. We can assume, similarly to the 1-median problem, that S contains only edges among the edges

(v i , v ′ i ), i ∈ 1, . . . , n. Let us consider N = {v i : (v i , v ′ i ) ∈ S}.
In the following, we show by contradiction that N is a vertex cover in G. Suppose that there exists an edge (v i , v j ) ∈ E such that v i ∈ N , v j ∈ N and i < j. Then x 1 is the optimal 1-center node in G ′ -S with a maximum weighted distance D max (x 1 ) = d(x 1 , x n ). The edge (v i , v j ) being not covered, this implies the existence of a path from x 1 to x ′ j using a subpath from x 1 to x i and joining x i to x ′ j by a subpath passing through the gadget associated to the edge (v i , v j ). Then D max (x 1 ) ≤ 2(i -1) + 1 + 2(ji) -1 + 1 + 2(nj) = 2n -1 < 2n, contradicting the assumption that S is an edge blocker. Therefore N is a vertex cover in G such that val(I, N ) = val(I ′ , S). Consequently, ε(I, N ) = val(I,N ) opt(I) -1 ≤ val(I ′ ,S) opt(I ′ ) -1 = ε(I ′ , S), which achieves the proof. 2

Theorem 4. Min Node blocker 1-median and Min Node blocker 1center are NP-hard to approximate within a factor 1.36.

Proof : We consider first Min Node blocker 1-median.

Let I be an instance of Min Vertex Cover consisting of a graph G = (V, E) with V = {v 1 , . . . , v n }. We construct an instance I ′ of Min Node blocker 1median formed by a graph G ′ = (V ′ , E ′ ) and a positive integer U as follows (see Figure 5). G ′ is a copy of G to which we add one node x 1 and complete graphs K i n+1 with n + 1 nodes x 1 i , . . . , x n+1 i for i = 2, . . . , n. We connect x 1 to v 1 and x r 2 for r = 1, . . . , n + 1, and each node x r i to v i for i = 2, . . . , n and r = 1, . . . , n + 1. We also connect each node x r i to each node x r i+1 for r = 1, . . . , n + 1 and i = 2, . . . , n -1. We assign a distance 1 to the edge (x 1 , v 1 ), a distance 2 to the edges (x 1 , x r 2 ) and (x r i , x r i+1 ) for i = 2, . . . , n -1 and r = 1, . . . , n + 1, and a distance 0 to all other edges in E ′ . Let us set w x1 = n 3 , w x r i = 1 for i = 2, . . . , n and r = 1, . . . , n + 1 and w vi = 0 for i = 1, . . . , n. Finally, we set U = n(n 2 -1). Observe that G ′ is designed so as to ensure that x 1 will always be the optimal 1-median node. Indeed, since the weight of vertex x 1 is n 3 and all edges incident to x 1 have distance at least 1, any other node would have a total weighted distance of at least n 3 . In the following, x 1 has always a total distance of at most n(n 2 -1).

We show first that opt(I ′ ) ≤ opt(I). Let V * ⊆ V be a minimum vertex cover in G. By removing V * from G ′ , the optimal 1-median node is x 1 with a total weighted distance

n ℓ=2 n+1 r=1 d(x 1 , x r ℓ ) = 2(n+1) n-1 i=1 i = n(n-1)(n+1) = U . Hence, opt(I ′ ) ≤ |V * | = opt(I).
Let N ⊆ V ′ be a node blocker. According to the construction of G ′ , in order to obtain an optimal solution for the 1-median problem in the graph G ′ -N of a value at least U , N must be included in V . We show, by contradiction, that N is a vertex cover in G. Suppose that there exists an edge (v i , v j ) ∈ E such that v i ∈ N , v j ∈ N and i < j. The optimal 1-median node in G ′ -N is x 1 with value strictly less than n(n -1)(n + 1). Indeed, let D(x 1 ) be the total weighted distance associated to

x 1 in G ′ -N . Hence, D(x 1 ) = n ℓ=2 n+1 r=1 d(x 1 , x r ℓ ) = j-1 ℓ=2 n+1 r=1 d(x 1 , x r ℓ ) + n+1 r=1 d(x 1 , x r j ) + n+1 r=1 n ℓ=j+1 d(x 1 , x r ℓ )
). We distinguish two cases:

• If v i = v 1 then d(x 1 , x r j ) = d x1v1 + d v1vj + d vj x r j = 1 for r = 1, . . . , n + 1. Hence, we obtain D(x 1 ) ≤ 2(n + 1) j-2 ℓ=1 ℓ + (n + 1) + 2(n + 1) n-1 ℓ=j ℓ < 2(n + 1) j-2 ℓ=1 ℓ + 2(j -1)(n + 1) + 2(n + 1) n-1 ℓ=j ℓ = n(n -1)(n + 1), contradiction. • If v i = v 1 then d(x 1 , x r j ) = d(x 1 , x 1 i ) + d x 1 i vi + d vivj + d vj x r j = d(x 1 , x 1 i ) for r = 1, . . . , n + 1. Hence, we obtain D(x 1 ) ≤ 2(n + 1) j-2 ℓ=1 ℓ + 2(i -1)(n + 1) + 2(n + 1) n-1 ℓ=j ℓ < 2(n + 1) j-2 ℓ=1 ℓ + 2(j -1)(n + 1) + 2(n + 1) n-1 ℓ=j ℓ = n(n -1)(n + 1), contradiction.
Therefore N is a vertex cover in G such that val(I, N ) = val(I ′ , N ). Consequently, ε(I, N ) = val(I,N ) opt(I) -1 ≤ val(I ′ ,N ) opt(I ′ ) -1 = ε(I ′ , N ), which achieves the proof.

We consider now Min Node blocker 1-center. We use the same construction as above with U = 2(n -1). Here again, we observe that G ′ is designed so as to ensure that x 1 will always be the optimal 1-center node.

We show first that opt(I ′ ) ≤ opt(I). Let V * ⊆ V be a minimum vertex cover in G. By deleting the nodes of V * from G ′ , the optimal 1-center node in the remaining graph is x 1 with a maximum weighted distance d(x 1 , x r n ) = 2(n -1) = U for any r = 1, . . . , n + 1. Hence, opt(I ′ ) ≤ |V * | = opt(I).

When we remove all nodes v i , i = 1, . . . , n from G ′ , the optimal 1-center node in the resulting graph is x 1 with value U . Hence, opt(I ′ ) ≤ n. Let N ⊆ V ′ be a node blocker. According to the construction of G ′ , in order to obtain an optimal 1-center node in G ′ -N of value at least U , N cannot contain x 1 . If N contains nodes x ℓ i for a given i and ℓ, then N must contains all the n + 1 nodes x r i for r = 1, . . . , n + 1, otherwise the value of an optimal solution for the 1-center problem in G ′ -N is the same as in G ′ -(N \{x ℓ i }). Therefore, since opt(I ′ ) ≤ n, we can consider in the following that N is included in V . In the following, we prove by contradiction that N forms a vertex cover in G. Suppose that there exists an edge (v i , v j ) ∈ E such that v i ∈ N , v j ∈ N and i < j. By removing N from G ′ , the optimal 1-center node is x 1 with a maximum weighted distance D max (x 1 ) = d(x 1 , x r n ) for any r = 1, . . . , n. We distinguish two cases:

• if v i = v 1 then D max (x 1 ) = d x1v1 + d v1vj + d vj x 1 j + d(x 1 j , x r n ) ≤ 1 + 0 + 0 + 2(n -j) ≤ 1 + 2n -4 < 2(n -1), contradiction. • if v i = v 1 then D max (x 1 ) ≤ d(x 1 , x 1 i ) + d x 1 i vi + d vivj + d vj x 1 j + d(x 1 j , x r n ) ≤ 2(i -1) + 0 + 0 + 0 + 2(n -j) = 2(n -1) -2(j -i) < 2(n -1), contradiction.
Therefore N is a vertex cover in G such that val(I, N ) = val(I ′ , N ). Consequently, ε(I, N ) = val(I,N ) opt(I) -1 ≤ val(I ′ ,N ) opt(I ′ ) -1 = ε(I ′ , N ), which achieves the proof. 2

Conclusion

We established in this paper negative results concerning the approximation of k most vital edges (nodes) and min edge (node) blocker versions of the 1-median and 1-center location problems. An interesting open question would be to establish positive results concerning the approximability of these problems. Another interesting perspective is to find efficient exact algorithms to solve them.

k

  weighted by two functions d : E → N and w : V → N and a positive integer k. Output: A subset S * ⊆ E, with |S * | = k, whose removal generates an optimal solution for the 1-median (1-center) problem in the graph G -S * of maximal value. Most Vital Nodes 1-median (1-center) Input: A connected graph G = (V, E) weighted by two functions d : E → N and w : V → N and a positive integer k. Output: A subset N * ⊆ V , with |N * | = k, whose removal generates an optimal solution for the 1-median (1-center) problem in the graph G -N * of maximal value.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Construction of G ′ from G

Fig. 5 .

 5 Fig. 5. Construction of G ′ from G with n = 4 nodes

1. If there exists a vertex cover V ′ ⊆ V of cardinality less than k in G then consider any set of vertices V ′′ ⊃ V ′ of cardinality k, and remove V ′′ from G ′ . Taking x 1 1 as the optimal 1-center node in G ′ -V ′′ , we get a maximum weighted distance max { max j=1,...,n

2. Let N * ⊆ V be any solution of k Most Vital Nodes 1-center which contains only nodes of V . Taking x 1 1 as the optimal 1-center node in G ′ -N * , we get opt(I ′ ) = max { max ℓ=1,...,n d(x 1 1 , x ℓ 2 ), max ℓ=1,...,n d(x 1 1 , x ℓ 3 )}. Since |N * | = k and opt(I)> k, N * is not a vertex cover in G. Thus, there exists at least one edge (v i , v j ) ∈ E which is not covered. This implies in G ′ the existence of a path from each x r i to each x r j for r = 1, . . . , n, passing through the edge (v i , v j ). Hence,

2

We prove now that the four problems Min Edge (Node) blocker 1median and Min Edge (Node) blocker 1-center are not 1.36 approximable, unless P=NP. These results, stated in theorems 3 and 4, are obtained by constructing E-reductions from Min Vertex Cover shown NP -hard to approximate within a factor 1.36 [START_REF] Dinur | On the hardness of approximating minimum vertex cover[END_REF].

Theorem 3. Min Edge blocker 1-median and Min Edge blocker 1center are NP-hard to approximate within a factor 1.36.

Proof : We first consider Min Edge blocker 1-median.

Let I be an instance of Min Vertex Cover consisting of a graph G = (V, E) with V = {v 1 , . . . , v n }. We construct an instance I ′ of Min Edge blocker 1median formed by a graph G ′ = (V ′ , E ′ ) and a positive integer U as follows (see Figure 4). We associate for each node v i ∈ V two nodes v i and v ′ i in V ′ and connect them in E ′ for i = 1, . . . , n. We add for each edge (v i , v j ) ∈ E, with i < j, an edge (v ′ i , v j ) to E ′ . We also add 2n nodes

. Finally, we connect x i to v i and x ′ i to v ′ i for i = 1, . . . , n. We assign the following distances to the edges of E ′ :

) ∈ E and i < j. We set w x1 = 2n 2 + 1, w xi = 1 for i = 2, . . . , n, w x ′ i = 1 and w vi = w v ′ i = 0 for i = 1, . . . , n and we consider that U = 2n 2 . We replace each edge of E ′ , except the edges (v i , v ′ i ) for i = 1, . . . , n, by the gadget given in Figure 2 where each edge is replaced by n+ 1 instead of n disjoint paths of length 2 (for edges (x 1 , v 1 ) and (x 1 , x ′ 1 ), x 1 plays the role of i in Figure 2). Observe that G ′ is designed so as to ensure that x 1 will always be the optimal 1-median node. Indeed, since the weight of vertex x 1 is 2n 2 + 1 and all