MD Hans Flaatten
email: hans.flaatten@uib.no

MRCP Susannah K Leaver
email: susannahleaver@nhs.net

MD Bertrand Guidet
email: bertrand.guidet@aphp.fr

Age is just a number: how should we triage old patients in the COVID-19 pandemic?

Age is just a number: how should we triage old patients in the coronavirus disease 2019 pandemic?

Increased numbers of Intensive Care beds are required in major surges, such as seen in the current Covid-19 pandemic. There are two possible options, available to hospitals , and these are not mutually exclusive: to increase the bed availability, and /or institute priority rules for admission of patients (triage).

Increase intensive care capacity

The first usual response is to enable the admission of an increased number of patients. This is how the surge response to the COVID-19 crisis has been managed and has led to significant pressures on hospitals, as well as intensive care units (ICUs). Expanding ICU bed capacity is not straightforward as it requires not only an increase in specialised equipment, but, more importantly, an increase in skilled health care workers (HCW). There is thus a limit to the expansion, with a trade-off between the quality of care delivered in this expanded or 'new; ICU, and the absolute numbers of extra beds [START_REF] Depuydt | Triage policy of severe covid-19 patients: what to do now?[END_REF](Figure1) . For example, in Paris and its suburbs, the normal availability of 1,100 ICU beds was increased to 2700 ICU beds at the peak of the first wave in early April 2020. Only 250 beds remained dedicated to non-COVID patients. This huge expansion was only possible by stopping scheduled medical and surgical activities enabling HCW to be moved away from the operating theatres and wards to the ICU. At the same time, a national lock-down reduced the requirement for trauma beds, which had a positive impact on ICU requirement. However, this was at a cost to non-covid patients. For example, patients with cancer saw delays to their treatment with a possible impact on their mortality [START_REF] Hanna | Mortality due to cancer treatment delay: systematic review and meta-analysis[END_REF].

Adjust ICU admission criteria:

If, despite an increased capacity, there is an ongoing demand for ICU beds the question of prioritisation and patient selection is the next step, and old patients are often the first "victim" of such a triage process. This was again shown in Paris, during the first wave (March 21 st to March 31 st ) when the percentage of patients above 75, and above 80 admitted to the ICU, dropped from 19.5 to 8.3% and 9.5% to 2.1% respectively. However, interestingly during the period mid-March to end of April, this reduction in admission to ICU of patients older than 75y did not translate into an increase in hospital mortality. The selection based on age could be justified for a number of reasons; higher mortality [START_REF] Group | on behalf of the REVA Network and the COVID-ICU Investigators. Clinical characteristics and day-90 outcomes of 4244 critically ill adults with COVID-19: a prospective cohort study[END_REF], poor recovery with loss of functional autonomy and decrease of HRQOL, and shorter life expectancy. In addition, the principle of distributive justice should probably apply with the goal of saving as many lives (or Life years) as possible.

A selection based solely on age was proposed in Italy [START_REF] Siaarti | Raccomandazioni di etica clinica per l'admissione a trattamenti intensivie per la loro sospensione, in condizioni eccezionali di squilibrio tra necessita e risorse disponibili[END_REF] but was considered unethical by several stakeholders and countries. However, most triage guidelines still use age as one of the factors that should be considered when deciding to admit or refuse a patient for admission to ICU [START_REF]Acute and critical care[END_REF][START_REF] Azoulay | Admission Decisions to Intensive Care Units in the Context of the Major Covid-19 Outbreak: local guidance from the COVID-19 Paris-Region Area[END_REF].

The question is not that simple as triage is often not a binary 'Yes/No' decision. We are not on a battlefield giving definitive triage decisions. The patient might be denied ICU admission but be admitted into an intermediate care unit or even a regular ward and receive good care including steroids, non-invasive ventilation (NIV), high flow oxygen and awake prone positioning. The patient may subsequently be admitted to ICU if they deteriorate despite the above measures. Hence, triage decisions are continuously being revised according to the patient's response to treatment. By contrast, a patient might be admitted to ICU and after a few days, their life-sustaining treatment (LST) is limited (or withdrawn) following deterioration despite optimal ICU treatment or new information of underlying diseases that had not been documented upon admission.

Although older age is frequently associated with frailty and associated findings such as sarcopenia, co-morbidity, cognitive decline, and a poor nutritional status, age alone does not tell us the whole story. [START_REF] Guidet | Caring for the critically ill patients over 80: a narrative review[END_REF][START_REF] Flaatten | Frailty: we need valid and reliable tools in critical care[END_REF]. Therefore, decisions about admission to the ICU should not just be based on crude chronological age, but on the patient's ability to benefit from treatment versus the risk of harm. In a pandemic, the competing needs of other patients should also be considered [START_REF]Acute and critical care[END_REF].

However, an intensivist is frequently required to make decisions, sometimes in the middle of the night, often with minimal available information, about whether a patient should be admitted to ICU. To aid these decisions a simple, reproducible easy-to-use tool to characterise frailty is of great value. The clinical frailty scale (CFS) fulfils these specifications [START_REF] Flaatten | Frailty: we need valid and reliable tools in critical care[END_REF].

We have demonstrated that CFS is the best predictive factor for mortality at one month in patients above 80 years [START_REF] Flaatten | The impact of frailty on ICU and 30-day mortality and the level of care in very elderly patients (≥ 80 years)[END_REF][START_REF] Guidet | for the VIP2 study group. The contribution of frailty, cognition, activity of daily life and comorbidities on outcome in acutely admitted patients over 80 years in European ICUs: The VIP2 study[END_REF]. Other geriatric parameters do not improve the prediction model [START_REF] Guidet | for the VIP2 study group. The contribution of frailty, cognition, activity of daily life and comorbidities on outcome in acutely admitted patients over 80 years in European ICUs: The VIP2 study[END_REF].

Assessment of frailty using CFS when applied to COVID patients, over the age of 70, has also been found to be an independent prognostic factor for 3-month mortality [11]. In addition, in a study of 1564 patients over 18 years old admitted to hospital with COVID-19, disease outcomes were better predicted by frailty than either age or comorbidity [START_REF] Hewitt | The effect of frailty on survival in patients with COVID-19 (COPE): a multicentre, European, observational cohort study[END_REF].

CFS is now included in several national guidelines such as UK, France and Netherland, and shortly in Denmark and Norway. Even though, frailty has been included into 'best practice' predictions, these recommendations based on frailty have been challenged [START_REF] Lewis | Rationing care by frailty during the COVID-19 pandemic[END_REF].

Besides the issues discussed above, the severity of the acute illness and also the patients' wishes and advance care plans must be assessed [START_REF] Oliver | Should advance care planning enter the mainstream[END_REF] . However, it is difficult for patients to make an informed decision when the reality of intensive care medicine is unknown to them. Many people do not appreciate that intensive care just buys time while an acute condition is being treated. It will not benefit those who deteriorate from a long-standing chronic condition. If the public was better informed into what intensive care can achieve, and this was discussed with those with significant co-morbidity in advance, at an appropriate time, this may reduce the unrealistic hopes and expectations of both patients and their relatives.

Only a few guidelines explicitly discuss treatment withdrawal in ICU. This option has been discussed in Sweden and Germany where it has been considered unlawful by the Ethics council and has now been escalated to the constitutional court in Germany.

Prioritising patients for ICU admission, and in particular during ICU treatment, is complex and difficult even under normal circumstances [START_REF] Van Heerden | The wave of very old people in the intensive care unit -a challenge in decision-making[END_REF]. In many countries, age alone is not usually considered a valid "stand-alone" criterion. During a surge, such as the present pandemic, it is tempting to use simple solutions for triage with readily available information.

It is therefore not surprising that age is considered. We would suggest, as discussed, that adding a simple evaluation of frailty status at admission will give us a superior and more robust platform for decision-making.

Figures shows the effect of increasing ICU capacity on quality of care.

A point is reached (A) where increasing capacity impinges on quality of care. As the two lines cross and capacity reaches its limit (B), stricter admission criteria have to be implemented.

Capacity (green line)

Quality of care (red line) Time A B

Baseline quality

Baseline capacity A = time when quality starts to drop ≈ when capacity approach the double B = time when very strict admission criteria are implemented


Shaw Julie Vatain

FACE TO FACE ON THE FOREIGN STAGE Translating contrast and symmetry in two scenes by Wilde and

Keywords: Translation. Theatre. Comedy of manners. Tone. Accent. Rhythm. Dramatic efficiency. Wilde, Op. 4: The Philanderer, Op. 5: An Ideal Husband

The rules and stakes of translation in the theatre are modified by the immediate impact of the dialogue as well as its incarnation in the voice and body of the actors. Using two precise examples of confrontation in the comedy of manners, this article focuses on how to translate into French the critical stance of the Irish playwright observing London society, and explores some of the linguistic and rhythmical difficulties implied by the complex use of tone and accent. Résumé:

L'impact immédiat du dialogue, et son incarnation par la voix et le corps des comédiens, modifient au théâtre les enjeux de la traduction. A partir de deux exemples précis de face à face humoristique dans la comédie de moeurs, cet article s'intéresse à la traduction en français du regard critique irlandais sur la société londonienne, et s'efforce d'explorer quelques-unes des difficultés langagières et rythmiques qu'impliquent le jeux sur les tons et les accents.

My dear Shaw, I must thank you sincerely for Op. 2 of the great Celtic School. I have read it twice with the keenest interest. I like your superb confidence in the dramatic value of the mere facts of life. I admire the horrible flesh and blood of your creatures, and your preface is a masterpiece-a real masterpiece of trenchant writing and caustic wit and dramatic instinct. I look forward to your Op. 4. As for Op. 5, I am lazy, but rather itching to be at it. When are you coming to the Haymarket? Sincerely yours, Oscar Wilde 1 In these lines addressed to his fellow playwright and Irishman George Bernard Shaw, Oscar Wilde appears to be heralding the development of a new dramatic tradition. The letter dates from 1893, and therefore refers to the early works of both playwrights; indeed Wilde is ranking Shaw's first play Widower's Houses along with his own Lady Windermere's Fan and A Woman of No Importance as beacons of what he calls, somewhat ironically, the Celtic School.

It is a well known fact that Wilde and Shaw, born in Dublin two years apart from each other, both left for England at the age of twenty, never or hardly ever to return. They spent most of their lives in England and abroad, each in his own way becoming a striking public figure, as well as a man of the stage and a social critic-whether through the advocation of individual freedom and aestheticism, or through the Fabian society and the promotion of political consciousness on and off stage; to put it roughly. The aim of this article will not be to ascertain how or whether Wilde and Shaw fit in with the other Irish playwrights, but to show how they dramatise England and how this will, in turn, need to be taken into account in any translation into French. Using two confrontation scenes in which the tension of the dialogue results from contrasts, parallelisms and rhythmical effects, we will study how the society of London is portrayed in The Importance of Being Earnest and Pygmalion.

In Earnest, we will focus on the end of act II, when Algernon and Jack fight over the plate of muffins and the right to be christened by Dr Chasuble, in a clever duet of echoing accusations, claims, and aphorisms. In Pygmalion, we will study the beginning of act II, when Eliza unexpectedly shows up in Wimpole Street in her best feathered hat, asking for lessons in phonetics, which triggers a comical power struggle between Higgins and her, under the critical glance of Mrs Pearce and Colonel Pickering2 .

Both playwrights depict a society in which they are at once insiders and outsiders, perhaps the Irish ("Celts") observing the English ("Saxons/Normans"). This observer's stance is highly theatrical, as it leads to an acute awareness of the processes of speech, its rhythms, vocabulary, mannerisms and sounds-an awareness sometimes bordering on caricature. Pierre Larthomas, author of an enlightening study on dramatic language, writes that in the theatre language is "caught in the act", intercepted and placed in front of us for our amazement: « Le théâtre, c'est du langage surpris. Le langage est comme placé devant nous pour que nous l'admirions »3 . I wish to study the dramatic efficiency of this continual foregrounding of language, and to study it through the angle of translation.

Translation acts as a filter, a screen. Just like acting or directing, it becomes an encounter of subjectivities, sensitivities and modes of expression, through which the dramatic text can be achieved, disfigured, recreated-sometimes revealed. In order to explore this idea of recreating the text, let us analyse the stuff comedies of manners are made of, and study the rendering of social boundaries, tone and accent in both plays: thus we will be able to see how translation can invent voices for the characters, and create tools for the actors.

Social and geographical situation

Although Pygmalion is presented as "A romance in five acts", it offers such a comical array of social types, from the dustman to the duchess, sparing neither convention nor eccentricity, that it also fits the genre of the comedy of manners. And Earnest, epigrammatically termed "A trivial comedy for serious people", belongs to that same tradition, with its dandies, determined young ladies, sentimental governess and its paragon of Victorian society called Lady Bracknell. The two plays therefore take their place in a long line of comedies, which also includes the works of Congreve or Sheridan.

Unlike tragedies, whose setting can remain indefinite or allegorical, comedies of manners are necessarily fraught with cultural allusions, since by definition they give a satirical portrait of a certain social group at a certain time. Hence the following question for directors and translators alike: how can such comedies still work when the spectators are far removed from the characters in time, or space, or both? The question of adaptation-be it to update the costumes or to modernise the language-emerges in fact as a secondary one, to be considered after the more essential points of recreating the comic structure and dramatic efficiency. While clarity is necessary, transposition is not. Tom Stoppard makes a similar point when he draws the following conclusion from contemporary ideas on staging Shakespeare: "I don't think theatre works as parable; it works as metaphor. … The power of metaphor is that it impacts, and just goes where you happen to see it from"4 . In other words, an audience can be trusted to find meaning in a play, no matter how strange or remote the setting. In the case of a comedy of manners, the satirical portraying of human nature remains intact, while the significance of the cultural context shifts slightly, losing some of its direct impact and political resonance, but acquiring a "period" charm, which ironically provokes a mistaken sense of superiority in the modern spectator. In both Pygmalion and Earnest, the distance between the French spectator and the English characters becomes part of this observer's stance earlier alluded to. It ties in with the distance between the Irish-born playwright and his English target, and enhances the plays' liberating, ironical exploration of the absurdities of social conventions. It paves the way for translation.

In their opening stage directions, both plays are significantly situated in time and space. Wilde simply uses a name, "Half-Moon Street"5 , to indicate the elegant atmosphere of Algernon's flat and his bachelor's style of living, which in French editions leads to the addition of a footnote for the use of set-designers. As for Pygmalion, it opens with one of Shaw's characteristically detailed stage directions:

London at 11:15 pm. Torrents of heavy summer rain. Cab whistles blowing frantically in all directions. Pedestrians running for shelter into the portico of St Paul's church (not Wren's cathedral but Inigo Jones' church in Covent Garden vegetable market). … THE DAUGHTER is standing in the space between the central pillars, close to the one on her left. (P 669) Whether an audience in Paris or New York would know which particular church the set is meant to represent remains doubtful, but they would nevertheless recognise a London setting, and relate to the electric mood of a large city during a storm. Shaw's precise indications create an atmosphere which is efficient both in terms of realistic impressions and in emotional terms, the perfect setting for the sensational effect which Professor Higgins is about to have on the motley crowd huddling under the pillars of St Paul's.

Defining social class: ladies and taxis and stockbrokers

In both plays, the characters are interested either in preserving social hierarchy, or in playing with it. Eliza Doolittle and Jack Worthing both manage to create parallel personalities for themselves-the Hungarian princess and Ernest-and in order to achieve their goals, both must prove their worth in good society (though what Jack can only prove through others by acquiring an aristocratic family, Eliza can prove on her own, through her constancy and merit in learning to speak "more genteel"). The rules and boundaries of society consistently remain in the background, a fact betrayed, for instance, by the constant use of titles: "Lord", "Lady", "Colonel", "Professor", "Gentleman", etc. Mrs Pearce uses such an argument to reprove Eliza for her forwardness: ELIZA: Did you tell him I come in a taxi? MRS PEARCE: Nonsense, girl! What do you think a gentleman like Mr Higgins cares what you came in? ELIZA: Oh, we are proud! He ain't above giving lessons, not him: I heard him say so.

The housekeeper sticks to conventional class distinctions, and contrasts a deprecatingly unqualified pronoun, "you", with the expression "a gentleman like Mr Higgins", imposing enough to speak for itself. Eliza, on the contrary, brings the discussion back to the grounds of money, or what she calls "business": the taxi, indicating wealth, and the fact that Higgins, no matter how superior his attitude, gets paid to teach phonetics, establish her full right to be there as a client. She later claims respect on similar grounds: "I won't be called a baggage when I've offered to pay like any lady", which could be rendered as "j'propose de payer comme les dames", though most translators choose to use the English titles ("comme n'importe quelle lady", "un gentleman comme monsieur Higgins"6 ), preferring to keep the picturesque aspect of the original words, and giving the actress playing Eliza an added opportunity to mispronounce something.

To this background tableau of Lords and Ladies, Wilde ironically adds parallel social groups, such as that of stockbrokers ("It is very vulgar to talk about one's business. Only people like stockbrokers do that, and then merely at dinner-parties"), or that of vegetarians ("I never go without my dinner. No one ever does, except vegetarians and people like that"). Such authoritative phrases sound delightfully nonsensical, while providing a double satire: that of people who behave in unusual or uneducated ways, and that of the all-powerful reign of categories and class boundaries. Here the translator must make sure that the phrasing sounds sufficiently superior, especially for the euphemistic and disapproving "people like that". For example: « Il n'y a que les gens de l'étoffe des agents de change pour se comporter ainsi » or « Personne ne se comporte ainsi que les végétariens et leurs pareils ». This can help the French actor recreate the satirical and narcissistic streaks in Algernon's tone.

Awareness of language and tone

Tone proves indeed a crucial element in translation. There lies most of the comedy, aside from the more farcical visual elements. In both plays the characters are supremely conscious of the powers attached to mastering language.

Algernon uses this power to tailor reality to his own wishes, relying on wit and repartee to imprison his friend in the web of his own lies. Thus, he pursues the conversation unto absurdity and manages to destabilise his opponent, arguing that Jack should not get christened since his imaginary brother recently died of a severe chill, which the latest improvements in science have declared to be hereditary. Imaginary science and fictional brothers, when phrased logically, can thus fetter reality. As for Higgins, he is professionally aware of what language can do, and delights in analysing it. He admires the rhetorical skills of Alfred Doolittle: "Observe the rhythm of his native woodnotes wild. … Sentimental rhetoric! That's the Welsh strain in him"(P 707), and claims to use swearwords to strictly poetical ends. He indeed maintains that the adjective "bloody", when applied to his boots, the butter and the brown bread, is: "Mere alliteration, Mrs Pearce, natural to a poet" (P 703).

All this implies that the features of the characters' speeches are not only theatrical but also socially significant, and must be recreated in French. The scene from Earnest thus calls for particular attention in the translation of adjectives and adverbs, which are often hyperbolical, and enhance the impression of a humorously superior attitude. Adverbs such as "perfectly", "absolutely", "thoroughly", "particularly" or "entirely" punctuate the text at every line, while the many adjectives are either extremely positive, "wonderful", or extremely negative, "ghastly". Frequent exclamations such as "Good Heavens!" and constant dismissive judgements through "Nonsense!" or "Absurd!" also support the notion of language as permanently excessive. Two of the attributes applied to the characters, "heartless", and "exploded", prove more difficult to translate than the rest, for they occur several times in different grammatical contexts 7 . Savine literally translates "heartless" as « sans coeur », which proves problematic when used as a noun: « c'est être un parfait sans coeur ». Déprats and Aquien prefer to use the noun and adjective « insensible/insensibilité », which offer greater grammatical flexibility. Another possibility could be the term « scélérat », whose combination of sibilant and harsh consonants is similar to that of "heartless", with equal possibilities of added vocal stress, and which seems to fit the image of an exaggerated accusation: « c'est te conduire en parfait scélérat que de manger des muffins ». The difficulty with "exploded", on the other hand, is that the author plays with several meanings of the word. Here Jack uses it to mean "exposed": "your friend Bunbury is quite exploded"; but when it appears again in the next act Lady Bracknell understands it differently: "Exploded! Was he the victim of a revolutionary outrage?" (E 156). Some of the published translations fail to use the same word in both scenes, thus missing the coherence of Wilde's pun; the only way to use the notion of explosion in French, it seems, is to switch from a past participle to a noun: « la seule satisfaction que je trouve dans cette déplorable affaire, c'est l'explosion totale de ton ami Bunbury »; otherwise, translators have looked for different images which work both concretely and metaphorically, such as Aquien's « ton ami Bunbury s'est littéralement volatilisé ».

Professor Higgins, too, displays a towering personality and strong command of language in his use of adjectives, which are carefully-chosen, forceful and often alliterative:

A woman who utters such depressing and disgusting sounds has no right to be anywhere-no right to live. Remember that you are a human being with a soul and the divine gift of articulate speech: that your native language is the language of Shakespeare and Milton and The Bible; and don't sit here crooning like a bilious pigeon. (P 679) "Bilious pigeon" is just one of the many colourful, deprecating images which Higgins uses to refer to Eliza, such as "creature", "baggage", "squashed cabbage leaf", "incarnate insult to the English language", and "draggletailed guttersnipe". The difficulty here is to preserve the misogynistic eccentricity of Higgins' insults, while still not sounding completely improbable (which would be the effect of « colis » for "baggage"), or falling too easily into the trap of French clichés, such as « petite effrontée » or « épouvantail », which, though accurate, tend to flatten the powerful effect of the Professor's idiom. Literally "this draggletailed guttersnipe" translates as « cette bécassine oiseau des rues qui traîne sa queue dans le caniveau ». This sounds a little too outlandish to be understood, but on the other hand Michel Habart's choice of « ce traîne-jupons, cette petite piaf des rues » replaces the Cockney flower-girl with a clearly Parisian reference, endowed with certain sentimental connotations. Perhaps something along the lines of « ce traîne-jupons, cet oiseau des caniveaux » would preserve the inventive rudeness of the expression, while still making enough sense for the image to be real and vivid upon a first hearing.

Accent

Finding a voice for Jack, Algernon and Professor Higgins in French leaves us facing the last and most delicate question of Eliza Doolittle's grammar and accent, to which there is no ideal answer.

Accents are a recurring problem when it comes to the translation of Anglophone drama, as well as the dubbing of films, for they are used consciously, for effect. The worldwide variety of accents in English, whether national, social, or both, obviously has no easy or absolute equivalent in French, and the solution is bound to be a compromise. To take an example from a different context, Tennessee Williams, rightly perceived as a playwright of the American South, whose writing is pervaded with instances of southern turns of speech and vowel-lengthening, can also surprise us when he uncharacteristically switches to very British phrases and modes of expression in the short play I Rise in Flame, Cries the Phoenix, staging the death of D. H. Lawrence. How can we make such a radical change, within the coherent rhythms and images of the same author, palpable in translation?

A similar question is raised, obviously, with added political resonance, when it comes to any Irish playwright who uses Hiberno-English. Accents are rarely used to produce a purely picturesque effect, and perhaps a different solution can or must be found each time, depending on what use the playwright makes of them. They define characters-age, education, aspirations-and situate them with regards to each other; therefore the first question to be considered is whether or not these accents are presented, within the system of the play, as deviating from a norm. This is the case in Pygmalion. Several creative attempts have been made by translators to transpose a regional accent into the target language by seeking a close linguistic or historical equivalent. Judith Lavoie thus recommends the use of French « créole » to render Jim's dialect in Huckleberry Finn, while Bill Findlay and Martin Bowman tap the linguistic resources of the Scottish vernacular in order to translate the « joual » of French Canadian playwright Michel Tremblay. Françoise Morvan's versions of Synge, for their part, take their inspiration from the dialects of Brittany 8 . While such approaches often lead to texts that are verbally inventive and rhythmically efficient, they do raise some theoretical issues as to the size and sense of belonging of the receiving community, as well as the political significance of the accents, which can be materially altered. They would also deserve an analysis of their own, which cannot be attempted here.

Suffice it to say that in Pygmalion, the social and political implications of Eliza's Cockney, which according to Shaw himself would prove "unintelligible outside London" (P 671), prove crucial to the story as well as the comedy. The entire plot rests on the progress of a girl from the slums of Lisson Grove to Higgins' "laboratory"-aptly situated in a "medical" street-and then on to the genteel atmosphere of a Chelsea drawing-room, or the splendours of an embassy party. The emphasis on the word "romance" in the title and the prevalence of humour tend to down-play the general social criticism in favour or the particular story, but all the same the implications of accent are discussed at length, given that "this is an age of upstarts" (P 679). Phonetics and social geography go hand in hand, a theme which according to Nicholas Grene can be traced back to Shaw's experience upon moving to England, and the self-consciousness surrounding his own Dublin accent. Grene quotes Shaw's review of Mrs Patrick Campbell in Sardou's Fedora (1895), in which he criticises the imperfect diction of the actress who was later to create the role of Eliza:

In order to secure refinement of tone, she articulates with the tip of her tongue against her front teeth as much as possible like the snobbish Irishman who uses it as a cheap recipe for speaking genteel English. 9

It is this deep-rooted awareness of the mechanisms and significance of phonetics which leads Shaw to declare in his preface: "The reformer we need most today is an energetic phonetic enthusiast: that is why I have made such a one the hero of a popular play" (P 659). Eliza's faulty English is defined against the standard of Higgins' apt command of language and tone. Shaw abandons his attempt to transcribe the Flower Girl's dialect phonetically after a mere 8 See Judith Lavoie's thesis, or her article, « Le français créolisé comme option de traduction du vernaculaire noir américain », Présence Francophone, n°51, 1997, pp. 117-138. Several plays from Québec have been translated into Scots by the Traverse Theatre Company ; for exemple Michel Tremblay's Messe solennelle pour une pleine lune d'été, translated by Bill Findlay & Martin Bowan as Solemn Mass for a Full Moon in Summer, London, Nick Hern Books, 2000. And as for Synge, see for instance Françoise Morvan's version of Baladin du monde occidental (Playboy of the Western World), Bedée, Folle Avoine, 1993. 9 Quoted in Nicholas Grene's insightful introduction to a recent edition of the play, Pygmalion, London, Penguin, 2000, p. vii. three lines, but he continues to write using her mistaken grammar and syntax, which the translation should seek to emulate.

Eliza's English features the usual cockney characteristics, such as double negatives ("I don't want no gold and no diamonds"), mistaken verb forms such as "ain't", "I come in a taxi" or "if you was a gentleman", as well as missing agreements such as "Woolly towels, there is" or "I know why ladies is so clean". Phonologically, Shaw insists on the h-dropping, the frequent condensation of two words into one ("Garn!"), and the lengthening of vowels with the frequent addition of the vowel for which there is no letter, //. Though grammatical errors in English and French are not exactly symmetrical, it is usually possible to recreate approximately the same number of mistakes, even if it means using the wrong noun instead of the wrong verb, and vice versa. For "if you was a gentleman", we can rely on a similarly common mistake in French to render the inaccuracy and write « si vous seriez gentleman ».

For "Did you tell him I come in a taxi?", on the other hand, it seems difficult to use the wrong verb form, but it is possible to alter the structure of the interrogative clause, with « Vous lui avez dit comment qu'je suis v'nue en taxi? » Besides, elisions provide an efficient way to indicate the relaxed and inaccurate quality of Eliza's diction.

Eliza on a French stage will not be Cockney. She may become a little Parisian, because through analogy the actress may well tend to play her as a variation on the « titi parisien »-or she may simply be speaking a form of inaccurate French in which each mistake is recognizable, but which is impossible to place precisely because it was more or less invented by the translator. This is perhaps what translation should aim for; the rest being up to the vision of the director and the talent of the actor. The language of theatre is in essence not real, more dense, more pure and more efficient than everyday speech. It is written for effect, and to carry dramatic potential. Which is why the best strategy may well be to translate the accent and inaccurate grammar within the system of the play, paying particular attention to the way in which the original proceeds, rather than to start with a preconceived idea of what a character should sound like in French. Antoine Vitez warns us against the dangers of transplanting a character too clearly into one particular region or character-type, arguing that the added connotations of the translation end up blocking our view of the original, and adding that although there is no definitive solution, there is a creative process which strives to transform the receiving language little by little:

Il n'y a pas de solution, il n'y en a pas de définitive. La solution ne peut pas être scientifique. Elle ne peut qu'être artistique au sens propre : de la nature de la métamorphose. De la transformation. […] Pour cela il faut jouer sur la syntaxe. Légèrement la gauchir, la transformer… [START_REF]I am borrowing this quote, which can originally be found in Vitez[END_REF] This process is never "comfortable", but not only is it quite respectful of the original, it is also truly theatrical, relying on the actors' input to complete the equation.

Tools for actors

Peter Brook states that "In the theatre, every form once born is mortal, every form must be reconceived" [START_REF] Brook | The Empty Space[END_REF] , and this seems to be equally true of acting and translating. The two have a lot in common; both being processes of re-creation, which involve struggling with the text and identifying with it in order to present a version of it. This is symbolised by the French term « interprète », which refers to both actor and translator, and enables Jean-Michel Déprats to write: « Le traducteur est le premier interprète de l'oeuvre » [START_REF] Déprats | Traduire Shakespeare. Pour une poétique théâtrale de la traduction shakespearienne[END_REF] . The analogy does not merely work metaphorically, but concretely as well, even physically-the dialogue has to go through the body and imagination and breathing rhythms of the translator as much as it does in the case of the actor.

Let us therefore finish by stressing this notion of rhythm, which is perhaps the most important tool a translator can provide an actor with. Small details, for instance parallel adverbs in the beginning of sentences, can be instrumental in enhancing the mirror effect which Wilde creates between the lines of his two dandies: "Well, that is no business of yours" / "Well, I can't eat muffins in an agitated manner". In spite of their apparent insignificance or superfluity, it is important to translate the symmetrical way in which these elements help tie the dialogue together: « Enfin, il faut bien prendre quelque chose au sérieux », « Enfin, la seule petite satisfaction que j'éprouve… » Similarly, Eliza punctuates many of her sentences with tags and repetitions: "I'm come to have lessons, I am", or "He ain't above giving lessons, not him". Although French does not feature the same grammatical possibilities, the translation should strive to reproduce the rhythm of these sentences, indicating that the flower-girl is trying to reassure herself at the end-her favourite declaration being: "I'm a good girl, I am". The French translation could read: « J'suis v'nue pour prendre des leçons, voilà pourquoi » and « Il a pas honte de donner des leçons, ça non », recreating this effect of enhancing the assertion by repeating one of its elements, and placing a strong and stubborn emphasis on the end of the line. The use of monosyllables should not be neglected either, since they offer many possibilities of varying intonations and stress on a particular word, for instance: "I don't want you here", « Je ne veux pas de toi ici ». This sounds simple and obvious enough, but such a vigilant awareness of the importance of rhythm in speech, of the vocal and breathing effects to which tempo can lead, may be the key to writing a translation which is dramatically efficient.

As a final, and perhaps more striking example of patterns in rhythm, we can note that a recurring effect in scenes of confrontation is sentence symmetry-stichomythia in verse-of which we find a derived version in Earnest: JACK: I wanted to be engaged to Gwendolen, that is all. I love her. ALGERNON: Well, I simply wanted to be engaged to Cecily. I adore her. JACK: There is certainly no chance of your marrying Miss Cardew. ALGERNON: I don't think there is much likelihood, Jack, of you and Miss Fairfax being united.

The logic of this passage is a combination of mirrored sentences and efforts to outbid each other. Some of the effects prove fairly easy to render, such as the gradation « je l'aime/ je l'adore », or the double rhythm of Jack's first line: "that is all. I love her", which becomes « voilà tout. Je l'aime », giving us two words instead of three, but still the same number of syllables in French. As to the rest, given that these lines are meant to be spoken fairly quickly, it seems best to avoid structures that are too involved or difficult to wrap one's tongue around, especially since impersonal turns of phrase often sound clumsy in French. One possible translation, therefore, is: JACK : Je souhaitais me fiancer à Gwendolen, voilà tout. Je l'aime. ALGERNON : Eh bien moi, je souhaitais simplement me fiancer à Cecily. Je l'adore. JACK : Il est certain que tu n'as aucune chance d'épouser Miss Cardew. ALGERNON : Je ne vois guère de probabilités, Jack, en faveur de ton union avec Miss Fairfax.

Having created a world of doubles, and a situation where two young men, both provided with fictional "rascally" counterparts and with parallel love troubles, farcically find themselves face to face around a single plate of muffins, Wilde composes his dialogue with the rigorous symmetry of a "verbal opera"13 , using balance and precision in language to enhance the comedy by combining farce with sophistication.

We could thus apply to Wilde and Shaw the words in which Virginia Woolf describes the plays of Congreve: "Miraculously pat, on the spot, each speaker caps the last, without fumbling or hesitation, … alive and alert to their fingertips"14 . Rendering this sense of immediacy and equilibrium makes translation efficient, providing actors with possibilities for symmetry and contrast in tone and gesture. Translation can thus recreate on the French stage the critical point of view of the observer, turning the added distance between characters and audience not into an obstacle, but into a different set of echoes and resonances.

Comedy bears the deceptive appearance of a light, polished surface, but it requires accuracy, attention to rhythm and a knowledge of how actors work with the text, on the part of the translator. Shaw pinpoints this false notion of simplicity when he ironically replies to Wilde's critics in his review of An Ideal Husband (having begun this article with Wilde on Shaw, it seems only fair to conclude it, symmetrically, with Shaw on Wilde):

[His critics] protest that the trick is obvious, and that such epigrams can be turned out by the dozen by any one lightminded enough to condescend to such frivolity. As far as I can ascertain, I am the only person in London who cannot sit down and write an Oscar Wilde play at will. The fact that his plays, though apparently lucrative, remain unique under these circumstances, says much for the self-denial of our scribes. Mr Wilde plays with everything: with wit, with philosophy, with drama, with actors and audience, with the whole theatre. Such a feat scandalizes the Englishman, who can no more play with wit and philosophy than he can with a football or a cricket bat. … All the literary dignity of the play … cannot quite overcome the fact that Ireland is of all countries the most foreign to England, and that to the Irishman (and Mr Wilde is almost as acutely Irish an Irishman as the Iron Duke of Wellington) there is nothing in the world quite so exquisitely comic as an Englishman's seriousness. 15

  Jean-Michel Déprats, L'Importance d'être Constant d'Oscar Wilde, pour la mise en scène de Jérôme Savary au théâtre national de Chaillot, Paris, L'Avant-scène N° 981, 1996. Albert Savine, L'Importance d'être Constant (1911) d'Oscar Wilde, in OEuvres, Paris, Librairie générale française, 2000.

Oscar Wilde, The Importance of Being Earnest (1895), London, Routledge, 1993, pp. 136-144. George Bernard Shaw, Pygmalion (1913), in Collected Plays, London, The Bodley Head, 1972, pp. 687-698.All references to the text of the plays will be given in these editions. Additional page numbers will be mentioned only for quotations outside these two scenes, with the letters E for Earnest and P for Pygmalion. As for the translations, where no particular reference is given, they are my own.

Pierre Larthomas, Le Langage dramatique, sa nature, ses procédés, Paris, Armand Colin, 1972, p. 60.

Tom Stoppard, "The Event and the Text", in Tom Stoppard in Conversation, ed. by Paul Delaney, Ann Arbor, The University of Michigan Press, 1994, p. 207.

"Morning-room in Algernon's flat in Half-Moon Street" is the first stage direction of the play (Half-Moon street was a fashionable street for bachelors in Westminster), p. 1.

These are the choices made for instance by Michel Habart in his translation, Pygmalion, Paris, l'Arche, 1983, p.26-27.

The following translations/adaptations of Wilde's play are the four most frequently published and produced in France. Anouilh's version does not feature our scene at all ; the other three have been taken into account : Nicole et Jean Anouilh, Il est important d'être aimé, Adaptation d'Oscar Wilde, Paris, Papiers, 1985. Pascal Aquien, L'Importance d'être Constant d'Oscar Wilde, édition bilingue, Paris, Flammarion, 2000.

W. H. Auden declared The Importance of Being Earnest "perhaps the only purely verbal opera in English". Quoted in Sos Eltis, Revising Wilde, Oxford, Clarendon Press, 2003, p. 170.

Virginia Woolf, "Congreve's Comedies", in Congreve Comedies, A Selection of Critical Essays, ed. By P. Lyons, London, Macmillan, 1982, p. 96.

George Bernard Shaw, "Review of An Ideal Husband", Saturday Review (12 Jan. 1895), reproduced in Karl Beckson: Oscar Wilde, The Critical Heritage, London, Routledge, 1970, p. 176-177.


Wen Sun

Jin-Kao Hao

Xiangjing Lai
email: laixiangjing@gmail.com

Qinghua Wu
email: qinghuawu1005@gmail.com

On feasible and infeasible search for equitable graph coloring

Keywords: Equitable coloring, tabu search, heuristics, penalty-based fitness function

An equitable legal k-coloring of an undirected graph G = (V , E) is a partition of the vertex set V into k disjoint independent sets, such that the cardinalities of any two independent sets differ by at most one (this is called the equity constraint). As a variant of the popular graph coloring problem (GCP), the equitable coloring problem (ECP) involves finding a minimum k for which an equitable legal k-coloring exists. In this paper, we present a study of searching both feasible and infeasible solutions with respect to the equity constraint. e resulting algorithm relies on a mixed search strategy exploring both equitable and inequitable colorings unlike existing algorithms where the search is limited to equitable colorings only. We present experimental results on 73 DIMACS and COLOR benchmark graphs and demonstrate the competitiveness of this search strategy by showing 9 improved best-known results (new upper bounds).

As a variant of the conventional graph coloring problem (GCP), the decision version of the ECP is NP-complete. is can be proved by a straightforward reduction from graph coloring to equitable coloring by adding sufficiently many isolated vertices to a graph and testing whether the graph has an equitable coloring with a given number of colors [START_REF] Furma | Equitable coloring of graphs[END_REF]. e ECP model has a number of practical applications related to garbage collection [START_REF] Tucker | Perfect graphs and an application to optimizing municipal services[END_REF], load balancing [START_REF] Blazewicz | Scheduling computer and manufacturing processes[END_REF], timetabling [START_REF] Kitagawa | An existential problem of a weightcontrolled subset and its application to school timetable construction[END_REF], scheduling [START_REF] Ding | An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem[END_REF][START_REF] Irani | Scheduling with conflicts, and applications to traffic signal control[END_REF][START_REF] Meyer | Equitable coloring[END_REF] and so on.

Much effort has been devoted to theoretical studies of the ECP. For example, Meyer conjectured that χ e (G) ≤ ∆(G) for any connected graph except the complete graphs and the odd circuits, where ∆(G) is the maximum vertex degree of G [START_REF] Meyer | Equitable coloring[END_REF]. is conjecture has been proved to be true for trees and graphs with ∆(G) = 3 [START_REF] Chen | Equitable coloring and the maximum degree[END_REF], connected bipartite graphs [START_REF] Lih | On equitable coloring of bipartite graphs[END_REF], graphs with the average degree at most ∆/5 [START_REF] Alexandr | On equitable ∆-coloring of graphs with low average degree[END_REF] and outerplanar graphs [START_REF] Alexandr | Equitable colorings of outerplanar graphs[END_REF]. Bodlaender and Fomin [START_REF] Hans | Equitable colorings of bounded treewidth graphs[END_REF] identified that the ECP can be solved in polynomial time for graphs with bounded treewidth. Furma ńczyk and Kubale investigated the computational complexity of the ECP for some special graphs [START_REF] Furma | e complexity of equitable vertex coloring of graphs[END_REF]. Yan and Wang discussed the ECP for kronecker products of the complete multipartite graphs and complete graphs [START_REF] Yan | Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs[END_REF].

From a perspective of solution methods for the ECP in the general case, several exact algorithms have been proposed. Specifically, Bahiense et al. presented a branch-and-cut algorithm based on a formulation by representatives [START_REF] Bahiense | A branchand-cut algorithm for the equitable coloring problem using a formulation by representatives[END_REF] and showed computational results only on a set of small random instances (with 60 vertices). Méndez-Díaz et al. investigated a polyhedral approach [START_REF] Méndez-Díaz | A polyhedral approach for the equitable coloring problem[END_REF] and a Dsatur-based algorithm [START_REF] Méndez-Díaz | A DSATUR-based algorithm for the Equitable Coloring Problem[END_REF] and presented computational results for a subset of benchmark instances from the DIMACS and COLOR competitions.

Given the computational challenge of the ECP, exact algorithms suffer inevitably from an exponential time complexity and thus are only applicable to graphs of limited sizes (typically with less than 150 vertices). To handle larger graphs, heuristic algorithms are o en used to find sub-optimal solutions in a reasonable time frame.

e first heuristics are based on greedy constructive principles [START_REF] Furma | Equitable coloring of graphs[END_REF]. More recently, two powerful heuristics were proposed, which are based on the tabu search method: TabuEqCol [START_REF] Méndez Díaz | A tabu search heuristic for the equitable coloring problem[END_REF] and BITS [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF]. TabuEqCol is a straightforward adaptation of the well-known Tabu-Col algorithm designed for the classical graph coloring problem [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF][START_REF] Hertz | Using tabu search techniques for graph coloring[END_REF]. BITS improves TabuEqCol by embedding a backtracking scheme under the iterated local search framework.

We observe that unlike the popular graph coloring problem for which many heuristic algorithms have been proposed, research on heuristics for the ECP is quite limited and is still in its infancy. In particular, one important feature of the problem identified by its equity constraint is not explicitly explored by the existing algorithms, which visit equity-feasible solutions only. On the other hand, it is well known that for constrained optimization problems (like the ECP), allowing a controlled exploration of infeasible solutions may facilitate transitions between structurally different solutions and help discover high-quality solutions that are difficult to locate if the search is confined to the feasible region [START_REF] Glover | e case for strategic oscillation[END_REF].

In this work, we present a feasible and infeasible search algorithm for the ECP which enlarges the search to include equity-infeasible solutions. To prevent the search from going too far away from the feasible boundary, we devise an extended penalty-based fitness function which is used to guide the search for an effective examination of candidate solutions. We show computational results on a set of 73 benchmark graphs from the DIMACS and COLOR competitions to assess the interest of the proposed approach. ese results include especially 9 improved best solutions (new upper bounds) which can be used to assess other algorithms for the ECP in the future.

e remainder of the paper is organized as follows. Section 2 introduces some preliminary definitions. Section 3 is dedicated to the description of the proposed algorithm. Section 4 presents computational results and comparisons with state-of-the-art algorithms. Section 5 analyzes the impact of some key components of the proposed algorithm. Conclusions and future work are discussed in the last section.

BASIC DEFINITIONS

We introduce the following basic definitions which are useful for the description of the proposed approach, where G = (V , E) is a given graph.

Definition 2.1. A candidate coloring of G is any partition of the vertex set V into k subsets V 1 , V 2 , . . . , V k , where each V i is called a color class.
Definition 2.2. A legal coloring is a conflict-free coloring composed of independent sets, i.e., any pair of vertices of any color class are not linked by an edge in E. Otherwise, it is an illegal or conflicting coloring. Definition 2.3. An equitable coloring or equity-feasible solution is any candidate coloring satisfying the equity constraint, i.e., the cardinalities of any two color classes differ by at most one. Otherwise, it is an equity-infeasible solution.

GENERAL APPROACH

e equitable coloring problem (ECP) involves finding the smallest number of colors k such that an equitable legal k-coloring exists for a given graph G. Like for the conventional GCP [START_REF] Galinier | Recent advances in graph vertex coloring[END_REF], the ECP can be approximated by finding a series of equitable legal k-colorings for decreasing k values. To seek an equitable legal k-coloring for a given k, one typically explores the space of equity-feasible colorings while minimizing a fitness function f which counts the number of conflicting edges [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF][START_REF] Méndez Díaz | A tabu search heuristic for the equitable coloring problem[END_REF]. e ECP problem with a given k is called the k-ECP problem.

is study follows this general approach of solving a series of k-ECP problems. However for each fixed k, our algorithm explores candidate solutions which include both equity-feasible and equityinfeasible colorings. For this, our feasible and infeasible search algorithm (FISA) introduces an extended fitness function F which is employed to measure the quality of any candidate solution.

e proposed FISA algorithm is composed of two search phases (see Sections 3.1 and 3.2). e first phase examines only the space of equity-feasible colorings to seek a legal (i.e., conflict-free) kcoloring. If a legal k-coloring is found, the k-ECP problem is solved with the current k value and we continue with the new k-ECP problem by se ing k = k -1. To be effective, the first phase is based on the basic tabu search procedure of the BITS algorithm [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF]. If the first phase fails to find a legal k-coloring with the equityfeasible space, the second phase is invoked to enlarge the search to include equity-infeasible colorings. To explore the enlarged search space, this second phase relies on the extended fitness function F to guide the search process. e infeasible search phase terminates if an equitable coloring is found or if the best solution found so far cannot be improved during 10000 consecutive iterations. e pseudo-code of the FISA algorithm is given in Algorithm 1. e algorithm starts with an initial equity-feasible solution which is generated with a simple greedy heuristic presented in [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF]. In the next sections, we explain the search strategies of both phases of the FISA algorithm.

Algorithm 1 Main Scheme of the FISA algorithm for the ECP s 1 ← per tur bat ion (s 2 ) 14: end while 3.1 Searching equity-feasible solutions [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF] e first phase of the proposed FISA algorithm searches the space of candidate solutions which verifies the equity constraint and tries to find a legal k-coloring. is is achieved by minimization of the number of conflicting edges of candidate equitable k-colorings, an edge is conflicting if its endpoints belong to the same color class.

3.1.1 Equity-feasible space and fitness function. We define the equity-feasible space Ω k to be the set of all candidate colorings verifying the equity constraint. Formally, Ω k is given by

Ω k = {{V 1 , V 2 , • • • , V k } : ||V i | -|V j || ≤ 1, ∪ k i=1 V i = V , V i ∩ V j = ∅} (1)
where i j, 1 ≤ i, j ≤ k.

To assess the quality of a candidate solution s in Ω k , the evaluation or fitness function counts the number of conflicting edges in the color classes of s. Specifically, let s = {V 1 , V 2 , . . . , V k } ∈ Ω k be a candidate solution, let C (V i ) denote the set of conflicting edges with both endpoints in V i . e fitness function f (which is to be minimized) is given by

f (s) = k i=1 |C (V i )| (2)
erefore, a solution s with f (s) = 0 is an equitable legal kcoloring satisfying both the equity and coloring constraints. When such a solution is found, the associated k-ECP problem is solved.

e feasible search phase of the FISA algorithm uses this fitness function to guide its search process to visit solutions of Ω k in order to obtain a solution s with f (s) = 0.

3.1.2 Move operators to explore space Ω k . To explore the space Ω k , the feasible search phase applies two move operators to generate neighboring solutions from the current solution. Let s = {V 1 , V 2 , . . . , V k } be the current solution. Let C (s) denote the set of conflicting vertices involved in the conflicting edges of s.

(1) One-move operator: It transfers a conflicting vertex from its current color class V i to a different color class V j ensuring that the equity constraint is always respected, i.e.,

|V i | > ⌊ n k ⌋, |V j | < ⌈ n k ⌉. Let < , V i , V j >
denote such a move. We use s⊕ < , V i , V j > to denote the neighboring solution generated by applying the move to s. en the neighborhood N 1 induced by this move operator contains all possible solutions obtained by applying "one-move" to s, i.e.,

N 1 (s) = {s ⊕ < , V i , V j > : ∈ V i ∩ C (s)} (3)
where

1 ≤ i, j, ≤ k, i j, |V i | > ⌊ n k ⌋, |V j | < ⌈ n k ⌉. Note that the one-move operator is not applicable if ⌊ n k ⌋ = ⌈ n k ⌉.
In this case, the neighborhood N 1 is empty.

(2) Swap operator: It exchanges a conflicting vertex of color class V i with another vertex u of color class V j (i j). Let swap( , u) denote such a move. e neighborhood N 2 induced by the swap operator is composed of all possible solutions obtained by applying "swap" to s (recall that C (s) is the set of conflicting vertices of s).

N 2 (s) = {s ⊕ swap( , u) : ∈ V i , u ∈ V j , i j, { , u} ∩ C (s) ∅} (4)
Since this operator does not change the cardinality of any color class, a neighboring solution generated by this operator is always equity-feasible (given that the current solution is an equitable k-coloring).

Exploration of the space Ω k .

Starting from an equitable (conflicting) k-coloring of Ω k , the first phase of FISA iteratively improves the solution according to the tabu search method [START_REF] Glover | Tabu Search[END_REF]. Specifically, the basic tabu search procedure (TS 0 ) described in [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF] is applied to find a conflict-free k-coloring. At each iteration, a best admissible candidate solution is taken among the neighboring solutions of N 1 and N 2 to replace the current solution. e underlying move (< , V i , V j > for one-move or swap( , u)) is recorded in the so-called tabu list in order to forbid the reverse move for a fixed number of next iterations. is tabu search process continues until either a solution s with f (s) = 0 is found in which case, the current k-ECP problem is solved, or the current solution is not improved during a fixed number of consecutive iterations in which case the FISA algorithm moves to the second search phase.

Searching equity-infeasible solutions

When the first phase fails to identify an equitable legal k-coloring within the equity-feasible space Ω k , the FISA algorithm invokes the second phase to explore an enlarged space Ω + k including both equity-feasible and equity-infeasible solutions.

Equity-infeasible space and extended fitness function. e enlarged search space Ω +

k explored by the second phase contains all possible partitions of the vertex set V into k disjoint subsets as follows.

Ω + k = {{V 1 , V 2 : • • • , V k }, ∪ k i=1 V i = V , V i ∩ V j = ∅} (5)
where i j, 1 ≤ i, j ≤ k. We note that this enlarged search subsumes the equity-feasible space Ω k and additionally includes the equity-infeasible solutions.

To evaluate the quality of the solutions of Ω + k , we devise an extended penalty-based fitness function F . For this purpose, we first introduce some notations.

Let W + = ⌈n/k⌉ and W -= ⌊n/k⌋, which represent respectively the theoretical cardinality of the largest and smallest color classes in an equitable k-coloring. en for an equitable k-coloring s

= {V 1 , V 2 , • • • , V k }, W -≤ |V i | ≤ W + (i = 1, • • • , k ) holds. Let s = {V 1 , V 2 , • • • , V k } be a candidate solution in Ω + k , we define the penalty ρ i (i = 1, • • • , k ) for each color class V i of
the solution s to be the gap between |V i | and the theoretical cardinalities as follows.

ρ i = |V i | -W + , i f |V i | ≥ W + W --|V i |, i f |V i | ≤ W - (6)
en we define our extended fitness function F (to be minimized) as a linear combination of the basic fitness function f (Equation ( 2)) and a penalty function as follows.

F (s) = k i=1 |C (V i )| + φ k i=1 ρ i (7)
where C (V i ) is the set of conflicting edges in color class V i and φ (a parameter with φ ≥ 1) is the penalty coefficient which is used to control the importance given to the penalty function (see Section 5.1 for an analysis of φ). According to this definition, a candidate solution violating strongly (weakly) the equity constraint will be penalized more harshly (slightly). Since in general the number of conflicting edges (the first term) of F decreases quickly when the search progresses, the penalty term has the desirable property of helping the search process to avoid infeasible solutions which are too far from the feasibility boundaries. Note that the penalty term of an equitable coloring equals 0. erefore, a partition s ∈ Ω + k with F (s) = 0 corresponds to a equitable and legal k-coloring, i.e., satisfying both the equity and coloring constraints and is thus a solution to the k-ECP problem.

Move operators to explore the space Ω +

k . To explore the search space Ω + k , the infeasible search phase also applies two move operators to generate neighboring solutions. Let s = {V 1 , V 2 , . . . , V k } be the current solution. Let C (s) denote the set of conflicting vertices of s, i.e., the vertices involved in a conflicting edge.

(1) One-move operator: Like for the first search phase, this operator displaces a conflicting vertex from its current color class V i to another color class V j . However, the equity constraint is no more considered. is leads to the following enlarged neighborhood.

N + 1 (s) = {s ⊕ < , V i , V j > : ∈ V i ∩ C (s), 1 ≤ i, j ≤ k, i j} (8) Clearly N + 1 is bounded by O (|C (s)| × k ) in size.
To effectively calculate the move gain which identifies the change in the fitness function F (Equation ( 7), we adapt the fast incremental evaluation technique of [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF]. e main idea is to maintain a matrix A of size n × k with elements A[ ][q] recording the number of vertices adjacent to in color class V q (1 ≤ q ≤ k ). Another n × k matrix B is maintained with elements B[ ][q] representing the penalty value of vertex assigned to color class q in the current solution. en, the move gain of each one-move in terms of extended fitness variation can be conveniently computed by

∆F = A[ ][j] -A[ ][i] + φ(B[ ][j] -B[ ][i]) ( 9
)
where φ is the penalty coefficient used in the extended fitness function F . Each time a one-move operation involving vertex is performed, we just need to update a subset of values affected by this move as follows. For each vertex u adjacent to vertex ,

A[u][i] ← A[u][i]-1, and A[u][j] ← A[u][j]+1. For any vertex w, B[w][j] ← k i=1 ρ i , 1 ≤ j ≤ k. B[w][j] = B[u][j],
if w and u belong to the same color class.

(2) Swap operator: e same swap operator as for the first phase is applied to exchange a pair of vertices (u, ) from different color classes where at least one of them is a conflicting vertex. However, there is an important difference.

Since the second search phase operates in the enlarged space Ω + k instead of Ω k , the equity-feasibility of a neighboring solution fully depends on the current solution. at is, if the current solution is equity-infeasible (equity-feasible), application of swap leads to an equity-infeasible (equityfeasible) solution. e resulting swap-based neighborhood is thus given as follows.

N + 2 (s) = {s ⊕ swap( , u) : ∈ V i , u ∈ V j , i j, { , u} ∩ C (s) ∅} (10)
where C (s) is the set of conflicting vertices of s. Notice that the swap operation has no impact on the penalty value of the neighboring solution and can only change the number of conflicting edges. en the fitness gain of a swap operation can be computed by

DeltaF = A[u][i] -A[u][j] + A[ ][j] -A[ ][i] -2e ,u (11)
where e ,u = 1 if and u are adjacent vertices, otherwise e ,u = 0.

Exploration of the enlarged space Ω +

k . To explore the enlarged space Ω + k , we apply again the tabu search method. Specifically, each iteration of tabu search selects the best admissible solutions among the neighboring solution of N + 1 and N + 2 . e procedure makes transitions between various k-coloring while minimizing the extended fitness function F with the purpose of a aining a solution s with F (s) = 0.

3.2.4

Perturbation of infeasible search. e tabu list used by the equity-infeasible exploration phase helps the search process to go beyond some local optima. Yet, this mechanism may not be sufficient to escape deep traps. To overcome this problem, we apply a perturbation procedure inspired by the procedure of [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF].

is operator follows the perturbation scheme of breakout local search [START_REF] Benlic | Breakout local search for maximum clique problems[END_REF] and combines directed and random applications of the one-move and swap operators. To avoid a too strong deterioration of the perturbed solution, a directed perturbation move takes into consideration the fitness variation and performs the most favorable move (i.e., deteriorating the solution the least). In contrary, a random perturbation performs a one-move or swap operation without considering the fitness deterioration. To combine these two types of perturbations, the number of performed moves dynamically varies in an adaptive way while the application of each type of perturbation is determined probabilistically. e resulting solution from the perturbation procedure is then used as the new starting solution of the next round of the infeasible search phase.

EXPERIMENTAL RESULTS AND COMPARISONS

In this section, we assess the performance of the proposed FISA algorithm on the set of 73 benchmark instances which are commonly used in the literature and were initially proposed for the DIMCAS and COLOR competitions for graph coloring problems1,2 .

Experiment settings

e proposed algorithm was coded in C++ and compiled by GNU g++ 4.1.2 with -O3 flag (option). e experiments were conducted on a computer with an Intel Xeon E5-2670 processor (2.5 GHz and 2 GB RAM) running Ubuntu 12.04. When solving the DIMACS Table 1: Comparative results of FISA with state-of-the-art algorithms on the 73 benchmark instances.

TabuEqCol [START_REF] Méndez Díaz | A tabu search heuristic for the equitable coloring problem[END_REF] BITS [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF] FISA Instance

|V |

LB [START_REF] Méndez-Díaz | A polyhedral approach for the equitable coloring problem[END_REF][START_REF] Méndez-Díaz | A DSATUR-based algorithm for the Equitable Coloring Problem[END_REF] UB [START_REF] Méndez-Díaz | A polyhedral approach for the equitable coloring problem[END_REF][START_REF] Méndez-Díaz | A DSATUR-based algorithm for the Equitable Coloring Problem[END_REF] k machine benchmark procedure 'dfmax.c' 3 without compiler optimization flag, the run time on our computer is 0.46, 2.68 and 10.70 seconds for graphs r300.5, r400.5 and r500.5, respectively.

For our comparative study, we use the most recent heuristic algorithms [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF][START_REF] Méndez Díaz | A tabu search heuristic for the equitable coloring problem[END_REF] as our references. e TabuEqCol algorithm (2014) [START_REF] Méndez Díaz | A tabu search heuristic for the equitable coloring problem[END_REF] was run on an Intel i5 CPU with 750 2.67 GHz and tested under a time limit of 1 hour. e BITS algorithm (2015) [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF] was run on an Intel Xeon E5440 CPU with 2.83 GHz and 2 GB RAM and tested under a time limit of 1 hour and a relaxed limit (10 4 seconds for the instances with up to 500 vertices and 2 × 10 4 seconds for larger instances with more than 500 vertices). As shown in [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF], the computational results of the more recent BITS algorithm dominate those of TabuEqCol. We also include the lower and upper bounds reported in [START_REF] Méndez-Díaz | A polyhedral approach for the equitable coloring problem[END_REF][START_REF] Méndez-Díaz | A DSATUR-based algorithm for the Equitable Coloring Problem[END_REF] which were obtained by exact methods under various test conditions. ese bounds provide useful information when they are contrasted with the results (upper bounds) obtained by the compared heuristic algorithms (TabuEqCol, BITS and FISA).

e FISA algorithm requires the tuning of some parameters related to tabu search and the extended fitness function F . Since our tabu search procedures are adaptations of the basic tabu search procedure of [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF], we adopted the parameter se ings used in the original paper. As to the penalty coefficient φ of the extended fitness function F , we provide an analysis in Section 5.

Following [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF][START_REF] Méndez Díaz | A tabu search heuristic for the equitable coloring problem[END_REF], we present a first experiment where we ran our FISA algorithm only once per instance with a cutoff time of 3,600 seconds (1 hour). Like [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF], we carried out a second experiment where we ran FISA 20 times to solve each instance under the extended stopping condition -10 4 seconds for the instances with up to 500 vertices and 2 × 10 4 seconds for larger instances with more than 500 vertices. We note that our Intel Xeon E5-2670 2.5 GHz processor is slightly slower than those used by the reference algorithms. As a result, our adopted stopping conditions can be considered as reasonable with respect to those used by the reference algorithms. Finally, as shown in [START_REF] Lai | Backtracking based iterated tabu search for equitable coloring[END_REF], the main reference BITS algorithm fully dominates the TabuEqCol algorithm. So the results of BITS have the most significant reference value.

Comparison with state-of-the-art algorithms

From Table 1, we can see that FISA shows a remarkable performance compared to the TabuEqCol and BITS algorithms under both stopping conditions. Under the 1 hour condition, FISA dominates TabuEqCol (Columns 5 and 8) on the 50 instances tested by both algorithms, by obtaining be er results for 30 instances and the same results for the remaining 20 instances. Compared to the most recent BITS algorithm, FISA obtains be er solutions for 14 instances (see negative entries in Column ∆(k 1 )), the same best results for other 58 instances and one worse result. When comparing FISA with BITS under the long time condition (the results of TabuEqCol under this condition are unavailable), one observes that FISA also performs very well (Columns 7 and 9). Specifically, FISA improves the best results of BITS for 9 instances (see negative entries in Column ∆(k best ) while matching the best results of BITS for other 63 instances. Only in one case, FISA obtains a slightly worse result. 3 dfmax: p://dimacs.rutgers.edu/pub/dsj/clique/ Finally, when comparing to the upper bounds obtained by exact algorithms (Column 4), it is clear that the bounds of FISA (Column 9) are much be er. If we contrast the current best lower bounds (Column 3) obtained by exact approaches of [START_REF] Méndez-Díaz | A polyhedral approach for the equitable coloring problem[END_REF][START_REF] Méndez-Díaz | A DSATUR-based algorithm for the Equitable Coloring Problem[END_REF] and the best upper bounds from FISA (Column 9), we observe important gaps for a number of instances. is indicates that both the current best lower and upper bounds can be further improved.

ANALYSIS

is section performs additional experiments to analyze the proposed FISA algorithm: the penalty coefficient φ and the perturbation strategy. ese experiments were performed on a selection of 26 instances which are relatively difficult according to the results reported in Table 1, i.e., the best-known results of these instances cannot be a ained by all algorithms. is section investigates the influence of the penalty coefficient φ on the performance of the proposed algorithm (Section 3.2, Equation 7). For this purpose, we tested FISA with 3 different values of φ = 1, 2, 3. We ran 20 times the algorithm with each φ value to solve each selected instance with a cutoff time of 1 hour.

Analysis of the penalty coefficient φ

e experimental results are presented in Table 2. e first column shows the names of instances, and the second column indicates the best results (k * 1 ) obtained in this experiment. e results of FISA with different φ values are respectively listed in columns 3 to 5 including the best values with the averaged values between parentheses. e rows #Equal and #Worse respectively indicate the number of instances for which each φ values a ains an equal and worse result compared to k * 1 . We note that the best results were obtained with φ = 1. is justifies the se ing of this parameter used in our previous experiments.

Impact of the perturbation operation

As shown in Section 3.2.4, the proposed algorithm uses a perturbation strategy to ensure a global diversification within the enlarged search space Ω + k . In order to assess this strategy, we compare it with a traditional restart strategy (denoted as REST), where each restart begins its search with a new equitable k-coloring generated by the greedy procedure mentioned in Section 3. e two algorithms were run 20 times on the 26 selected instances with a time limit of 1 hour per run. e results of this experiment are shown in Table 3. Column 1 lists the names of instances. Column 2 indicates the best results (k * best ) obtained in this experiment. e best results (k best ) and the average results (k a ) of FISA and REST are respectively listed in columns 3 to 6. e rows #Equal and #Worse respectively indicate the number of instances for which FISA and REST a ain an equal and worse result compared to k * best . It is clear that FISA dominates the REST variant by obtaining 12 be er results out of the 26 tested instances and no worse result. is experiment confirms thus the interest of the adopted perturbation strategy.

CONCLUSIONS

e equitable coloring problem (ECP) is an NP-hard problem with a number of practical applications. In addition to the conventional coloring constraint (i.e., adjacent vertices must receive different colors), a solution of the ECP must satisfy the equity constraint (the cardinalities of the color classes must differ by at most one). In this work, we investigated the benefit of examining both feasible and infeasible solutions with respect to the equity constraint. e resulting algorithm (called FISA) combines an equity-feasible search phase where only equitable colorings are considered and an equityinfeasible search phase where the search is enlarged to include nonequitable solutions. To guide the search procedure (which is based on tabu search), we devised an extended fitness function which uses a penalty to discourage candidate solutions which violates the equity constraint. A perturbation procedure was also used as a means of diversification to help the algorithm to explore new search regions.

We assessed the performance of the FISA algorithm on the set of 73 benchmark instances from DIMACS and COLOR competitions and presented comparative results with respect to state-of-the-art algorithms.

e comparisons showed that FISA performs very well by discovering 9 improved best results (new upper bounds) and matching the best-known results for the remaining instances except one case. e new bounds can be used for assessment of other ECP algorithms. is study demonstrates the benefit of the mixed search strategy examining both equity-feasible and equityinfeasible solutions for solving the ECP.

For future work, several directions could be followed. First, the penalty term of the extended fitness function could be improved by introducing adaptive techniques like [START_REF] Chen | A hybrid metaheuristic approach for the capacitated arc routing problem[END_REF][START_REF] Glover | e case for strategic oscillation[END_REF] to enable a strategic oscillation for dynamically transitioning between feasible and infeasible space. Second, other search operators (rather than those used in this work) can be sought to further improve the performance of the search algorithm. ird, the proposed algorithm could be advantageously integrated into a hybrid population-based method (e.g., memetic search, path-linking) as a key intensification component. Finally, the instances tested in this work are based on the conventional DIMACS coloring benchmark graphs. ese graphs can be considered as being limited in size with respect to massive graphs obtained from a number of modern applications like complex networks and biological networks. Contrary to DIMACS graphs, these massive graphs are typically very sparse with very low edge density. It would be interesting to investigate the ideas of this work in the context of coloring massive graphs.

s 1 ) and st op 7: end if 8: while stopping condition is not met do 9: s 2 ← inf easibl e sear ch (s 1 ) / * Section 3.2 * / 10: if F (s 2 ) = 0 then

	1: Input: Graph G; k colors
	2: Output: An equitable legal k -coloring if found
	3: s 0 ← r eed init ial (G, k ) / * Generate an initial equity-feasible
		k-coloring * /
	4: s 1 ← f easibl e sear ch (s 0 ) / * Section 3.1 * /
	5: if f (s 1 ) = 0 then
	6: r etur n (11: r etur n(s 2 ) and st op
	12:	end if
	13:

Table 2 :

 2 Comparative results of the FISA algorithm with 3 different values of φ on the 26 instances. e best results are in bold.

	Instance	k * 1	k 1, φ=1 (A )	k 1, φ=2 (A )	k 1, φ=3 (A )
	DSJC125.5.col	17	17(17)	17(17)	17(17)
	DSJC250.1.col	8	8(8)	8(8)	8(8)
	DSJC250.5.col	29	29(29.8)	29(29.65)	29(29.75)
	DSJC250.9.col	72	72(72.1)	72(72.05)	72(72.05)
	DSJC500.5.col	53	53(53.35)	53(53.95)	53(54)
	DSJC500.9.col	130	131(131.6)	131(131.4)	130(130.75)
	DSJR500.5.col	126	126(126.85)	126(126.65)	126(126.9)
	DSJC1000.1.col	21	21(21)	21(21.15)	21(21.15)
	DSJC1000.5.col	98	98(99.45)	100(101.6)	101(104.75)
	DSJC1000.9.col	253	253(254.35)	254(254.6)	254(254)
	R250.5.col	66	67(67)	66(66.9)	67(67)
	R1000.5.col	250	251(253.9)	251(255.05)	250(252.85)
	flat300 28 0.col	32	33(33.85)	32(33.95)	32(33.85)
	flat1000 50 0.col	96	96(97.4)	98(99.9)	99(102.25)
	flat1000 60 0.col	97	97(97.9)	98(100.35)	99(102.2)
	flat1000 76 0.col	98	98(98.65)	99(100.7)	101(102.95)
	latin square 10.col	105	105(106.1)	114(115.15)	115(116.6)
	C2000.5.col	198	198(199.55)	200(201.25)	199(200.85)
	mulsol.i.2.col	36	36(36.95)	36(36.95)	36(36.95)
	fpsol2.i.1.col	65	65(65)	65(65.05)	65(65)
	fpsol2.i.2.col	47	47(47.2)	47(47.25)	47(47.3)
	inithx.i.2.col	36	36(38.8)	37(38.65)	36(39.95)
	inithx.i.3.col	37	38(39.85)	37(40.1)	37(39.55)
	zeroin.i.1.col	49	49(49.75)	49(49.4)	49(49.6)
	zeroin.i.2.col	36	36(36)	36(36)	36(36)
	zeroin.i.3.col	36	36(36)	36(36)	36(36)
	#Equal		21	16	18
	#Worse		5	10	8

Table 3 :

 3 Analysis of the influence of the perturbation on the performance of the FISA algorithm.

			FISA		REST
	Instance	k * best	k best k a	k best k a
	DSJC125.5.col	17	17	17	17	17
	DSJC250.1.col	8	8	8	8	8
	DSJC250.5.col	29	29	29.8	29	29.95
	DSJC250.9.col	72	72	72.1	72	72.1
	DSJC500.5.col	53	53	53.35	54	55.15
	DSJC500.9.col	131	131	131.6	131	131.7
	DSJR500.5.col	126	126	126.85	126	127.05
	DSJC1000.1.col	21	21	21	21	21
	DSJC1000.5.col	98	98	99.45	102	102.15
	DSJC1000.9.col	253	253	254.35	253	254.3
	R250.5.col	67	67	67	67	67.05
	R1000.5.col	251	251	253.9	252	255.35
	flat1000 50 0.col	96	96	97.4	101	101.5
	flat1000 60 0.col	97	97	97.9	101	101.75
	flat1000 76 0.col	98	98	98.65	101	101.95
	flat300 28 0.col	33	33	33.85	33	34.3
	latin square 10.col 105	105	106.1	105	106.5
	C2000.5.col	198	198	199.55	201	201
	mulsol.i.2.col	36	36	36.95	37	37.75
	fpsol2.i.1.col	65	65	65	77	79.4
	fpsol2.i.2.col	47	47	47.25	56	73.05
	inithx.i.2.col	36	36	38.8	60	63.85
	inithx.i.3.col	38	38	39.05	57	64.85
	zeroin.i.1.col	49	49	49.75	55	55.9
	zeroin.i.2.col	36	36	36	39	42
	zeroin.i.3.col	36	36	36	38	43.05
	#Equal		26		14
	#Worse		0		12

h p://www.dimacs.rutgers.edu/

h p://www.cs.hbg.psu.edu/txn131/graphcoloring.html/

ACKNOWLEDGMENTS

e authors would like to thank the anonymous referees for their valuable comments and helpful suggestions. Support for the first author from the China Scholarship Council (2015-2019) is also acknowledged.