Réhan Noordally
email: rehan.noordally@univ-reunion.fr

Yassine Gangat
email: yassine.gangat@univ-reunion.fr

Arnaud Ravoavahy
email: arnaud.ravoavahy@gmail.com

Pascal Anelli
email: pascal.anelli@univ-reunion.fr

Xavier Nicolay
email: xavier.nicolay@univ-reunion.fr

How long delays impact TCP performance for a connectivity from Reunion Island ?

Keywords: Passive metrology, TCP, Internet Delay

TCP is the protocol of transport the most used in the Internet and have a heavy-dependence on delay. Reunion Island have a specific Internet connection, based on main links to France, located 10.000 km away. As a result, the minimal delay between Reunion Island and France is around 180 ms. In this paper, we will study TCP traces collected in Reunion Island University. The goal is to determine the metrics to study the impacts of long delays on TCP performance.

I. INTRODUCTION

Internet has evolved to become a large network where services will differ according to the user's need. Internet can be used, as it first purpose was, to send mail or use the World Wide Web (WWW). Now, on-line gaming, audio or videao discussion are currently used on the Internet. But all these new services require low delay for interactivity. Due to the difficulty of using news transport protocols, these news services continue to use Transmission Control Protocol (TCP). This transport protocol is very sensitive to the variation of the delay. There are some geographic areas where the delay is higher than usual. In [START_REF] Noordally | Analysis of internet latency : the reunion island case[END_REF], the authors have shown that Reunion Island has a specific behavior in terms of routing and delay. In this paper, we would investigate the impact of these characteristics on the performance of TCP.

After a selection of specific metrics, we have collected data by passive metrology during one month using a listener. The analysis work on the traffic distribution and on the type of services over TCP.

The remainder of this paper is organized as follows. The section II explains the specific context of physical connectivity of Reunion Island. A description of the suitable metrics to analyze TCP traffic have been determined in the section III, whereas the section IV presents the tools used to capture and to analyze TCP traces. The section V presents the methodology to collect traffic. Collected traffic is analyzed in section VI. We complete the paper with the overview of related work in section VII and our conclusions in section VIII.

II. CONTEXT

Reunion Island is a French overseas department located far away from France: in the Indian Ocean, between Madagascar and Mauritius. From the map (see figure 1) issued by http://www.submarinecablemap.com, we can see that Reunion Island is connected to the Internet by two submarine cables. The first one is the South Africa Far East (SAFE) spans from 2b shown the updated results. The red curve shows a shorter delay than before, while the minimal delay from Reunion Island has increased. The delay from Reunion Island was smooth through time between the two experiments. This is one reason why we will study the impact of this specific connectivity on the transport protocol performance.

III. METRICS

In this section, we would describe each metric we have chosen to analyze TCP traffic. We have split the metrics in two categories: supervision and performance.

A. Traffic Supervision

In this class of metrics, we would only have a view of the traffic exchange, as an ISP could have.

The first concern is the volume exchanged with IPv4 protocol. In this volume, we would make a distinction in terms of destination. We divide the collected traffic in 3 categories:

1) The first one is traffic in Local Area Network (LAN) and concerned only traffic inside the intranet of collected points.

2) The second one can be associated to traffic in Metropolitan Area Network (MAN). With the presence of an Internet eXchange Point (IXP), we will, in this case, consider traffic intra-Reunion Island.

3) The last case is Wide Area Network (WAN) traffic and identified traffic going outside of the Island. The analyze of destinations included in the WAN part would give us some indications about the location of the information needed by the user. Our second metric we have focused on is the traffic's volume of different protocols of transport, like TCP and UDP. This would inform us of the most used protocol and if the services use the right protocol.

Lastly, the number of the destination ports will give us an overview of services that have been used.

B. Protocol performance

The TCP is the principal protocol of transport used around the world with heavy-dependence on delay. Studying its performance is equivalent to study Internet performance. In [START_REF] Jain | The art of computer systems performance analysis[END_REF], the author has explained the functioning of a system based on requests. The figure 3 has been taken from his book. We used it for choosing which TCP metrics should be used. The Fig. 3: Functioning of a request system first and the second metrics are the RTT and the throughput. Some event could be easily identified, like packets losses and retransmits. We define a flow as a bi-directional series of IP packet with the same source and destination address, port number and protocol number.

C. Summary

The table I resume all the metrics choose for the experiment.

IV. TOOLS INVOLVED

A. TCPDump

TCPDump [START_REF] Jacobson | The tcpdump manual page[END_REF] is a tool developed in 1989 by Jacobson, using the PCAP library [START_REF]pcap-packet capture library[END_REF] to capture and analyze the Internet flows. This tool is the first tool created for this kind of metrology and allows the writing and reading of files in pcap format.

B. Anonymization

In agreement with the French law [START_REF]Loi numéro 78-17 du 6 janvier 1978 relative à l'informatique, aux fichiers et aux libertés[END_REF], we need to anonymize the data obtained before the analysis. The article [START_REF] Minshall | Tcpdpriv: Program for eliminating confidential information from traces[END_REF] explain that an Internet packet contains private information and need to be removed before analysis. The author describes a tool to anonymize confidential information. But in [START_REF] Xu | Prefix-preserving IP address anonymization: Measurement-based security evaluation and a new cryptography-based scheme[END_REF], Xu explains some lack in TCPdriv and proposes a new solution called Crypto-pan. Crypto-pan is the most anonymized algorithm used actually. This program used the prefix-preserving system, which means that if two IP address have k-bits in common, their anonymized address keep k-bits in common.

C. Analysis

As said in IV-A, PCAP is a library with several tools for traces One of the most well-know tool is Wireshark [START_REF] Chappell | Wireshark network analysis: the official Wireshark certified network analyst study guide[END_REF]. Wireshark can be used with a graphic-interface. But this tool is not adapted to our need, i.e. it doesn't take into account the geolocation of an IP address or it can't anonymize the raw data. To fill this gap, we have developed our own tool to obtain information about all metrics stated in section III. This tool, developed in C, includes Crypto-pan concept and focuses only on the metrics we have selected.

V. METHODOLOGY

The first study on Reunion Island connectivity was realized with the help of the Internet Service Provider (ISP) was made in 2013 by [START_REF] Vergoz | Classement des opérateurs Internet réunionnais[END_REF]. In this paper, the authors have used active metrology to analyze the characteristics of the Reunion Island's Internet. To identify the performance of TCP, a better way is the listening of traffic and to analyze what happens in real-time or later. ISP information about their performances are very sensitive data, and this is the reason why they don't want to share it. To respect their publishing data politics, we have made our own measurement infrastructure. Deployed in the Computer Sciences and Mathematics Laboratory (LIM) of Reunion Island University, we have collected data traffic from students and researchers. The collected data have been realized between one and 23 hours per day with port-mirroring protocol [START_REF] Foschiano | Cisco systems' encapsulated remote switch port analyzer (erspan)[END_REF]. The start and the duration of each measurement have been randomized. Two measurements have a maximal distance of 24 hours. We are fully aware that our collection is not representative of Reunion Island's traffic, but still a good set of tests for our analyze tools.

VI. RESULTS

The results illustrated the output obtained by our analysis tool. It can be divided in two main parts. In subsection VI-A, we have the results of the supervision of the data collected. The subsection VI-B concerns the analysis of the characteristics of the flows and the performance of TCP.

A. Traffic characteristics

The LIM laboratory and in fact all laboratories and faculties of our University are connected to the Internet through a fiber access with a bandwidth of 500 Mbits/s with RENATER as ISP. RENATER is the French network reserved for Universities and research centers. During one month, we have collected 72 Gigabytes of data. These data concerned only IPv4 because IPv6 is not available in Reunion Island University. As we stated before, we have three kinds of networks that have been analyzed: LAN (local network), MAN (network flow in Reunion Island) and WAN (network flows outside Reunion Island). With the analyze of the IP address, we have spread the traffic into these three categories. The table II shown the results obtained. The WAN part is the main traffic identified regroup all port number without any matching in the file 'service' located on the analysis server. Other identify protocols with a percentage lower than 1%. The presence of SSH is explained by its frequently use to push data on the webserver of the laboratory or to connect to distant servers. The Mail item regroup five protocols consecrate to send or receive email, like Post Office Protocol (POP), SMTP or Internet Message Access Protocol (IMAP) and their secured version, POP3s, IMAPs. But these protocols are only present when you use an email application like Thunderbird or Outlook. The connection to Gmail with an web browser wrap the traffic into HTTPS. In one hand, we have the strong presence of TCP, and in the second one we have the sensation of slowness described by the users. It's therefore perfectly supposed to focus our analysis on the performance of the majority protocol: TCP.

B. TCP Performance

We have analyzed the different types of flows present in the data analysis. The figure 4a represent the Cumulative Density Function (CDF) for the flow length L in packets. We can notice that more than 90% of our flows are composed of fewer than 100 packets. These flows represent 94.45% of the volume exchange in bytes. That supposed that the packet exchanged are heavy in terms of data. In the Internet, 80% of the traffic are made by only 20% of the flow. In our case, the Pareto distribution for the Internet is not respected. The figure 4b represent the PDF for the flow duration in seconds. The bin used for the PDF is 3s. We can see that the first peak represents the Recovery Time Objective (RTO) of TCP. These flows represent only 3.5% of the volume exchange. Exceed the RTO, the probability of the duration decrease. We can notice that on the figure, every 60s, a peak are present. The flows exceeding 300s (5 min) represent 59% of the volume exchange. That means more the flows carry on, more the volume exchange increase.

With the figure 5, we can analyze the meaning throughput of each flow. We can notice that 60% of our traffic have a meaning throughput less or equal than 10 bits per seconds, but this majority represent only less than 10 -3 % of the volume exchange. That's mean the flows are very light in terms of bytes exchange. TCP is a protocol which can keep open some service by sending light packet, called Kepp-Alive. This traffic Fig. 5: Meaning Throughput Cumulative could be explained by the presence of this kind of packet.

TCP is a protocol relying on delay but Reunion Island have a specific behavior on this parameter [START_REF] Noordally | Analysis of internet latency : the reunion island case[END_REF]. A supposition we can do is that Reunion Island's traffic is very sensitive to Congestion Events. We have two ways to confirm it.

1) The first one is to identify the different flag of the flow and see if the Explicit Congestion Notification(ECN) [START_REF] Floyd | The Addition of Explicit Congestion Notification (ECN) to IP[END_REF] and the Congestion Window Reduce (CWR) flags are put to one. 2) The second way is to identify the reduction of TCP's windows and see what happens after.

With the first way of Congestion Event identification, none event was found. That means the different flag for the management of Congestion Event didn't rise up. The authors of [START_REF] Trammell | Enabling internet-wide deployment of explicit congestion notification[END_REF] shown that the number of servers which answered to ENC negotiation has increased. The missing of mark on the client side could be explained by two hypothesis. The first one is the obsolescence of the computer used in the Laboratory. But the machine used by our colleagues have been bought recently (current 2015 for someone). The second hypothesis is the remove of the flag by the equipment. In both hypotheses, the absence of the ECN flags are harmful for the TCP performance. In [START_REF] Mellia | TCP-aware packet marking in networks with diffserv support[END_REF], the authors have made some traffic simulation about TCP performance and packet marked.

The results shown that the performance of TCP will increase when the packets have been marked. Without these flags, the Congestion Event is more difficult to identify. The second way is more difficult to set up. We need to identify the windows reduced and see if we could identify some Lost Packet around this event. We have identified are like crumbs, with less than 1%. The percent of these errors are less than TCP could produce in normal condition.

VII. RELATED WORKS

A description of Cuba Internet's connectivity has been done in [START_REF] Bischof | In and out of Cuba: Characterizing Cuba's connectivity[END_REF]. The authors have shown that, despite a similar Internet access than Reunion Island, Cuba have an Internet latency near to the general case. This general case was presented in [START_REF] Krajsa | RTT measurement and its dependence on the real geographical distance[END_REF], where a relation between delay and geographical distance have been made. The authors of [START_REF] Noordally | Analysis of internet latency : the reunion island case[END_REF] have proved that Reunion Island is a specific case. In analyzing the Internet performance of the African continent, several studies have been made. In 2001, [START_REF] Johnson | Traffic characterization and internet usage in rural Africa[END_REF] have highlighted that the delay is very high and the HTTP response very low in rural area of Africa. In comparison with us, their flows are less longer, with 60% of their traffic have a duration lower than 2 seconds. The presence of flow durations higher than 10 minutes is a little fraction (0.47%) but are still present in the analyze. Another study has been done in a rural area of the African continent, more specifically in Zambia. The study has been done in 2005 by the author of [START_REF] Zheleva | Internet bandwidth upgrade: implications on performance and usage in rural zambia[END_REF] after an upgrade of the bandwidth. However, the meaning delay to reach services stayed higher than elsewhere.

A recent research about the presence of services in Africa has been explained in [START_REF] Fanou | Pushing the frontier: Exploring the african web ecosystem[END_REF]. The author has explained that despite the presence of servers in the continent, most of the traffic continues to go to America. It is a very similar situation as in Reunion Island with France servers.

VIII. CONCLUSION

Making a campaign of passive metrology is the second step for a better knowledge of the reasons why the Internet is degraded in some regions. Reunion Island has a specific connectivity to the Internet, with two submarine cables and a routing rules which made that the majority of the traffic going through France. Our study shows that up to 78% of the LIM traffic is to WAN and TCP is the most important transport protocol used in Reunion Island. Studying its performance is important to identify the default of the Reunion Island connectivity but the filter set up by the University impact our results. The analysis shows that the feeling of slowness didn't come from the performance of TCP but only due to the delay and the routing rules. In the future, we will contact the ISP working on Reunion Island and try to make an analysis of TCP performance of the Isl. In addition to the performance, we will supervise Reunion Island's Internet. We would also try to exchange information with the ISP present in the Indian Ocean countries, like Madagascar, Mauritius or Seychelles to make a comparison in the region.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Reunion Island Internet Connectivity (source : Submarine Cable Map) Asia (India and Malaysia) to South Africa. The SAFE is extended by the SAT3-WASC (South Africa Transit 3/West Africa Submarine Cable) cable which connected West Africa to Europe. The Lower Indian Ocean Network (LION) and LION2 cables connect, as its name indicates, the lower part of the Indian Ocean to a range of submarine cables in East Africa. This means that Reunion Island is connected to four landing points namely West Africa and Europe, East Africa and Asia. The author of [2] compared the Internet latency observed from Reunion Island and Paris. The figures 2a and 2b represents the Probability Density Function (PDF) of the Round-Trip Time (RTT). The RTT was evaluated with the ping command on a sample of IPv4 addresses distributed over the world. The first part colored in blue in 2 represents the density probability for delay from Reunion Island, while the red depicts the PDF from Paris. On the first figure, the two curves have the same trend with a

  Fig. 4: TCP Flow

TABLE I :

 I Metric summary

	Traffic Supervision	LAN MAN WAN Protocol Transport characterization Traffic Geographic Destination
		Services Used
		IPv4 volume exchanged
			Congestion
			Event
			Losses
		TCP	Retransmissions
	Protocol Performance	performance	Out of Order Windows Flags
			Connection Es-
			tablished Prob-
			lem
			Delay
			Throughput
		Flows characterization	Size Duration Rate

TABLE II :

 II Distribution of the LIM trafficThe first remarkable result is the presence of Internet Control Message Protocol (ICMP) packet. The presence of 5.72% of ICMP packets is due to a measurement delay campaign as it has been explained in[START_REF] Noordally | Analysis of internet latency : the reunion island case[END_REF]. The percentage

	each packet captured.
		Traffic	LAN	MAN	WAN
		Percent	21.65	0	78.35
	of the laboratory. That's mean the information needed by the
	user is mainly located outside of the University or Reunion
	Island.
	The table III represent the geographical distribution of the
	IP addresses only present in the WAN traffic and has been
	regrouped by continents. We can notice that two continents,
	TABLE III: Geographic distribution of our WAN destination
	(Source : RIPE NCC database)
	Continent	Africa	Asia	Europe	North America
	Percent	1.31	5.26	28.95	64.47
	Oceania and South America, are not present in our data. Most
	of the server joined by the users are mainly present in Europe
	and North America. These two continent hosted the principal
	servers for research publications.
	The table IV represent the distribution of the protocol of
	transport from the Computer Science Laboratory by analyzing

TABLE IV :

 IV Spread of the transport protocol TCP have the higher percentage between the different protocol. One reason can be that Reunion Island's University have set up some rules to limit the traffic generated by the users and closed some port. For example, Skype is prohibited as call-conference and the majority of TCP ports except the common like 22 for Secure-Shell (SSH) or 25 for Simple Mail Transfer Protocol (SMTP) are closed.The table V illustrate the analyze of TCP ports. The item Non

	Protocol	ICMP	IGMP	TCP	UDP
	Percent	5.72	0.01	92.49	1.78
	of UDP is low if we are taking into consideration the fact that
	Google Chrome is the most used browser in Reunion Island as
	presented on a website 1 . This web browser has an option call
	QUIC which increase the performance of the browser by using
	HyperText Transport Protocol (HTTP) over User Datagram
	Protocol (UDP) [12].
	Needless to say,

TABLE V :

 V Distribution of the service used by TCP

	Service	SSH DNS Mail Non	Other HTTPS HTTP
		indentified
	Percent	0.02 1.63 4.91 7.21	9.45	32.97	43.79

  152, 230 packets which indicate a window reduction. It's represented only 3 × 10 -3 percent of the packets exchange. But with only 232, 789 flows, a flow has 65% of chance to include a packet marked Windows reduce.TableVIrepresent the percent of packets retransmits or losses. We can see that the percent of packets retransmits or losses

TABLE VI :

 VI Packets spreading

	Packets	Fast Retransmit	Spurious	Lost	None
			Retransmit	Packet	retransmit
					or lost
	Percent	8.3 × 10 -3	9.7 × 10 -3	18 ×	99.96
				10 -3

ACKNOWLEDGMENTS

Réhan Noordally's PhD study is supported by Région Réunion and European Union (ERDF).


Aristide Grange

Imed Kacem

Sébastien Martin

Algorithms for the Bin Packing Problem with Overlapping Items

Keywords: Pagination, Bin packing, VM Packing, Integer linear programming, Heuristics, Genetic algorithms

We study an extension of the bin packing problem, where packing together two or more items may make them occupy less volume than the sum of their individual sizes. To achieve this property, an item is defined as a finite set of symbols from a given alphabet. Unlike the items of Bin Packing, two such sets can share zero, one or more symbols. The problem was first introduced in 2011 by Sindelar et al. [19] under the name of VM Packing with the addition of hierarchical sharing constraints making it suitable for virtual machine colocation. Without these constraints, we prefer the more general name of Pagination. After formulating it as an integer linear program, we try to approximate its solutions with several families of algorithms: from straightforward adaptations of classical Bin Packing heuristics, to dedicated algorithms (greedy and non-greedy), to standard and grouping genetic algorithms. All of them are studied first theoretically, then experimentally on an extensive random test set. Based upon these data, we propose a predictive measure of the statistical difficulty of a given instance, and finally recommend which algorithm should be used in which case, depending on either time constraints or quality requirements.

Introduction

Over the last decade, the book (as a physical object) has given ground to the multiplication of screens of all sizes. However, the page arguably remains the fundamental visual unit for presenting data, with degrees of dynamism varying from video to static images, from infinite scrolling (e.g., Windows Mobile interface) to semi-permanent display without energy consumption (e.g., electronic paper). Pagination is to information what Bin Packing is to matter. Both ask how to distribute a given set of items into the fewest number of fixed-size containers. But where Bin Packing generally handles concrete, distinct, one-piece objects, Pagination processes abstract groups of data: as soon as some data are shared by two groups packed in the same container, there is no need to repeat it twice.

Practical applications

As an introductory example, consider the following problem. A publisher offers a collection of audio CDs for language learning. Say that a typical CD consists of 100 short texts read by a native speaker; for each of them, a bilingual vocabulary of about 20 terms has to be printed out on the CD booklet. How best to do this? The most expansive option, both financially and environmentally, would require the impression of a 100-page booklet, i.e., with one page per audio text. But now suppose that each page can accommodate up to fifty terms. If all individual vocabularies are collated into one single glossary, no more than 100 × 20/50 = 40 pages are needed. This is the cheapest option, but the least convenient, since it forces the consumer to constantly leaf through the booklet while listening to a given text. To minimize cost without sacri-ficing usability, the publisher will be better off to pack into each page as many individual vocabularies as possible. If there were no common term between any two vocabularies, this problem would be Bin Packing; but obviously, most of the time, the vocabulary of a given text partially overlaps with several others: this is what we propose to call the pagination problem, in short Pagination.

In this example, it takes advantage of the fact that the more terms are shared by two vocabularies, the cheaper to pack them together; as an added benefit, a good pagination will tend to group on the same page the audio texts dealing with the same topic.

Coincidentally, it was in this context of linguistics that we first stumbled across Pagination. At that time, we needed to display selected clusters of morphologically related Chinese characters on a pocket-sized screen. A full description of our initial purpose would be beyond the scope of this paper, and ultimately unnecessary, since the problem is in fact perfectly general. It only differs from Bin Packing by the nature of the items involved: instead of being atomic, each such item is a combination of elements, which themselves have two fundamental properties: first, they are all the same size (relatively to the bin capacity); and second, their combination is precisely what conveys the information we care about.

For instance, the members of a social network may interest us only to the extent that they are part of one or several friendship circles. Such groups of mutual friends are nothing more than the so-called cliques of a graph (Fig. 1, upper), but the cliques are notoriously difficult to extract visually. Visualizing them as separated sets of vertices is more effective, although quite redundant. A better compromise between compacity and clarity is attained by paginating these sets as in Fig. 1 (lower part). Note that, although no group is scattered across several pages, finding all the friends of a given person may require the consultation of several pages.

Definition and complexity

Our problem is not just about visualization. It extends to any need of segmentation of partially redundant data (see Section 1.3.1 for an application to virtual machine colocation). Let us define it in the most general way: ,4) with a given capacity (here, at most 9 vertices). To allow each clique to be entirely contained in a single page, some vertices may be repeated on different pages (here, 19 on 3 pages, and 3, 4, 10, 16 on 2 pages). The individual page layouts are not relevant.

Definition 1. Pagination can be expressed as the following decision problem:

• Input: a finite collection T of nonempty finite sets (the tiles1 ) of symbols, an integer C > 0 (the capacity) and an integer n > 0 (the number of pages).

• Question: does there exist an n-way partition (or pagination) P of T such that, for any tile set (or page2 ) p of P, | ∪ t∈p t| ≤ C?

Example 1. On the left of Fig. 2, T = {{a, b, c, d, e}, {d, e, f}, {e, f, g}, {h, i, j, k}} denotes the tiles to be distributed on pages (with respect to a given capacity of 7). On the right, we present 4 possible such paginations of this set. For easier reading, in the remainder of this paper, any set of symbols (especially, a tile) defined by extension (for instance, {w, o, r, d}) will be represented as a gray block: word . Moreover, in any collection of symbol sets (especially T , or a page), the separating commas will be omitted: { May June July }.

Proposition 1. Pagination is NP-complete in the strong sense.

Proof. Any given pagination P can be verified in polynomial time. Furthermore, Bin Packing is a special case of Pagination with no shared symbol. Hence, the latter is at least as difficult as the former, which is strongly NP-complete.

In the rest of this paper, we focus on the associated NP-hard optimization problem (i.e., where the aim is to minimize the number of pages).

Related works

Bin Packing and its numerous variants are among the most studied optimization problems, and, as such, regularly subjected to comprehensive surveys [START_REF] Edward | Approximation algorithms for bin packing: a survey[END_REF][START_REF] Coffman | Bin Packing Approximation Algorithms: Survey and Classification[END_REF][START_REF] Johnson | Near-Optimal Bin Packing Algorithms[END_REF][START_REF] Martello | Bin-packing problem[END_REF]. The purpose of the present section is far more limited: to extract from this vast literature the few problems which exhibit the distinguishing feature of Pagination, i.e., which deal with objects able to overlap in a non-additive fashion. For instance, despite its similar name, we will not discuss Newspaper Pagination, a Bin Packing variant studied in [START_REF] Lagus | Paginating the generalized newspapers -A comparison of simulated annealing and a heuristic method[END_REF] for the placement of (obviously non overlapping) blocks of text on the columns of a generalized newspaper.

Virtual machine allocation

Pagination was first introduced in 2011 by Sindelar et al. [START_REF] Sindelar | Sharing-aware algorithms for virtual machine colocation[END_REF] in the context of virtual machine (VM) colocation. A VM can be seen as a set of memory pages: although most of them belong exclusively to one machine, some pages are identical across several machines. This happens more often as the configurations are close in terms of platform, system version, software libraries, or installed applications. If these VM run on the same physical server, their common memory pages can actually be pooled in order to spare resources.

The authors study two related problems. The first one, VM Maximization, is defined as follows: being given a collection of VM (our tiles), each consisting in a set of memory pages (our symbols), determine the most profitable subset of VM that can be packed into a given set of servers (our pages) having a capacity of k memory pages (of C symbols). Note that, with one server, this problem can be seen equivalently as Knapsack with Overlapping Items [START_REF] Grange | On the Knapsack Problem Under Merging Objects' Constraints[END_REF], or Densest k-subhypergraph. Hajiaghayi et al. [START_REF] Hajiaghayi | The minimum kcolored subgraph problem in haplotyping and DNA primer selection[END_REF] have proven the latter to be hard to approximate within a factor of 2 (log n) δ for some δ > 0, and Rampersaud and Grosu [START_REF] Rampersaud | A sharing-aware greedy algorithm for virtual machine maximization[END_REF] approximated it by a greedy heuristic with an approximation ratio equal to the number of VM. Furthermore, when the sharing among VM occurs in certain hierarchical fashions, Sindelar et al. have used a left-right dynamic programming method to devise a fully-polynomial time approximation scheme (FPTAS) [START_REF] Sindelar | Sharing-aware algorithms for virtual machine colocation[END_REF].

The second problem, VM Packing, is nothing else than Pagination: it demands to allocate the VM to a minimal number of servers. Sindelar et al. have shown that repeating their dynamic programming algorithm solves it within a O(log n) factor in a clustered version of the hierarchical model; and that a greedy algorithm achieves a factor of 3 when each cluster is a singleton.

Although these hierarchical restrictions lead to provably-good approximations algorithms, they say nothing about the general model, which the authors left open [START_REF] Sindelar | Sharing-aware algorithms for virtual machine colocation[END_REF]. Thereafter, efforts have mainly focused on models and methods designed specifically for the purposes of solving real-world VM allocation problems (e.g., [START_REF] Rampersaud | Sharing-aware online virtual machine packing in heterogeneous resource clouds[END_REF] with multiple resource requirements in an online setting, or [START_REF] Wilcox | Solving virtual machine packing with a reordering grouping genetic algorithm[END_REF] for approaches based on genetic algorithms): as far as we know, the general case has been left unexplored. In the interest of differentiating it from these VM-oriented models, we take the liberty to replace the terms of VM packing, memory pages, VM and servers, by the application-agnostic terms of Pagination, symbols, tiles and pages (respectively).

Hypergraph partitioning

Let us recall that a hypergraph G = (V, E) is defined by a set of vertices V and a set of hyperedges E, where each element of E is a subset of V [START_REF] Berge | Graphs and Hypergraphs[END_REF]. Bearing this in mind, it is easy to see the lefthand part of Fig. 2 as a subset-based drawing [START_REF] Kaufmann | Bet[END_REF] of a hypergraph mapping the instance, namely with V = A (the set of vertices is the set of symbols) and E = T ((the set of hyperedges is the set of tiles). Since Pagination is a partitioning problem, it is natural to ask whether we could take advantage of the extensive literature on Hypergraph Partitioning. In [START_REF] Karypis | Multilevel k-way Hypergraph Partitioning[END_REF] for instance, the latter problem is defined as "partitioning the vertices of a hypergraph into k roughly equal parts, such that a certain objective function defined over the hyperedges is optimized". Although our capacity constraint on the symbols is reminiscent of this "roughly equal" number of vertices, the main purpose of Pagination is to partition the tiles (i.e., the hyperedges), and certainly not the symbols (i.e., the vertices).

So, what happens if we try to exchange the roles of the tiles and the symbols? This gives the following alternative hypergraph representation of the instances of Pagination: V = T (the vertices are the tiles) and E = A (the hyperedges are the symbols). To be more specific, a symbol shared by several tiles connects them as a hyperedge, while a proper symbol (i.e., a symbol belonging to one tile only) connects this tile to itself as a hyperloop. Now, paginating G indeed amounts to partitioning the vertices, but in the meantime two issues have arisen. First, we do not care if each part contains roughly the same number of tiles: we want instead that the number of involved hyperedges is at most equal to C. Second, we have to express our objective function (minimizing the number of pages) on the hyperedges (the symbols). To cite [START_REF] Karypis | Multilevel k-way Hypergraph Partitioning[END_REF] again: "a commonly used objective function is to minimize the number of hyperedges that span different partitions". At first sight, it would indeed seem reasonable to minimize the number of replications of a given symbol across the pages. However, this leads to another impasse: Proposition 2. Minimizing the number of pages and minimizing the number of symbol replications are not equivalent. counterexample. For C = 5, let T = { a1 357 a2 468 }. The optimal pagination {{ a1 357 }, { a2 468 }} minimizes the number of pages (2), but not the number of replicas (symbol a is replicated once). Conversely, the non-optimal pagination {{ a1 a2 }, { 357 }, { 468 }} minimizes the number of symbol replications (0), but not the number of pages [START_REF] Coffman | Bin Packing Approximation Algorithms: Survey and Classification[END_REF].

Therefore, contrary to appearances, Pagination has very little in common with Hypergraph Partitioning 3 .

The rest of this paper is organized as follows.

In Section 2, we formulate Pagination as an integer linear program (ILP), and introduce the various metrics and rules used by our algorithms. Then, in Section 3, we describe several heuristics and metaheuristics for the problem. Finally, we compare the results produced by all the algorithms (exact or not) in Section 4, and conclude in Section 5.

Theoretical tools

To look on our problem from another perspective, let us formulate it as an ILP problem. In addition, we will be able to solve some (admittedly simple) instances with a generic optimization software. Thereafter, the introduction of several supplementary concepts will permit us to actually generate the instances, and to describe our own algorithms for tackling the largest ones.

Integer linear programming model

Numberings. We use the following sets of indexes:

• A = {i : i = 1, . . . , |A|} for the symbols;

• T = {j : j = 1, . . . , |T |} for the tiles;

• P = {k : k ∈ N} for the pages4 .

Inputs.

• C is a strictly positive integer capacity;

• a i j is an assignment of symbols to tiles: ∀i ∈ A, ∀j ∈ T, a i j = 1 if i ∈ t j , and 0 otherwise.

Decision variables.

For any i ∈ A, j ∈ T and k ∈ P , we define:

• x i k as equal to 1 if symbol i is present on page k, and 0 otherwise (pagination of the symbols);

• y j k as equal to 1 if tile j is present on page k, and 0 otherwise (pagination of the tiles);

• z k as equal to 1 if page k is used, and 0 otherwise (unitary usage of the pages).

It is worth noting that x i k = max j∈T (a i j y j k ) and z k = max j∈T (y j k ). The mathematical model of Pagination is thus entirely specified with y j k : the introduction of these auxiliary variables is only used to achieve the linearity of its formulation.

Integer linear program. A possible ILP formulation of Pagination

is: min. k∈P z k s. t. k∈P y j k = 1, ∀j ∈ T (1) z k ≥ x i k , ∀i ∈ A, ∀k ∈ P (2) i∈A x i k ≤ z k C, ∀k ∈ P (3) x i k ≥ a i j y j k , ∀i ∈ A, ∀j ∈ T, ∀k ∈ P (4) x i k , y j k , z k all binary, ∀i ∈ A, ∀j ∈ T, ∀k ∈ P (5)
Eq. 1 assigns each tile to exactly one page. Eq. 2 ensures that a page is used as soon as it contains one symbol. Conversely, thanks to the objective function, every used page contains at least one symbol. From Eq. 3, a page cannot contain more than C symbols. Eq. 4 guarantees that, when a tile belongs to a page, this page includes all its symbols 5 . The integrality constraints of the auxiliary variables of Eq. 5 could be relaxed.

Counting of the symbols

Definition 2 (metrics). Let α be a symbol, t a tile and p a set of tiles (most often, a page). Then:

1. the size |t| of t is its number of symbols; 2. the volume V(p) of p is its number of distinct symbols: V(p) = | ∪ t∈p t|; and its complement C -V(p), the loss on p;

3. by contrast, the cardinality Card(p) is the total number of symbols (distinct or not) in p:

Card(p) = t∈p |t|.
4. the multiplicity µ p (α) counts the occurrences of α in the tiles of p: µ p (α) = |{t ∈ p : α ∈ t}|;

5. the relative size of t on p is the sum of the reciprocals of the multiplicities of the symbols of t in p:

|t| p = α∈t 1 µp(α) .
In recognition of the fact that a given symbol may occur several times on the same page, the terms cardinality and multiplicity are borrowed from the multiset theory [START_REF] Syropoulos | Mathematics of Multisets[END_REF].

Example 2. In pagination P 3 of Fig. 2

: size |t 1 | = 5, volume V(p 1 ) = 6 (loss: 7 -6), cardinality Card(p 1 ) = 5 + 3, multiplicity µ p1 (e) = 2, relative size |t 2 | p1 = 1/2 + 1/2 + 1.
These definitions are extended to several pages (i.e., sets of sets of tiles) by summing the involved values:

Example 3. In the same figure, volume V(P 3 ) = 6 + 7 (loss: 7 -1 + 7 -7), cardinality Card(P 3 ) = Card(T ) = 5 + 3 + 3 + 4, multiplicity µ P3 (e) = µ T (e) = 2 + 1, relative size |t 2 | P3 = |t 2 | T = 1/2 + 1/3 + 1/2.
We are now able to express a first interesting difference with Bin Packing: Proposition 3. A pagination whose loss is minimal is not necessarily optimal. counterexample. For C = 4, the tile set T = { 12 13 23 ab ac bc } has a loss of 1+1 on the optimal pagination ({ 12 13 23 }, { ab ac bc }); but a loss of 0 + 0 + 0 on the non-optimal pagination ({ 12 ab }, { 13 ac }, { 23 bc }).

As seen in this counterexample, for the complete page set, multiplicity, cardinality and relative size do not depend on the pagination. Then: Proposition 4. A pagination is optimal if and only if the average cardinality of its pages is maximal.

Proof. Since the sum of the page cardinalities is always equal to t∈T |t|, its average depends only of the size n of the pagination. Hence, minimizing this size or that average is equivalent.

Simplifying assumptions

Definition 1 encompasses many instances whose pagination is either infeasible (e.g., one tile exceeds the capacity), trivial (e.g., all tiles can fit in one page) or reducible (e.g., one tile is a subset of another one). The purpose of this subsection is to bring us closer to the core of the problem, by ruling out as many such degenerated cases as possible.

For each one, we prove that there is nothing lost for an offline algorithm to ignore the corresponding instances.

Rule 1.

No tile is included in another one:

∀(t, t ) ∈ T 2 : t = t , t ⊆ t .
Proof. If t ⊆ t , then t and t can be put together on the same page of the optimal solution.

Remark 1. This does not hold for an online algorithm. Take for instance T = { 12 345 126 378 } and C = 5. If the tiles are presented in this order, the first two may be placed on the first page, making necessary to create a new page for each remaining tile: {{ 12 345 }, { 126 }, { 378 }}. An optimal pagination would require two pages only: {{ 12 126 }, { 346 378 }}.

In other words, the tile sets we deal with are Sperner families [START_REF] Sperner | Ein satz über untermengen einer endlichen menge[END_REF]. It follows that: Proof. Otherwise, let P be an optimal pagination, for a capacity of C -1, of the reduced instance T = {t \ α : t ∈ T and t = {α}}. Then adding α to each page of P gives an optimal pagination P of T for capacity C. Should a tile {α} exist in T , it can be put back at no cost on any page of P.

In other words, T has not the Helly property [START_REF] Mitre | Complexity aspects of the Helly property: Graphs and hypergraphs[END_REF]. Contrast this with VM Packing [START_REF] Sindelar | Sharing-aware algorithms for virtual machine colocation[END_REF], where the mere existence of root symbols violates this rule. Proof. Since all tiles contain at least one symbol, Rule 3 implies C ≥ 2. Assume that C = 2, i.e., all tiles consist in one single symbol. Hence,

{{t 1 , t 2 }, {t 3 , t 4 }, ...} is an optimal pagination of T in |T | 2 pages. Rule 8. C < |A|.
Proof. Otherwise, all tiles could fit in one page.

To sum up, an optimal solution of an instance violating Rules 1, 3 (with |t| = C), 4, 5 or 6, could be deduced from an optimal solution of this instance deprived of the offending tiles or symbols; an instance violating Rule 3 (with |t| > C) would be infeasible; an instance violating Rules 2, 7 or 8 would be trivial. All these rules can be tested in polynomial time, and are actually required by our instance generator (Section 4.1).

Heuristics

In this section, we investigate four families of heuristics for Pagination, from the simplest to the most sophisticated one. The first family consists of direct adaptations of the well-studied Bin Packing's greedy Any Fit algorithms; we show that, in Pagination, their approximation factor cannot be bounded. The second family is similar, but relies on the overlapping property specific to our problem; a general instance is devised, which shows that the approximation factor of their offline version is at least 3. With the third algorithm, we leave the realm of greedy decisions for a slightly more complex, but hopefully more efficient strategy, based upon a reentering queue. Finally, we present two genetic algorithms and discuss which encoding and cost function are better suitable to Pagination. All of this is carried out from a theoretical perspective, the next section being devoted to the presentation of our benchmarks.

Greedy heuristics inspired from

Bin Packing

Definitions

The question naturally arises of how the Bin Packing classical approximation algorithms [START_REF] Edward | Approximation algorithms for bin packing: a survey[END_REF] behave in the more general case of Pagination. Let us enumerate a few of them with our terminology:

• Next Fit simply stores each new tile in the last created page or, should it exceed the capacity, in a newly created page.

• First Fit rescans sequentially the pages already created, and puts the new tile in the first page where it fits.

• Best Fit always chooses the fullest page, i.e., the page with maximal volume. Such a criterion needs to be clarified in our generalization of Bin Packing: fullest before or after having put the new tile? This alternative should give rise to two variants.

• Worst Fit, contrary to Best Fit, favors the less full page.

• Almost Worst Fit is a variant of Worst Fit opting for the second less full page.

These algorithms are known under the collective name of Any Fit (AF). In their offline version, presorting the items by size has a positive impact on their packing; but for Pagination, such a sorting criterion would obviously be defective: due to possible merges, a large tile often occupies less volume than a small one.

A general unfavorable case

Regardless of its scheduling (online or offline), no AF algorithm has performance guarantee on the following extensible Pagination instance.

Let C be an even capacity (C = 4 on Fig. 3). Let A α = {α 1 , ..., α C } and A β = {β 1 , ..., β C } be two sets of distinct symbols such that A is the disjoint union of A α and A β . Let T α = Aα C/2 and T β = A β C/2 be the set of the C 2 -combinations of A α and A β (respectively). Then P opt = {T α , T β } is an optimal pagination of T = T α ∪ T β in 2 pages. Now, let us feed these tiles to any of our AF algorithms, but only after having sorted them in the worst order: since all of our tiles have the same size C/2, we are indeed free to organize them the way we want. The most unfavorable schedule simply involves alternating the tiles of T α and T β . In this way, regardless of the selected AF algorithm, the first two tiles would saturate the first page, the next two, the second page, and so on. In total, an AF algorithm would then create n

= |T α | = |T β | = C C/2 = C! (C/2)! 2 pages instead of 2.
In this family, the approximation factor is thus unbounded. This stands in stark contrast to the efficiency of the AF algorithms on Bin Packing-where, for instance, First Fit was recently shown [START_REF] Dósa | First Fit bin packing: A tight analysis[END_REF] to achieve an absolute factor of exactly 1.7.

Study case: First Fit algorithm

For our tests, we have chosen to focus on First Fit (in its online version). The worst case complexity can be analyzed as follows. There are |T | tiles to paginate. At worst, according to Rule 6, there exists only one tile compatible with any other, resulting in |T | -1 pages. Lastly, each set intersection costs a linear time in the size of the candidate tile. Hence, the overall complexity is O(|T | 2 Card(T )).

Note that in Bin Packing, for n items, an appropriate data structure can reduce the straightforward quadratic complexity to O(n log(n)) [START_REF] Johnson | Near-Optimal Bin Packing Algorithms[END_REF]. This optimization is not applicable here, where the current volume of a given page says little about its ability to accommodate a given tile.

Specialized greedy heuristics

Definition

We can easily improve on the Bin Packing heuristics by taking into account the merging property of Pagination items.

The corresponding offline greedy algorithms always select, among the remaining tiles, the one which minimizes or maximizes a certain combination of the metrics introduced in Definition 2 (e.g., volume, multiplicity, relative size, etc.). In their online version, since the new tile is given, this optimization relies only on the past assignments.

A general unfavorable case

Before introducing the particular heuristic we have the most thoroughly tested, Best Fusion, let us mark out the limitations of the algorithms of this family. We will design an extensible instance whose all tiles are equivalent with respect to these metrics. As such, they may be taken in any order, including the worst, which ensures that the reasoning is valid for both online and offline scheduling.

Take an even capacity C, and

A 0 = {α 1 , ..., α C } a first subset of A. Let T 0 = A0
C-1 the (C -1)combinations of A 0 , which amount to C tiles of size C -1. From now on, to better understand the general construction, we will illustrate each step on an example with C = 4:

A 0 = 1234 , T 0 = { 123 124 134 234 }
Introduce two more symbols, namely a and b, which will be used to lock the pages. Partition T into C 2 couples of tiles: (t 1 , t 2 ), (t 3 , t 4 ), ..., (t C-1 , t C ). From each such couple, form

A i = (t 2i-1 ∩ t 2i ) ∪ {a, b} with 1 ≤ i ≤ C 2 , a subset of A.
In the same way as on A 0 , define T i = Ai C-1 on each A i :

A 1 = 12ab , T 1 = { 12a 12b 1ab 2ab } A 2 = 34ab , T 2 = { 34a 34b 3ab 4ab }
Constructing this instance is actually constructing an optimal solution to it. Indeed, for the whole tile set, |P opt | = C 2 + 1:

p 1 = { 123 124 134 234 } → 1234 p 2 = { 12a 12b 1ab 2ab } → 12ab p 3 = { 34a 34b 3ab 4ab } → 34ab
Now, let us construct a non-optimal pagination. This is done by pairing each tile of T 0 with a tile including a "locking" symbol. Specifically, on pages 2i -1 and 2i, put respectively t 2i-1 and t 2i , and lock these pages with tiles (t 2i-1 ∩ t 2i ) ∪ {a} and (t 2i-1 ∩ t 2i ) ∪ {b} (respectively) from T i . This process creates C locked pages:

p 1 = { 123 12a } → 123a p 2 = { 124 12b } → 124b p 3 = { 134 34a } → 134a p 4 = { 234 34b } → 234b
But what enables us to construct such inefficient two-tile pages? All tiles having the same size, it is clear that the first one can be chosen arbitrarily. Now, let t be an eligible second tile, and p the resulting page. Then, all t are equivalent under our various metrics: same size |t | = C -1, same volume

V(p ) = C, same cardinality Card(p ) = 2(C -1), same relative size |t | p = C-2 2 +1 = C 2 .
So, nothing prevents our greedy algorithms to systematically select the worst candidate.

If C > 2, the C -2 tiles including both a and b still remain in every tile set (but T 0 ). For each one, gather its tiles on a new page:

p 5 = { 1ab 2ab } → 12ab p 6 = { 3ab 4ab } → 34ab
Finally, we have obtained a non-optimal pagination P totaling C + C 2 = 3C 2 pages. Hence, for a given even capacity C, any greedy algorithm of this family may yield |P| |Popt| = 3C C+2 times more pages than the optimal. In other words, its approximation factor is at least 3.

Study case: Best Fusion algorithm

In our benchmarks, the following criterion was used: for each tile t, let p be the eligible page on which the relative size |t| p is minimal. If |t| p < |t|, then put t on p; otherwise, put t on a new page. We call Best Fusion the online version of this algorithm. Its worst-case complexity is the same as in First Fit, i.e., O(|T | 2 Card(T )).

Since a new page is created for every tile whose assignment to an existing page would bring no immediate benefit, the cases raised in Section 3.1.2 are solved to optimality. However, the downside of such a strategy becomes readily apparent with pure Bin Packing instances: in the absence of shared symbols, each new tile will trigger the creation of a new page. Consequently, Best Fusion has no more performance guarantee than the AF algorithms. The difference here is that no resulting page is locked in a bad state. In practice, this flaw is easily fixed by the so-called decantation posttreatment (see Section 3.5), which can be considered as a multi-scale First Fit 6 . 6 Strictly speaking, with this post-treatment, Best Fusion is no more greedy. Preserving at the same time the greediness of the algorithms of the present family, and an

Overload-and-Remove heuristic

The following non-greedy approach has the ability to reconsider past choices whenever better opportunities arise. As a result, in particular, it always finds the optimal solution of the unfavorable cases outlined in Sections 3.1.2 and 3.2.2.

The main idea is to add a given tile t to the page p on which t has the minimal relative size, even if this addition actually overloads p. In this case, the algorithm immediately tries to unload p by removing the tile(s) t of strictly smallest size relative size ratio. The removed tiles are rescheduled at the latest by adding them to a FIFO data structure, and simultaneously forbidden to reenter the same page-this ensures termination. When the main loop is over, the possible remaining overloaded pages are suppressed, and their tiles redistributed by First Fit.

Algorithm: Overload-and-Remove Q ← queue containing all the tiles of T P ← pagination consisting of one empty page while Q is nonempty: In the worst case, a given tile might successively overload and be removed from all pages, whose total number is at most |T |. Each trial requires one set intersection on each page. Hence, the overall complexity is O(|T | 3 Card(T )).

| t ← dequeue(Q) | P t ←
acceptable behavior on both Section 3.1.2's and pure Bin Packing's instances, can nevertheless be attained by means of offline scheduling (described in Section 3.2.1). This is at least |T | times more complex, and still untested. Due to its overly broad encoding capabilities, Standard GA is not guaranteed to produce a valid pagination. Our fitness function is devised with this in mind, in such a way that an invalid chromosome would always cost more than a valid one. Thus, seeding the initial population with at least one valid individual will be enough to ensure success.

Evaluation. Our aim is twofold. First and foremost, to penalize the invalid paginations; second, to reduce the volume of the last nonempty page. For this purpose, we will minimize the fitness function f defined as follows:

As soon as one page is overloaded (i.e., ∃k ∈ P :

i∈A x i k > C)
, we count |T |C symbols (as if all possible pages were saturated), to which we also add every extra symbol:

f (P) = |T |C + k∈P max 0, ( i∈A x i k ) -C (6a)
Otherwise, let us call k the index of the last nonempty page (i.e., such that ∀k > k, z k = 0). Count (k -1)C symbols (as if all nonempty pages but the last one were saturated), and add the number of symbols on page p k :

f (P) = (k -1)C + i∈A x i k (6b)
Example 5. If all tiles of Fig. 2 were put on a single (invalid) page, by (6a), the fitness value would reach 4 × 7 + 4 = 32. By (6b), the paginations P 1 to P 4 have a fitness value of 3 × 7 + 4 = 25, 2 × 7 + 4 = 18, 1 × 7 + 7 = 14, and 1 × 7 + 4 = 11 (respectively).

Mutation. It consists in transferring one randomly selected tile from one page to another.

Crossover. The standard two-point crossover applies here without requiring any repair process.

Grouping model

In [START_REF] Falkenauer | A genetic algorithm for bin packing and line balancing[END_REF], Falkenauer et al. show that classic GAs are not suitable to the grouping problems, namely "optimization problems where the aim is to group members of a set into a small number of families, in order to optimize a cost function, while complying with some hard constraints". To take into account the structural properties of such problems, the authors introduce the so-called grouping genetic algorithms (GGA). Their main idea is to encode each chromosome on a one gene for one group basis. The length of these chromosomes is thus variable: it depends on the number of groups. Crucially, the belonging of several items to the same group is protected during crossovers: the good schemata are more likely to be transmitted to the next generations.

Pagination is clearly a grouping problem, moreover directly derived from Bin Packing-one of the very problems Falkenauer chooses to illustrate his meta-heuristic. We thus will adapt, and sometimes directly apply his modelization.

Encoding. A valid pagination on n pages is encoded as a tuple (p 1 , ..., p n ) where p k is the set of the indexes of the tiles put on the k th page.

Example 6. This time, the paginations of Fig. 2 would be encoded as ({1}, {2}, {3}, {4}), ({1}, {2, 3}, {4}), ({1, 2}, {3, 4}) and ({1, 2, 3}, {4}) (respectively). Or, in Falkenauer's indirect, but sequential notation: 1234:1234, 1223:123, 1122:12 and 1112:12, where the left part denotes, for each j th tile, the index of its page; and the right part, the list of all pages.

Evaluation. In our notation, the maximization function of [START_REF] Falkenauer | A genetic algorithm for bin packing and line balancing[END_REF] for Bin Packing would be expressed as f

BP (P) = 1 n n k=1 ( 1 C V(p k )) d .
In other words, the average of volume rates raised to a certain disparity d, which sets the preference given to the bins' imbalance: thus, for the same number of bins and the same total loss, the greater the disparity, the greater the value of an unbalanced packing.

Although this formula still makes sense in the context of Pagination, we should not apply it as is. Indeed, whereas minimizing the loss amounts to minimizing the number of bins, Proposition 3 warns us this is actually untrue for the number of pages: in the associated counterexample, with d = 2 (the empirical value proposed by [START_REF] Falkenauer | A genetic algorithm for bin packing and line balancing[END_REF]), the optimal pagination would be evaluated to ((3/4) 2 + (3/4) 2 )/2 = 0.5625, and the suboptimal one to ((4/4) 2 + (4/4) 2 + (4/4) 2 )/3 = 1.

Instead of privileging the high volume pages, we will privilege the high multiplicity ones (i.e., replace V(p k ) by Card(p k )). Proposition 4 guarantees that the higher the average page multiplicity, the better the overall pagination.

One detail remains to be settled: ensure that the quantity raised to the power d never exceeds 1. Here, in the same way that V(p k ) is bounded by C, Card(p k ) is bounded by Card(T ), and even, more tightly, by the sum of the multiplicities of the C most common symbols, which we will note M T C . This leads us to the following fitness function for Pagination:

f (P) = 1 n n k=1 Card(p k ) M T C d (7)
Example 7. In Fig. 2, M T C = 3 + 2 + 2 + 1 + 1 + 1 + 1 = 11. With d = 2, the four paginations are respectively evaluated as follows:

(5/11) Mutation. The mutation operator of [START_REF] Falkenauer | A genetic algorithm for bin packing and line balancing[END_REF] consists in emptying at random a few bins, shuffling their items, and then inserting them back by First Fit. We follow the exact same procedure, but without the suggested improvements: at least three reinserted bins, among which the emptiest one.

Crossover. The two parents (possibly of different length) are first sliced into three segments:

(a 1 , a 2 , a 3 ) et (b 1 , b 2 , b 3
). The tiles of b 2 are withdrawn from a 1 and a 3 : a 1 = a 1 \b 2 and a 3 = a 3 \b 2 .

To construct the first offspring, we concatenate (a 1 , b 2 , a 3 ), sort the missing tiles in decreasing order, and insert then back by First Fit. The second offspring is calculated in the same manner (just exchange the roles of a and b).

Post-treatment by decantation

We introduce here a quadratic algorithm which, in an attempt to reduce the number of pages, will be systematically applied to the results produced by all our heuristics but First Fit. Its three steps consist in settling at the beginning of the pagination as much pages, components and tiles as possible. First, we must specify what is a component: Definition 3. Two tiles are connected if and only if they share at least one symbol or are both connected to the same intermediate tile. The (connected) components are the classes of the associated equivalence relation.

Example 8. In Fig. 2, the components of the instance are { abcde def efg } and { hijk }. Definition 4. A valid pagination is said to be decanted on the pages (resp., components, tiles) if and only if no page contents (resp., component, tile) can be moved to a page of lesser index without making the pagination invalid.

Example 9. In Fig. 2, P 3 is decanted on the pages, but not on the components or the tiles. P 4 is a fully decanted pagination (on the pages, the components and the tiles).

Obviously, a pagination decanted on the tiles is decanted on the components; and a pagination decanted on the components is decanted on the pages. To avoid any unnecessary repetition, the corresponding operations must then be carried out in the reverse direction. Moreover, the best decantation of a given pagination P is attained by decanting P successively on the pages, the components, and then the tiles.

Example 10. Let ({ 123 }, { 14 567 }, { 189 }) be a pagination in 3 pages with C = 5. Its decantation on the components, ({ 123 14 }, { 567 }, { 189 }), does not decrease the number of pages, as opposed to its decantation on the pages: ({ 123 189 }, { 14 567 }). For an example on components/tiles, let us substitute 567 with 1567 in the instance. Let ({ 123 }, { 14 1567 }, { 189 }) be a pagination in 3 pages with C = 5. Its decantation on the tiles, ({ 123 14 }, { 1567 }, { 189 }), does not decrease the number of pages, as opposed to its decantation on the components: ({ 123 189 }, { 14 1567 }). This decantation algorithm is thus implemented as a sequence of three First Fit procedures of decreasing granularity. In our tests, the interest of such a post-treatment varies greatly: it is of course useless on First Fit, but reduces the outcomes of GAs by one page in about 0.1 % of cases, and both Best Fusion and Overload-and-Remove by up to ten pages for about 21 % and 40 % of instances, respectively.

Experimental results

Supplementary material. In order to empower the interested readers to reproduce our analysis and conduct their own investigation, we provide at [START_REF] Grange | Algorithms for the bin packing problem with overlapping items: Dataset and experimental results[END_REF] a ∼60 MB Git repository containing: the whole set of our random instances (gauss); a companion Jupyter Notebook (analysis.ipynb) which generates every plot and numerical result mentioned or alluded in the present section; some instructions for using this notebook interactively (README.md).

Generating a test set

First, let us introduce another simplifying assumption:

Rule 9 (optional). All tiles contain more than one symbol: ∀t ∈ T , |t| > 1.

This rule cannot be considered on the same level than those of Section 2.3: forbidding one-symbol tiles may theoretically make some instances easier to paginate. counterexample. By definition, no tile is empty. Suppose there exists a tile t of size 1, and let P be an optimal pagination of the reduced instance T \ {t}. If there exists a page p ∈ P such that |p | < C, then adding t on p produces an optimal pagination of T . However, in the rare cases where all pages are saturated, P ∪ {{t}} is not necessarily an optimal pagination of T . Take for instance T = { 0 123 45 167 89 } and C = 5. The reduced instance T \ { 0 } admits an optimal pagination P = {{ 123 45 }, { 167 89 }}, all of whose pages are saturated. Nevertheless, the pagination P ∪ {{ 0 }} has one page more than the optimal pagination P = {{ 123 167 }, { 45 89 0 }}.

Since the latter behavior requires both a specially constructed instance and a particularly weak pagination algorithm, we have chosen to add this constraint during the generation of our random test sets: in practice, it will have no other effect than to avoid polluting the instances with a bunch of unmergeable, interchangeable, easy-to-place tiles. Although in some rare cases, numerous passes were required before halting on a result, it proved to be robust enough to produce, for each distinct combination of its parameters, six valid instances (for a total of 10,986 instances).

Measuring the statistical difficulty of a given instance

What is a difficult instance of Pagination? Although we cannot answer this question in all generality, the highly experimental nature of the present approach certainly enables some observations to be made. Indeed, we have not only generated several thousands of instances, but also submitted them to no less than six different solvers: one ILP, two genetic algorithms, two greedy algorithms, and one specialized heuristic (not counting its sorted variant), Overload-and-Remove. When these various methods all produce roughly the same number of pages, one can conclude that the instance was an easy one; conversely, when the pagination size differs greatly among methods, it clearly presents some particular challenges.

The dispersion of the pagination sizes can be measured in several ways: range (i.e., difference between minimum and maximum), average range (i.e., average difference with the minimum), standard deviation, median absolute deviation... Although, statistically speaking, the last one is the most robust, the second one proved to be slightly more suited to our problem, where outliers are arguably no accidents, but rather evidences of some significant structural features. Hence: Conjecture 1. The statistical difficulty of a given instance can be approximated by the difference between the average and the minimal number of pages in the paginations calculated by our various solvers.

There are some caveats. First, this measure of the statistical difficulty is intrinsically correlated (Pearson's r = 0.792 [START_REF] Pearson | Notes on regression and inheritance in the case of two parents[END_REF]) to the size of the best pagination (e.g., if the best algorithm produces 2 pages, it is unlikely that any of its competitors will produce 20 pages). This is by design. Intuitively, a "large" random instance is more difficult to paginate than a "small" one. For example, the larger an instance, the longer it takes for a brute force algorithm to find the optimum. In our tests, normalizing the difference by dividing it by the best size has indeed proven counterproductive.

Second caveat, this measure only makes sense for random instances. We certainly could devise a particular instance which would be easy for a special tailored algorithm, but difficult for our generalpurpose solvers.

Third caveat, CPLEX gave us the optimal pagination for only 43 instances. That the minimum heuristic result is the optimum, or a tight estimate, is therefore not guaranteed. Note however that, when the optimum is known, the same number of pages is produced by at least one heuristic in 1 -4/43 = 91 % of the cases.

Finally, as its name suggests, this measure depends on our set of algorithms. Therefore, adding another one may either increase or decrease the statistical difficulty of any instance. Of course, the more "reasonable" algorithms would be tested, the less the prevalence of this effect.

Predicting the statistical difficulty of a given instance

Pagination can be seen as an almost continuous extension of Bin Packing: being given a pure Bin Packing instance (i.e., no tile has shared symbols), we may gradually increase its intricacy by transforming it into a Pagination instance as convoluted as desired (i.e., many tiles share many symbols). Therefore, we can expect that:

Conjecture 2. The statistical difficulty of a given random instance is strongly correlated to the density of its shared symbols, or average multiplicity. A multiplicity of 10 indicates that, in the corresponding instances, a given symbol is shared by an average of 10 tiles. For these instances, the average range of pagination sizes produced by our different solvers (the so-called difficulty) varies between 0 (all solvers obtain the same number of pages) and 5.

Figure 4 tests this hypothesis on our instance set: the average multiplicity of a given random instance appears to be a good predictor (r = 0.784) of its statistical difficulty. Is it the best one? We can think of a few other possible candidates, and calculate their correlation with the statistical difficulty: Before we go any further, it is important to be aware that the average multiplicities in our test set are far from being evenly distributed (Fig. 5): for example, there are 1119 instances whose average multiplicity lies between 4 and 5, but only 107 between 23 and 24, and 10 between 53 and 54 (see [START_REF] Grange | Algorithms for the bin packing problem with overlapping items: Dataset and experimental results[END_REF] for these exact values). Overall, more than half of them concentrate between multiplicities 2 and 9.

Thus, any observation made on the higher multiplicities (and the smaller ones) must be approached with great caution.

Discussion

Behavior of the integer linear program

As seen in Fig. 5, only a limited subset of our instances (342 of 10,986) have been submitted to CPLEX. This was for practical reasons: despite a powerful testing environment (Linux Ubuntu 12.04 on Intel Core i5-3570K with 4 cores of 3.4 GHz and 4 GB of RAM), CPLEX turned out to need a generous time-limit of one hour to be able to solve to optimality a mere 12.6 % of this subset (i.e., 43 instances). The ratio dropped to 3.8 % when the average multiplicity reached 13; above 20, no more success was recorded. Thus, this ILP quickly becomes irrelevant as the multiplicity increases, i.e., as Pagination starts to distinguish itself from Bin Packing.

Unless we could find strong valid inequalities to improve it, our experimentations suggest that the heuristic approach constitutes a better alternative. All of our heuristics have been implemented in Python 2.7, and tested under Mac OS X 10.10 on Intel Core i5-3667U with 2 cores 7 of 1.7 GHz and 4 GB RAM. The average execution time ranges from less than 0.1 seconds for the greedy algorithms, 1 second for Overload-and-Remove, 7 seconds for Standard GA, through 90 seconds for Grouping GA. For the two GAs, the following parameters were selected as offering the best ratio quality/time: 80 individuals, 50 generations, crossover rate of 0.90, mutation rate of 0.01. Their initial population was constituted of valid paginations obtained by applying First Fit to random permutations of the tile set. Figure 6 shows how the various algorithms scale as multiplicity grows: performance-wise at least, all remain practical on our most difficult instances.

Comparison of the heuristic methods

Note that this analysis, and the next one, are carried out on a moving window of equally-sized subsets of instances sorted by increasing average multiplicity: by eliminating noise, this technique helps to visually separate the different curves; it has the side-effect of making some endpoints disappear, but, as explained in Section 4.3, their loss is greatly outweighed by the gain of a constant confidence level on the remaining data. heuristics. The irregularities of the top line also somehow give indirect insight into the rare achievements of our ILP (among the 342 instances submitted to CPLEX, only 6 proved to have a better solution than the result of the best heuristic). General observations and recommendations that can be derived from the underlying data are as follows.

Standard GA can definitely be ruled out. As expected from Section 3.4.2, Standard GA was consistently surpassed by the more sensible Grouping GA: no more than 4 exceptions (0.036 %) occurred. Rather suspiciously, all of them involved a minimal instance, i.e., subject to a 2-page pagination. Further examination revealed that, in each case, this optimal pagination was already present in the initial random population constructed by First Fit; hence, its apparition was by no means indicative of some rare small-scale superiority of Standard GA: due to the fact that our implementation systematically transmits the best individual to the next generation, it was preserved, rather than produced by the evolution. This may also partially explain as pure chance the comparatively good performances in the lowest multiplicities; beyond that, the curve stabilizes quickly around an 85 % efficiency of Grouping GA. Finally, note that, up to an average multiplicity of 15, Standard GA is even outclassed by Overloadand-Remove, a six times faster heuristic.

Grouping GA produces the best overall results. When quality is the top priority, Grouping GA is the way to go: it almost always (99.64 % of cases) guarantees equivalent or smaller paginations than any other heuristic. ILP did improved on it in 6 cases (1.75 % of the 342 selected instances): 2 with a better feasible solution, 4 with the optimal solution. But even if such good surprises would multiply on the whole set of instances, we must keep in mind that CPLEX was given one hour on four cores, against about 90 seconds to a pure Python implementation running on a single core (twice as slow): Grouping GA has yet to unleash its full potential.

The fastest non-genetic contender is among Best Fusion and Overloadand-Remove. If speed matters, the choice depends on the average multiplicity of the instance: in most cases, Overload-and-Remove records quite honorable results. It is even the only non-genetic algorithm which proved occasionally (0.2 % of cases) able to beat Grouping GA. However, its quality regularly deteriorates (count up to 5 % for a 10 points increase in multiplicity). Around 35, somewhat surprisingly, the greedy algorithms get more and more competitive, with Best Fusion taking over at 40. Regardless of why this happens, a specialized heuristic for such deeply intricate instances would certainly be needed; in the meantime, Best Fusion represents the best tradeoff when average multiplicity meets or exceeds the 40 mark.

Conclusion

In this paper, we revisited an extension of Bin Packing originally devised by Sindelar et al. [START_REF] Sindelar | Sharing-aware algorithms for virtual machine colocation[END_REF] for the virtual-machine colocation problem. We broadened its scope to an application-agnostic sharing model: in Pagination, two items can share unitary pieces of data, or symbols, in any nonhierarchical fashion. We showed that with such overlapping items, or tiles, the familiar tools and methods of Bin Packing may produce surprising results: for instance, while the family of Any Fit approximations have no more guaranteed performance, genetic algorithms still behave particularly well in the group-oriented encoding of [START_REF] Falkenauer | A genetic algorithm for bin packing and line balancing[END_REF]. We tested all these algorithms on a large set of random instances, along with an ILP solver, and some specialized greedy and non-greedy heuristics. The choice of the best one is not clear-cut, but depends on both time/quality requirements and the average multiplicity of the symbols. The latter measure was proposed as a predictor of the statistical difficulty of a given instance, and correlated experimentally with the actual outcome of our various algorithms.

Obviously, this work did not aim to close the problem, but rather to open it to further research, by providing the required vocabulary, several theoretical tools, and an extensive benchmark. Indeed, numerous directions should be investigated: examples of these are worst-case analysis, proof of lower bounds, elaboration of efficient cuts, etc. To make Pagination more manageable, a promising approach restricts it to one single page [START_REF] Grange | On the Knapsack Problem Under Merging Objects' Constraints[END_REF][START_REF] Rampersaud | A sharing-aware greedy algorithm for virtual machine maximization[END_REF].

Figure 1 :

 1 Figure 1: Application of Pagination to the visualization of the cliques of a given graph. The cliques are split over a small number of pages (here, 4) with a given capacity (here, at most 9 vertices). To allow each clique to be entirely contained in a single page, some vertices may be repeated on different pages (here, 19 on 3 pages, and 3, 4, 10, 16 on 2 pages). The individual page layouts are not relevant.

4 Figure 2 :

 42 Figure 2: For the tiles T = { abcde def efg hijk } and a capacity C = 7, P 3 = ({ abcde def }, { efg hijk }) is a possible optimal pagination in n = 2 pages.

Corollary 1 (Rule 2 .Rule 3 .

 123 Sperner's Theorem). A page of capacity C contains at most No tile contains all the symbols: t ∈ T : t = A. Proof. Direct consequence of Rule 1. Each tile has less than C symbols: ∀t ∈ T , |t| < C.Proof. Let t be an arbitrary tile. If |t| > C, the problem has no solution. If |t| = C, then no other tile t could appear on the same page as t without violating Rule 1. Let P be an optimal pagination of the reduced instance T \{t}. Then P = P ∪{{t}} is an optimal pagination of T . Rule 4. No symbol is shared by all tiles: α ∈ A : ∀t ∈ T , α ∈ t.

Rule 5 .

 5 Each symbol belongs to at least one tile: ∀α ∈ A, ∃t ∈ T : α ∈ t. Proof. By Definition 1 of an instance. Rule 6. Each tile is compatible with at least another one: ∀t ∈ T , ∃t ∈ T \ {t} : |t ∪ t | ≤ C. Proof. If there exists a tile t not compatible with any other, any solution should devote a complete page to t. The conclusion of the proof of Rule 3 still applies here. Rule 7. C > 2.

Figure 3 :

 3 Figure 3: To the left, a set T = T α ∪ T β of 2 4 2 = 12 tiles; at the center, a pagination of capacity 4 calculated by the Any Fit algorithms when the tiles of T α and T β are fed alternatively; to the right, an optimal pagination.

3. 4

 4 Genetic algorithms 3.4.1 Standard model Encoding. Any pagination (valid or not) on n pages is encoded as a tuple (k 1 , ..., k |T | ) where k j ∈ [1, n] is the index of the page containing the tile t j . Example 4. The four paginations of Fig. 2 would be respectively encoded as (1, 2, 3, 4), (1, 2, 2, 3), (1, 1, 2, 2) and (1, 1, 1, 2).

Figure 4 :

 4 Figure4: Statistical difficulty by average multiplicity (r = 0.784). A multiplicity of 10 indicates that, in the corresponding instances, a given symbol is shared by an average of 10 tiles. For these instances, the average range of pagination sizes produced by our different solvers (the so-called difficulty) varies between 0 (all solvers obtain the same number of pages) and 5.

Figure 5 :

 5 Figure 5: Number of instances by average multiplicity (sym-log scale).

Figure 6 :

 6 Figure 6: Performance of the main heuristics (log scale). From top (slowest) to bottom (fastest): Grouping GA, Standard GA, Overload-and-Remove, Best Fusion, First Fit.

Figure 7 :

 7 Figure 7: Relative quality of the five main heuristics. The outcomes are plotted at y = best sizesize , with y = 1 corresponding to the best known solution (which is either the optimal or the best feasible solution found by CPLEX, or the smallest approximation calculated for the given instance).

Figure 7

 7 Figure7compares the results of the various7 Since Python can only execute on a single core, we usually launched two processes in parallel.

  pages of P where t has never been put on | if P t has no page p such that |t| p < |t|: | | add to P a new page consisting solely of {t} | | continue with next iteration | p ← page p of P t such that |t| p is minimal | put tile t on page p | while V(p) > C and ∃t 1 , t 2 ∈ p 2 :

	|t1| |t1|p = |t2| |t2|p :
	| | remove from p one tile t minimizing |t |/|t | p
	| | enqueue(Q, t )
	remove all the overloaded pages from P
	put their tiles back in P (by First Fit)

  As one can see, P 4 (the most unbalanced pagination) scores better than P 3 . The difference would increase with disparity d.

	2 + (3/11) 2 + (3/11) 2 + (4/11) 2 /4 0.12
	(5/11) 2 + (6/11) 2 + (4/11) 2 /3 0.21
	(8/11) 2 + (7/11) 2 /2 0.47
	(11/11) 2 + (4/11) 2 /2 0.57

  Our instance generator takes as input a capacity C, a number |A| of symbols and a number |T | of tiles. It follows a three-step process: 1. Calculate a standard deviation s = C 5 and a mean m = RC 4 , where R is a random variable uniformly distributed on {1, 2, 3}. 2. Draw an integer k from the corresponding normal distribution: k ∼ N (m, s 2 ). If 1 < k < C (Rules 3 and 9), make a candidate tile up from a uniform random sample of k distinct symbols. Add it to the accepted set if and only if Rule 1 is still satisfied. Repeat this step until |T | tiles are obtained. This algorithm has been called repeatedly with C varying from 15 to 50 in steps of 5, |A| varying from C + 5 to 100 in steps of 5 (for lesser values, by Rule 7, all symbols would fit in a single page) and |T | varying from 20 to 100 in steps of 5.

	3. Accept the resulting instance if and only if
	Rules 4, 5 and 6 are satisfied.

The fact that Pagination generalizes Bin Packing has its counterpart in our terminology: the items become the tiles, since they can overlap like the tiles on a roof.

Likewise, the move from concrete to abstract is reflected by the choice of the term page instead of bin.

The problem studied in[START_REF] Duncan | A branch-and-bound algorithm for pagination[END_REF], and coincidentally named pagination (by reference to the fixed-length contiguous block of virtual memory, or memory-pages), is in fact a special case of Hypergraph Partitioning, where the objective is to minimize the total weight of edge-cuts in a weighted graph, with an upper bound on the size of the parts.

For the sake of simplicity, we assume that an infinite number of pages are available. In practice, prior to the calculations, this number will be limited to a reasonable value, either given by a heuristic, or |T | (one tile per page) in the worst case.

Although Eq. 4 produces a lot of unnecessary constraints of the form x i k ≥ 0, we prefer it to the equivalent, but slightly less explicit formulation x i k ≥ y j k , ∀j ∈ T, ∀i ∈ t j , ∀k ∈ P .

• r = -0.082 for |A|, the number of symbols;

• r = 0.366 for |A|×|T |, the size of the instance, i.e., the number of bits required to encode it. More precisely, a stream of |A|×|T | bits, where the ith bit is 1 if and only if the i/|T | -th tile of T includes the (i mod |T |)-th symbol of A (plus three long integers for the capacity, the size of the alphabet and the number of tiles, all of them being dominated by the first quantity).

• r = 0.563 for |T |, the number of tiles.

• r = 0.770 for Card(T ), the sum of the tile sizes.

Among these candidates, Card(T ), the cardinality of the tile set, is almost as good a predictor as Card(T )/|A|, its average multiplicity. The choice of the latter value is mainly dictated by the fact that it involves the number of symbols. Indeed, when |A| approaches Card(T ), Pagination approaches Bin Packing, which we expect to reduce the difficulty of the instance.

(1, 3] (3, 5] (