Joanne L Hall
email: joanne.hall@rmit.edu.au

Metod Saniga
email: msaniga@astro.sk

Free Cyclic Submodules and Non-Unimodular Vectors

Keywords:

Given a finite associative ring with unity, R, and its two-dimensional left module, 2 R, the following two problems are addressed: 1) the existence of vectors of 2 R that do not belong to any free cyclic submodule (FCS) generated by a unimodular vector and 2) conditions under which such (non-unimodular) vectors generate FCSs. The main result is that for a non-unimodular vector to generate an FCS of 2 R, R must have at least two maximal right ideals of which at least one is non-principal.

Introduction

Projective geometries over finite associative rings with unity have recently found important applications in coding theory (see, e. g., [START_REF] Honold | Linear codes over finite chain rings and projective Hjelmslev geometries[END_REF]) and quantum information theory (see, e. g., [START_REF] Planat | Quantum entanglement and projective ring geometry[END_REF][START_REF] Havlicek | Projective ring line of an arbitrary single qudit[END_REF][START_REF] Saniga | Projective ring line encompassing two-qubits[END_REF]). When constructing a geometry over a ring, a majority of authors consider as points of such a geometry only free cyclic submodules (FCSs) generated by unimodular vectors [START_REF] Veldkamp | Geometry over rings[END_REF], whilst some authors consider all cyclic submodules [START_REF] Brehm | Projective geometry on modular lattices[END_REF][START_REF] Faure | Morphisms of projective spaces over rings[END_REF]. It has recently been shown [START_REF] Havlicek | Vectors, cyclic submodules and projective spaces linked with ternions[END_REF] that there exists rings for which some vectors of the submodule are not contained in an FCS generated by a unimodular vector. These vectors have been called outliers. Even more interesting is that some outliers themselves generate FCSs. A geometry may be constructed using all FCSs.

Analysing all finite associative rings with unity up to order 31 inclusive, only several rings are found to feature outliers. Out of these, only few non-commutative rings exhibit FCSs comprising solely non-unimodular vectors [START_REF] Saniga | Projective lines over finite rings, an invited Kempner colloquium given at the Department of Mathematics[END_REF]; the smallest example being the ring of ternions over the Galois field of order two [START_REF] Havlicek | Vectors, cyclic submodules and projective spaces linked with ternions[END_REF]. These examples motivated a more systematic and general treatment of the questions of the existence of outliers and FCSs generated by them. The outcomes of our explorations are not only interesting on their own, but they can also have interesting physical bearings (like, e. g., those proposed in [START_REF] Saniga | Space versus time: unimodular versus non-unimodular projective ring geometries?[END_REF]).

Definitions and Preliminaries

All rings considered are finite, associative and with unity (multiplicative identity). It is well known that in such a ring, R, an element is either a unit or a (two-sided) zero-divisor (see, for example, [11, §2.1]); in what follows the group of units of R is denoted by R * and the set of zero divisors by R \ R * . 1 is the unity element of R and the symbol ⊂ stands for strict inclusion.

Definition 1. Let R, •, + be a ring. A left ideal, I l , is a subgroup of R, + such that rx ∈ I l for all r ∈ R and x ∈ I l . A right ideal, I r , is a subgroup of R, + such that xr ∈ I r for all x ∈ I r and r ∈ R. An ideal is principal if it is generated by a single element of R. For a ∈ R the principal left ideal generated by a is Ra, and a principal right ideal generated by a is aR.

For further background on rings see, for example, [START_REF] Lam | A First Course in Noncommutative Rings[END_REF]. Definition 2. [5, Defi 2.9][13, p. 16] Let S ⊆ R. The left (right) annihilator of S, denoted ⊥ S (S ⊥ ), is defined as:

⊥ S = {x ∈ R : xa = 0, ∀a ∈ S}, S ⊥ = {x ∈ R : ax = 0, ∀a ∈ S}.
For sets containing a single element, the notation is simplified ⊥ {a} := ⊥ a.

Lemma 3. Let P, S ⊆ R, then ⊥ S is a left ideal, S ⊥ is a right ideal and

⊥ P ∩ ⊥ S = ⊥ (P ∪ S).
Definitions below are given for left modules, the mirrored definitions can be given for right modules. Definition 4. [START_REF] Veldkamp | Geometry over rings[END_REF] Let R be a ring with unity, and 2 R be a left module over R, and let aR + bR = {ax + by : x, y ∈ R}.

(

) (a, b) ∈ 2 R is unimodular if aR + bR = R. 1
Note that aR and bR are principal right ideals of R. The following Lemma provides an alternate definition of unimodular. Lemma 5. [START_REF] Veldkamp | Geometry over rings[END_REF] Let R be a ring with unity, and 2 R be a left module over R. (a, b) ∈ 2 R is unimodular if and only if there exists x, y ∈ R such that ax + by = 1. If (αa, αb) = (0, 0) only when α = 0, then R(a, b) is a free cyclic submodule.

Reworking the definition of a free cyclic submodule using annihilators leads to the obvious lemma:

Lemma 7. Let R be a finite associative ring with unity. R(a, b) is a free cyclic submodule of 2 R if and only if ⊥ a ∩ ⊥ b = {0}. ( 2
)
Proof. Let (a, b) be the generating vector, then by definition R(a, b) is free if α(a, b) = (0, 0) only if α = 0. This is equivalent to equation (2). Unimodular vectors have other useful properties [START_REF] Veldkamp | Geometry over rings[END_REF], and for many rings all free cyclic submodules are generated by unimodular vectors. However this is not always the case. Corollaries 21 and 24 show two classes of rings for which all free cyclic submodules are generated by unimodular vectors. The ring of ternions [START_REF] Havlicek | Vectors, cyclic submodules and projective spaces linked with ternions[END_REF] is an example where some free cyclic submodules are generated by non-unimodular vectors. Definition 9. An outlier is a vector which is not contained in any free cyclic submodule generated by a unimodular vector.

The aim of this research is to get some insight into which rings contain outliers, and, more specifically, which rings contain outliers that generate free cyclic submodules. This question is of interest for general n R, but we only treat the simplified case of 2 R where R is a finite associative ring.

Results

Unimodular vectors

We begin by collecting some important facts about unimodular vectors.

If a ∈ R * , then aR = R, hence for all b ∈ R, aR + bR = R. Thus any vector containing a unit as an entry is a unimodular vector. Unimodular vectors may be divided into two types:

• Type I: vectors which contain at least one entry which is a unit;

• Type II: vectors which contain no entries that are units.

Theorem 10. Let R be a finite associative ring with unity. If a, b ∈ R \ R * , then (a, b) is a unimodular vector in 2 R if and only if there exist maximal right ideals, I 1 , I 2 , such that a ∈ I 1 \ I 2 and b ∈ I 2 \ I 1 . Proof. ⇒ Assume (a, b) is unimodular. Since a, b ∈ R \ R * ,
aR and bR are right ideals strictly contained in R. If there is some proper right ideal, I, that contains a and b, then aR + bR ⊆ I ⊂ R. Hence, if (a, b) is unimodular, then a and b cannot be contained in the same maximal ideal.

⇐ Assume a ∈ I 1 \ I 2 and b ∈ I 2 \ I 1 , then aR and bR are right ideals for which aR ⊂ I 1 and bR ⊂ I 2 . aR+bR is a right ideal not contained in either I 1 or I 2 . Therefore aR+bR must be contained in a right ideal that contains both I 1 and I 2 . Since I 1 and I 2 are maximal, the only right ideal containing them both is R. Hence aR + bR = R, and (a, b) is a unimodular vector of 2 R.

All type II unimodular vectors of 2 R conform to the conditions of Theorem 10.

Theorem 11. Let R be a finite associative ring with unity. a, b, α ∈ R.

1. R(αa, αb) ⊆ R(a, b). 2. R(αa, αb) = R(a, b) if and only if α ∈ R * . 3. If (a, b) is a unimodular vector in 2 R, then (αa, αb) is also unimodular if and only if α ∈ R * .
Proof. 1, 2. Let R be a finite associative ring with unity. Then R(αa, αb

) ⊆ R(a, b). If α ∈ R * , then R(αa, αb) = R(a, b). 3. [14, Prop 2.1].
Theorems 10 and 11 give criteria for checking for unimodular vectors of 2 R. More difficult is finding outliers.

Outliers

In the light of Theorem 11 we can refine our notion of outlier. If R is commutative then (a, b) is an outlier of the left module exactly when (a, b) T is an outlier of the right module. In a non-commutative ring, the set of left outliers may be different to the set of right outliers (the smallest example is the ring of ternions of order 8 [START_REF] Havlicek | Vectors, cyclic submodules and projective spaces linked with ternions[END_REF]). The set of outliers is dependent on the structure of the ideals of the ring. If the left and right ideals of a ring have different structures, then a left outlier may be right unimodular.

C = {c} + α ⊥ and D = {d} + α ⊥ , (3)
From Theorems 10 and 13 we get that:

Lemma 14. If a and b are in some right ideal which is non principal, not both in any principal right ideal, and not both in the same maximal left ideal, then (a, b) is an outlier and (a, b) T is unimodular.

Free cyclic submodules and outliers

We have established that the structure of the ideals of a ring determines the set of outliers and unimodular vectors. The Jacobson radical is an important ideal and of crucial importance in the study of unimodular vectors.

Definition 15. [12, §4] For a finite ring R, the Jacobson radical, rad(R), may be equivalently defined as:

• the intersection of all the maximal left ideals of R;

• the largest left ideal J such that 1 + j ∈ R * for all j ∈ J.

Note that the Jacobson radical is a left and right ideal.

Definition 16. [12, Defi 4.9] A one-sided or two-sided ideal, I, is nilpotent of nilpotency m if a 1 .a 2 . . . a m = 0 for any set of elements a 1 , a 2 , . . . , a m ∈ I.

Lemma 17. [START_REF] Lam | A First Course in Noncommutative Rings[END_REF]Thm 4.12] Let R be a finite associative ring. Then rad(R) is nilpotent.

Theorem 18. Let R be a finite associative ring. Let J ≡ rad(R). Then no vector from n J generates a free cyclic submodule.

Proof. From Lemma 17 it readily follows that J has nilpotency m for some m ∈ N. Let (a 1 , a 2 , . . . , a n ) ∈ n J, x 1 , x 2 , . . . , x m-1 ∈ J and α = x 1 .x 2 . . . x m-1 . Then (αa 1 , αa 2 , . . . , αa n ) = (0, 0, . . . , 0). Hence R(a 1 , a 2 , . . . , a n ) is not a free cyclic submodule.

Definition 19. [12, §19]

A local ring is an associative ring that has exactly one maximal left (and also right) ideal.

As a side note we mention that geometries over local rings are called Hjelmslev geometries [5, §9], and have applications in coding theory [START_REF] Honold | Linear codes over finite chain rings and projective Hjelmslev geometries[END_REF].

Theorem 20. Let R be a local ring.

1. No outliers of 2 R generate free cyclic submodules.

(a, b

) is an outlier of 2 R if and only if a ∈ bR and b ∈ aR.

Proof. 1. R has exactly one maximal ideal, which is therefore the Jacobson radical, J. All ring elements not belonging to J are units. Hence any outlier of 2 R has both entries as elements of J. Theorem 18 shows that no vectors with both entries from J can generate a free cyclic submodule.

2. J, the unique maximal ideal of R, cannot generate R. By Theorem 10, no unimodular vector of 2 R can contain elements of the same maximal ideal. Since every element of R is either a unit or an element of J, all unimodular vectors have a unit entry; all unimodular vectors are of type I. So, the outliers of 2 R are those vectors which are not contained in a free cyclic submodule of 2 R generated by (1, x) or (x, 1), x ∈ R. A vector which is not an outlier is of the form This is a class of rings for which all free cyclic submodules are generated by unimodular vectors (the reverse of Lemma 8). In particular, this means that Hjelmslev geometries (which are geometries over a local ring) cannot have non-unimodular points.

Next we look at another property of ideals which precludes the existence of non-unimodular free cyclic submodules. By the same logic

⊥ b ⊇ ⊥ α. Hence ⊥ a ∩ ⊥ b ⊇ ⊥ α = {0}.
Lemma 22 then gives the following important result.

Theorem 23. Let R be a finite associative ring with unity. If every right ideal is a principal ideal, then there are no free cyclic submodules of 2 R generated by non-unimodular vectors.

This shows that a necessary condition for the existence of non-unimodular free cyclic submodules of 2 R is the presence of non-principal right ideals.

Corollary 24. Let R be a principal ideal ring, then R(a, b) is a free cyclic submodule if and only if (a, b) is unimodular. This is another class of rings (see Corollary 21) for which all free cyclic submodules are generated by unimodular vectors.

When using associative rings, free cyclic submodules are generated by either unimodular vectors or outliers. If the assumption of associativity is removed, then this is no longer true. Lemma 25. Let R be a finite ring with unity and let (a, b) be a unimodular vector in 2 R. If there exists α such that (αa, αb) is a non-unimodular vector and R(αa, αb) is a free cyclic submodule of 2 R, then R is non-associative.

Proof. Assume that R is associative. Then, by Theorem

3, if (αa, αb) is non-unimodular, then α ∈ R \ R * . If R(αa, αb) is free, then R(αa, αb) = R(a, b). Thus there exists β ∈ R such that (βαa, βαb) = (a, b),
under the assumption that R is associative, this requires that βα = 1, contradicting that α ∈ R \ R * . Hence if there exists α such that (αa, αb) is a non-unimodular vector and R(αa, αb) is a free cyclic submodule, then R is non-associative.

Examples have been calculated of non-associative rings of order 8, where (a, b) is unimodular, R(αa, αb) is free and R(αa, αb) ⊆ R(a, b).

Conclusion and Further Directions

For the existence of FCSs of 2 R that are generated by non-unimodular vectors ("nonunimodular FCSs"), R must have at least two maximal right ideals, at least one of which is non-principal. This is a necessary condition. Calculated examples [START_REF] Saniga | Projective lines over finite rings, an invited Kempner colloquium given at the Department of Mathematics[END_REF] show that this condition is not sufficient; other properties of a ring are required to guarantee the presence of FCSs generated by non-unimodular vectors.

As already mentioned in the introduction, in our worked examples [START_REF] Saniga | Projective lines over finite rings, an invited Kempner colloquium given at the Department of Mathematics[END_REF] non-unimodular FCSs have been only found for non-commutative rings. One would be tempted to conjecture that non-commutativity is essential in this respect. Yet, this is questionable because some rings feature non-unimodular FCSs in 2 R, but not in R 2 (and vice versa). Hence, it is highly desirable to clarify to what extent the existence of non-unimodular FCSs depends on the non-commutativity of the ring; in particular, what is the smallest commutative ring featuring non-unimodular FCSs?

Further, in all analysed examples, a non-unimodular FCS was found to share with any other FCS at least one vector apart from (0, 0); is this true in general, or just a feature of the particular small-order rings? Finally, within our bank of examples, we found rings where all outliers generate FCSs (like the smallest ring of ternions [START_REF] Havlicek | Vectors, cyclic submodules and projective spaces linked with ternions[END_REF]), as well as rings where only some outliers have this property. What distinguishes the two kinds of rings? These are exciting open questions we would like to focus on in the near future.

Definition 6 .

 6 R(a, b) is a cyclic subset of 2 R generated by (a, b): R(a, b) = {(αa, αb) : α ∈ R}.

Lemma 8 . [ 5 ,

 85 §1] Let (a, b) be a unimodular vector in 2 R, then R(a, b) is a free cyclic submodule.

Definition 12 .

 12 Let R be a finite associative ring with unity. (a, b) is an outlier of 2 R if there does not exist α, c, d ∈ R such that (a, b) = (αc, αd) and (c, d) is unimodular. Theorem 13. Let R be a finite associative ring with unity. (a, b) is an outlier of 2 R if and only if there exists a right ideal I ⊆ R, such that a, b ∈ I and 1. there are no principal right ideals which contain both a and b; 2. for all principal right ideals αR such that a, b ∈ αR, then aR + bR ⊂ αR. Proof. ⇒ Theorem 10 shows that if (a, b) is an outlier of 2 R then a and b are contained in some maximal right ideal. Either a, b ∈ αR for some α ∈ R \ R * (showing part 2) or there exists α, c, d such that (αc, αd) = (a, b) only if (c, d) is not unimodular. Assume that there exists (αc, αd) = (a, b) with (c, d) not unimodular. Let C = {c : αc = a} and D = {d : αd = b}. If αx = αy with x = y, then α(xy) = 0, thus (xy) ∈ α ⊥ . Since,

  one gets aR + bR = αcR + αdR = α(cR + dR + α ⊥ ). Thus aR + bR = αR if and only if there exists c ∈ C and d ∈ D such that cR + dR + α ⊥ = R. let CR = {cr : c ∈ C, r ∈ R} and DR = {dr : d ∈ D, r ∈ R}. Since we can choose any c ∈ C and d ∈ D, we require that CR + DR + α ⊥ = R. From equation (3) it follows: CR + DR + α ⊥ = CR + DR. If CR + DR = R, then there exists c ∈ C and d ∈ D and x, y ∈ R such that cx + dy = 1, implying that (c, d) is a unimodular vector. This contradicts that (a, b) is an outlier, and hence we find that aR + bR ⊂ αR (showing part 1). ⇐ 1. If all right ideals that contain a and b are non-principal, then there does not exist α ∈ R \ R * such that a, b ∈ αR. Hence (a, b) is an outlier of 2 R. 2. Let αR be a principal right ideal for which a, b ∈ αR. Then there exists c, d such that αc = a and αd = b. If aR + bR ⊂ αR, then (αc)R + (αd)R ⊂ αR, α(cR + dR) ⊂ αR, cR + dR ⊂ R, and (c, d) is not unimodular. This holds for all principal right ideals containing a and b; hence (a, b) is an outlier.

  (a, ax) or (ax, a), for some a, x ∈ R. Thus outliers are those vectors which do not fit this form. If (a, b) is contained in a free cyclic submodule then there exists x ∈ R, such that ax = b or bx = a. Hence b ∈ aR or a ∈ bR. If a ∈ bR and b ∈ aR, then (a, b) is an outlier. Corollary 21. If R is a finite local ring, then R(a, b) is a free cyclic submodule if and only if (a, b) is unimodular.

Lemma 22 .

 22 Let R be a finite associative ring with unity. Let a, b be elements of the same principal proper right ideal, αR, then R(a, b) is not a free cyclic submodule of 2 R. Proof. a = αc and b = αd. Then ⊥ a = {x : xa = 0} = {x : xαc = 0} ⊇ {x : xα = 0} = ⊥ α.

Acknowledgement

The authors wish to thank Andrea Blunk and Asha Rao for comments on early drafts. JLH gratefully acknowledges the support from the National Scholarship Programme of the Slovak Republic. This work was also partially supported by the VEGA grant agency projects 2/0092/09 and 2/0098/10.


Ferdi Grootenboers
email: fgrootenboers@gmail.com

Mathijs De Weerdt
email: m.m.deweerdt@tudelft.nl

Mahdi Zargayouna
email: zargayouna@inrets.fr

Impact of Competition on Quality of Service in Demand Responsive Transit

Keywords: Dial-a-ride, multi-company, quality of service, auction

Demand responsive transportation has the potential to provide efficient public door-to-door transport with a high quality. In currently implemented systems in the Netherlands, however, we observe a decrease in the quality of service (QoS), expressed in longer travel times for the customers. Currently, generally one transport company is responsible for transporting all customers located in a specified geographic zone. In general it is known that when multiple companies compete on costs, the price for customers decreases. In this paper, we investigate whether a similar result can be achieved when competing on quality instead. To arrive at some first conclusions, we set up a multiagent environment to simulate the assignment of rides to companies through an auction on QoS, and the insertion of allocated rides in the companies' schedules using online optimization. Our results reveal that this set-up improves the quality of the service offered to the customers at moderately higher costs.

Introduction

Demand-Responsive Transit (DRT) services are a form of transport that is a compromise between public transportation and individual taxis. The principle of these systems is to define the itineraries and schedules of the vehicles based on the requests of the users. Customers are thus provided with relatively cheap doorto-door transportation insofar as they accept to share their ride with others and tolerate a certain detour from their direct trip. The main problem with current DRT services as organized in the Netherlands is that the quality of service (QoS) cannot be guaranteed over longer periods of time. A strong competition for the right to serve for a period of usually three years promises a reasonable quality at a low price, but has the effect that a company that is too optimistic in the contracting phase receives the assignment, but subsequently cannot meet the quality objectives without incurring serious losses. Heavily penalizing such a company for a low QoS will soon lead to bankruptcy, and therefore an even lower QoS until a new company has been found.

© Springer

Source Lecture Notes in Computer Science, 2010, vol. 6251 QoS is usually not specifically addressed in the allocation of rides. The minimization of company's costs is treated as a primary objective, while imposing a minimal QoS [START_REF] Cordeau | A branch-and-cut algorithm for the dial-a-ride problem[END_REF]. The idea put forward in this paper is to let companies compete on QoS on a day to day basis given a price per kilometer that is fixed in advance. Given known results that competition can reduce the total costs, the question is can we use it to improve the QoS instead, and at what costs? Here we divert from research on using auctions and other price-based mechanisms for task allocation in that not the company with the lowest price receives the task, but the company that guarantees the highest QoS. Our main hypothesis is that this approach significantly increases the QoS without much additional costs.

To test our hypothesis, we implement the proposed approach in a multiagent environment (see Section 3), simulate series of requests, simulate the bidding and scheduling process of the companies (in Section 4), and compute the resulting costs and QoS in Section 5. We compare these results to a single-company setting where the company optimizes costs with and without a guaranteed QoS level.

Background

DRT services are usually modeled as a Dial-a-Ride Problem with Time Windows (DARPTW), an extension of the Vehicle Routing Problem. A DARPTW is defined by a set of customers and a fleet of vehicles. Each customer desires to be transported from an origin location to a destination. Customers can impose a time window which includes the earliest possible time and the latest possible time they can be either picked up or delivered. The dynamic DARPTW (D-DARPTW) is NP-hard, which can be proven by a translation from the Traveling Salesman Problem (TSP) [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. The problem can be solved exactly by modeling it as a Mixed Integer Program (MIP) [START_REF] Ropke | Models and branch-and-cut algorithms for pickup and delivery problems with time windows[END_REF], or by applying heuristics [START_REF] Jaw | A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows[END_REF]. The disadvantage of using exact algorithms in a dynamic environment is that these algorithms take too much computation time. The disadvantage of using heuristics is that in some cases the solutions are significantly far from the optimal solution.

In a technique called on-line optimization the optimal solution is searched for with exact algorithms, but only taking into account that part of the problem that is relevant for the moment [START_REF] Mahr | Can agents measure up? a comparative study of an agent-based and on-line optimization approach for a drayage problem with uncertainty[END_REF]. For instance, when searching for the best departure times of the locations of a request to insert into a current schedule, only that part of the current schedule that can be influenced by inserting the new request needs to be considered in the solution process. This results in smaller problems as input for exact algorithms, which implies less computation time. In our simulations of the multi-company environment we apply this online optimization for the insertion of a ride into the schedule of one of the companies.

The Multi-Company DARPTW

In this section, we define a DARPTW where multiple companies compete for requests. The general principle is that the companies announce an offer to the customer, who chooses the company that will serve its request. Conditioned on some negotiated constraints, the winning company can then insert the request into its schedule.

Problem Definition

The DARPTW can be represented by a directed graph of locations and rides between these locations, G = (L, R). The set of locations L contains two vehicle depots for each company, that serve as start and end vertex of all vehicles (denoted by 0 and 2n + 1), n pickup locations P = {1, . . . , n}, and n delivery locations D = {n + 1, . . . , 2n}. This implies that L = {0, 2n + 1} ∪ P ∪ D.

A request is a combination of a pickup location i ∈ P and a delivery location n + i ∈ D. Time windows are associated with a location i as [s i , e i ], with s i the earliest possible time the request can be served at that location (either pickup or delivery), and e i the latest possible time the request can be served. Each location i has an associated load q i , which denotes the number of passengers that are to be pickup up or delivered at that location. We define q 0 = q 2n+1 = 0, q ≥ 0 for i = 1, . . . , n, and q i = -q i-n for i = n + 1, . . . , 2n. Each company has a set of vehicles denoted by K, and with each vehicle k ∈ K a maximal capacity Q k and a maximal route duration T k are associated. The cost of a ride from location i to j with vehicle k is denoted by c k ij , and the travel time of a ride between i and j is denoted by t ij . To account for service time at locations (i.e. time to get in and out the vehicle), we associate with every location i a service duration d i ≥ 0 and d 0 = d 2n+1 = 0.

Mechanism Overview

A customer announces its request to the center, and this is forwarded to all known companies. Once a company receives a new request, it checks whether it is possible to insert it into one of its vehicle schedules. If it is not possible to insert the request into one of the company's vehicle schedules, the company will not place a bid in the current auction. Otherwise, a bid value is calculated for this request. When the center has received all bids, it determines the best one (the highest QoS) and sets the conditions that have to be met by the winning company in serving the request. The winning company is informed of the determined conditions, and all other companies are sent a message that they have not won the auction. The winning company then inserts the request into the schedule of one of its vehicles. We assume there is always the possibility to have the request served by a taxi company outside the system at a (usually high) so-called reservation price. This is done when no bid is offered below this reservation price. The following subsections detail the elements of this process, starting with the computation of the QoS calculation.

Bidding Service Quality

Usually, the additional costs needed to serve a request is used as a bid [START_REF] Mes | Sequential Auctions for Full Truckload Allocation[END_REF], and to minimize overall costs, the request is assigned to the vehicle that has announced the bid with the lowest additional costs. In our work, we let the companies compete on the QoS for an incoming request. Therefore, the bid value in our setting contains the QoS that a company promises to provide. We define QoS as the ratio of the actual ride time to the direct ride time. For instance, when the time to travel from A to B directly (i.e. with no detours) is equal to 5 minutes, and the vehicle drives from A to B via C, in 7 minutes, then the QoS is 5 7 . For customers, this measure emphasizes one of their biggest complaints, namely large detours. For companies, this ratio is a measure of how efficiently different rides are combined.

A vehicle's route is modeled by a sequence of locations i with associated service times d i and departure times t i . Furthermore let the minimal time needed to drive from location i to location j be denoted by t ij . The QoS for a request with pickup location i and delivery location j can then be calculated as follows:

QoS ij = t ij + d i + d j t j -t i (1)

Auction on QoS and Pre-determined Payments

The mechanism that we propose is based on a reversed sealed-bid second-price auction, using QoS instead of prices. In such an auction, each bid is private to the company that submits it, and the winner of the auction has to meet the details of the second-highest bid value. The auction is reversed, because there are multiple sellers (the companies) and a single buyer (the customer). This single buyer announces the details of its request, and then the companies can determine a bid value. The winning company is the company that announces the highest QoS, and if multiple companies announce the same highest bid, one of these companies is arbitrarily selected as winner. The request that has been auctioned is allocated to the winning company, which then has to serve the request with the amount promised by the second-highest bidder.

In our setting, the payment for the service is not defined by the auction, but must be set on forehand. We set the payment equal to a price per kilometer C km multiplied by the direct distance between the pickup and the delivery location of the customer's request. The profit of a company is then defined as the total income a company receives from serving requests minus the total costs needed to serve these requests. Clearly, C km essentially determines the income of the companies.

Let for each request (i, j) ∈ R the direct distance t ij be given. For this problem, we define solutions for two hypothetical situations with complete knowledge of the requests during the day (in advance). We let OP T (R) denote the transportation costs when all rides are optimally combined (in hindsight), and OP T 1.0 (R) denote the transportation costs when each request is served with a QoS of 1.0. Proposition 1. If an auction on QoS is used for multiple companies, and the (fixed) price per kilometer C km is below OP T (R) (i,j)∈R ti,j few people will be transported. If C km is above OP T 1.0 (R) (i,j)∈R ti,j , everyone will be transported separately.

Proof. The lower bound for C km is the minimal total costs needed to serve all requests divided by the total direct distance traveled by all customers. When C km is set below this value, companies have more costs than income, except when a ride largely overlaps with an existing ride (which is never the case when the schedule is still empty). Companies will thus not bid in the auction. Therefore few people will be transported. On the other hand, when C km is set above the average cost of transporting everyone separately, every company makes a net profit for each customer. Therefore, every company will bid a QoS of 1.0 for every request, because it then has the highest chance to win the auction. Since this holds for all companies, all requests have to be served with QoS 1.0.

Computations for the Companies

The computations of the transport companies are based on online optimization for the insertion of rides, and for bid determination use a look-ahead on possible future requests via a Monte Carlo simulation in combination with an insertion heuristic. Both approaches are detailed below.

Online Optimization

Every company has to solve a DARPTW problem to find the set of routes for their vehicles. We define a planning horizon H, which is the time period for which the routes are planned. A solution for one company is represented as follows. Let u k i be the time at which vehicle k starts servicing at a location i, w k i the load of vehicle k upon leaving location i, and r k i the ride time of a customer that places the request to travel from i to n + i. In the model that follows, x k ij is equal to 1 if and only if a ride from location i to j is allocated to vehicle k.

In Figure 1 the entire model is given, in which the objective function is to minimize total routing costs (see Equation 2). Constraint 3 ensures that all requests are served only once and Constraint 4 ensures that every vehicle will once drive to the start and end depot. Together with 5 and 6 this guarantees that every request is served once by the same vehicle and that each vehicle starts and ends its route at a depot. Constraint 7 states that the arrival time at a location must be higher or equal to the start time of servicing at the starting location, plus the service duration at that location, plus the time of the ride from start to end location. It is also obvious that the load of a vehicle at the end location of a ride is higher than or equals the load of that vehicle at the start location (Constraint 8).

The travel time of a user is higher than or equals the time the vehicle is at his delivery location minus the time he picked up the user and minus the duration of servicing at the pickup location; this is ensured by Constraint 9. Constraint 10 states that the duration of a vehicle to drive from the start depot to the end depot must be less than or equal to the total route duration specified for that vehicle, while Constraint 11 ensures that every location is visited within the specified time horizon. The ride time of a passenger is specified to be at least as

Minimize k∈K i∈L j∈L c k ij x k ij (2)
subject to k∈K j∈L big as the time of a direct ride between its pickup and delivery location and at most as big as the planning horizon (Constraint 12). The load of a vehicle can never be higher than the highest possible load specified. Note that the load of a vehicle increases at a pickup location and decreases at a delivery location, so we can state Constraint 13. The last constraint ensures that we deal with binary variables, so that a variable denotes whether a ride is allocated to a vehicle or not, and we cannot specify that half of that ride is allocated to another vehicle.

x k ij = 1 (i ∈ P ), (3)
i∈L x k 0i = i∈L x k i,2n+1 = 1 (k ∈ K), (4)
j∈L x k ij - j∈L x k n+i,j = 0 (i ∈ P, k ∈ K), (5)
j∈L x k ji - j∈L x k ij = 0 (i ∈ P ∪ D, k ∈ K), (6)
u k j ≥ (u k i + di + tij)x k ij (i, j ∈ L, k ∈ K), (7)
w k j ≥ (w k i + qj)x k ij (i, j ∈ L, k ∈ K), (8)
r k i ≥ u k n+i -(u k i + di) (i ∈ P, k ∈ K), (9)
u k 2n+1 -u k 0 ≤ T k (k ∈ K), ( 10
) si ≤ u k i ≤ ei (i ∈ L, k ∈ K), (11) ti
,n+i ≤ r k i ≤ H (i ∈ P, k ∈ K), (12) max{0
, qi} ≤ w k i ≤ min{Q k , Q k + qi} (i ∈ L, k ∈ K), (13)
x k ij = 0 or 1 (i, j ∈ L, k ∈ K). (14)
For the insertion of requests by a company, we use the mathematical model that we have just defined. This formulation evolves over time ignoring (previously inserted and) serviced requests.

Bid Calculation

To check whether an incoming request can be inserted, we use the insertion heuristics developed by Jaw et al. [START_REF] Jaw | A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows[END_REF] and Solomon [7]. This is done before a bid value is calculated, and can save expensive computation time. If the request is feasible, the company can propose a bid to the customer.

A company wants to maximize its profit, defined as income minus costs. The company can gain income by serving requests (winning auctions) and it can decrease costs by combining requests. Combining requests often leads to a lower QoS (because there are less direct rides), which can lead to winning less auctions. Promising a higher QoS results in a higher probability to win the auction, but decreases the flexibility to insert future requests.

There are different costs associated with the different QoS values that a company can bid. In general, a company can bid a low QoS for low internal costs, or a high QoS for higher internal costs. For a single-shot second-price auction, it can be shown that it is optimal to bid the highest price possible. However, this is not the case in our (repeated) auction on quality.

Proposition 2. If each company bids the highest QoS possible, all rides will be transported at QoS of 1.

Proof. When a company bids the highest QoS possible for the first request, this bid will be a QoS of 1, since its vehicles have empty routes so far. When all companies follow this behavior, the second "price" will also be a QoS of 1, so the ride is accepted at a QoS of 1. When a route contains only rides with a QoS of 1, a next ride cannot be combined, so the highest QoS possible will also be 1. With induction, all rides will be transported at a QoS of 1.

To avoid this side effect of using QoS as a bid for the companies, we allow them to incorporate knowledge about future requests in their bid calculation. This way, they reason about the future possible combinations of the current request while bidding the promised QoS, instead of reasoning only about the current request. To incorporate the expected profit of future requests, the companies must have some knowledge about the distribution in time and space of future requests. From this distribution, they can calculate the expected profit for an incoming request, based on future requests that can give the companies possibilities to combine rides and lower costs. To this end, we use a Monte Carlo [START_REF] Metropolis | The monte carlo method[END_REF] simulation in combination with an insertion heuristic.

Estimating expected profit The idea is to estimate the expected profit that a company would make assuming that the current request is inserted into the schedule. To calculate the expected profit, a distribution has to be known on the arrival location and time of future requests. With the help of these distributions, a set of possible future requests can be generated and inserted into the schedule. Once this is done, the total costs needed to insert these requests, and the total income gained by inserting them can be calculated. This expected profit is calculated by using an insertion heuristic based on the works of Jaw et al. [START_REF] Jaw | A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows[END_REF] and Solomon [START_REF] Solomon | Algorithms for the vehicle routing and scheduling with time window constraints[END_REF].

Monte Carlo simulations

The specific set of generated future requests can have a big influence on the calculated expected profit. Therefore, a Monte Carlo simulation [START_REF] Metropolis | The monte carlo method[END_REF] is performed. The above algorithm is repeated a number of times, and the final expected profit is taken as the average expected profit of these repetitions. To obtain the highest QoS level for the current request, taking into account future requests, Monte Carlo simulations are performed for different levels of QoS. The level for which the expected profit is closest to zero is taken as the bid value.

Experiments and Results

The main hypothesis to be tested is the following.

Hypothesis 1 When multiple companies compete on QoS, the average QoS is higher than in a situation with a single company which minimizes costs. Transportation costs are also higher.

But also for a single company we expect that transportation costs are higher when the QoS is higher: Hypothesis 2 A higher required QoS is more expensive (for a single company).

As discussed before, requiring a higher QoS from a single company fails in practice, because in general, a higher QoS is more expensive, and for example penalties are not sufficient to incentivize a company to meet the agreed QoS. Our main thesis is that competition can be used to realize a higher QoS, and we expect that this can be done at approximately the same additional cost as for a single company, leading to a third hypothesis.

Hypothesis 3 When multiple companies compete on QoS, the costs are not significantly higher than in a situation with a single company which minimizes costs with the same average QoS.

Experimental Setup

To test these hypotheses, we run the mechanism and algorithms proposed in the previous section on a set of benchmarks. The size of these benchmark problems is chosen such that each one takes at most about 1 hour computation time to solve. This decision resulted in a set of 100 problem instances, each containing 16 customers, in which the coordinates and the pickup and departure times of the requests are distributed following a uniform distribution. We consider these instance over a planning period of 4 hours. The considered network is a continuous map, defined by a square area of 20 by 20 km with a node on every km. To make the problem instances dynamic, we add to each customer the moment at which it becomes available to the system. This is done by randomly choosing a number in the interval [e i -90, e i -60] (i.e. between 90 and 60 minutes before the earliest pickup or delivery time). We choose these values because we want the instances as dynamic as possible. This means that customers announce their requests quite late, but such that vehicles are able to respond to schedule changes. The maximum capacity for each vehicle is set to 3 passengers. All Service quality versus total costs all served, multiple companies all served, single company (min costs) not all served, multiple companies not all served, single company (min costs) Fig. 2. QoS versus total costs for a multiple company setting and a single company the experiments have been performed in Java and Java Agent DEvelopment Framework (JADE) [START_REF] Bellifemine | JADE -a FIPA-compliant agent framework[END_REF] on an Intel Xeon E5345 2.33GHz with 16 Gb RAM. Each company uses the MIP-solver SCIP to insert assigned requests. SCIP is one of the fastest non-commercial solvers [START_REF] Achterberg | SCIP -a framework to integrate constraint and mixed integer programming[END_REF].

To test the hypotheses, we run the system two times for each problem instance. The first time two companies have two vehicles each and compete on QoS. The second time, there is only a single company, having four vehicles and minimizing costs. In a single-company setting, the company does not have any incentive to bid high QoS, because it knows already that it contractually gets assigned all the requests.

First Experiment

In Figure 2, a plot is given for the comparison of QoS and total costs between a situation with a single and a situation with multiple companies. Two clouds of points can be distinguished. The cloud of points of instances with multiple companies is situated with relative high QoS and high total costs. The other cloud of points has less quality and less total costs and mainly contains instances with a single company. A paired t-test is performed for both average QoS and total costs. The mean difference for QoS is 0.097 with a higher quality in the multicompany setting. The confidence interval is [0.071, 0.122] and the probability that these results are obtained assuming that there is no difference between the two settings is 5.98 × 10 -10 . A t-test gives us a mean difference of 37.5 higher total costs for the multi-company setting with a confidence interval of [25. 3, 49.8], and a p-value of 1.25 × 10 -7 .

In conclusion, we have discovered that total costs are about 13% higher in the multi-company setting than in the single-company setting. The fact that companies in a multi-company setting have the incentive to bid higher service quality instead of minimizing costs, results in a higher average service quality. This follows from the results of the paired t-test showing that the QoS of the multi-company setting is 12% higher. Both differences are (very) significant, confirming Hypothesis 1.

Second Experiment

In the previous experiment, the single company did not take any required level of QoS into account. However, to make a fair comparison of costs (to establish the second hypothesis), we would like to have the same average QoS for the single company as the multiple companies obtain by competition. To arrive at a certain average QoS, we ensure that each ride of the single company has a certain minimal QoS. To determine how to set the required QoS to arrive at such a desired average QoS, we first run the experiments for a single company for a required QoS of {0.00, 0.05, . . . , 1.00}. We then investigate the relation between these required QoS levels and the average QoS, and at the same time the relation between the required QoS levels and the total costs, to test Hypothesis 2.

In Figure 3 (left), it is shown that the average total costs are increasing as from a QoS level of 0.4, with a slight decrease at level 1.0. This last decrease of average total costs can be interpreted by the fact that if the minimal QoS level is 1.0, less requests can be served, which leads to lower total costs. The non-increasing part of the figure (from level 0.0 to 0.4) can be explained by the fact that the levels do not influence the outcome, because even when a single company minimizes costs, it still serves requests with an average QoS of about 0.66. This is also shown in Figure 3 (right), in which we see no increase in QoS at this interval.

Besides these two exceptions, overall there is a strong correlation between total costs and minimal QoS. The correlation coefficient over the complete range 0.93, confirming Hypothesis 2. When we take only the interval from 0.40 to 0.95 Service quality versus total costs all served, multiple companies all served, single company (min level = 0.77) not all served, multiple companies not all served, single company (min level = 0.77) Fig. 4. QoS versus total costs for a multiple company setting and a single company setting in which the single company acts like a company in a multi-company setting.

into account, the correlation coefficient is even 0.99. The minimal QoS level that is needed in order to let the company in the single-company setting serve requests with an equal average QoS as in the multi-company setting is derived by searching in Figure 3 (right) for the corresponding level. The average QoS over all instances in the multi-company setting is 0.93 and when we search for the corresponding minimal QoS level we find a value of 0.77. Subsequently, we run the first experiment again, but now requiring a QoS of 0.77 for the single company. In Figure 4 a scatter plot is shown in which QoS is plotted against total costs, for the multi-company and single-company setting. From this we observe that the costs are somewhat higher in the multi-company setting, but the points in the plot are too close to each other to give a proper judgment about this measure. The paired t-test gives us a mean difference of 23.5 total costs, a 95%-confidence interval of [11.9, 35.0], and a p-value of 1.71 × 10 -4 , with higher total costs in the multi-company setting. Another paired t-test is performed to verify that the difference in average QoS between the two settings is not significant. The results of this test confirm this with a mean difference of 0.0013 (higher in the multi-company setting), and a p-value of 0.92.

We thus conclude that compared to the multi-company setting, the total costs in a single-company setting are less, even if this single company provides equal QoS, rejecting Hypothesis 3.

Discussion

We conclude that if the price per kilometer is fixed within a reasonable range (Proposition 1), and expectations about the future are somehow taken into ac-count (see also Proposition 2), it is indeed possible to obtain a higher QoS in door-to-door transportation by letting multiple companies compete on QoS (Hypothesis 1). However, in our experiments, the costs are about 7% higher than in the idealistic case where a single company always meets a required QoS while minimizing costs.

For future work, we aim to study other definitions of QoS. For instance, we are thinking about taking into account deviations from desired departure/arrival time. We also plan to consider more realistic generation of requests, based on real data. Besides, we plan to define mechanisms where companies compete both on QoS as well as on costs. In addition, we believe better results can be obtained if the mechanism allows for bidding on combinations of requests. Finally, this paper focused mainly on an experimental evaluation of the idea of competing on quality. It would be very interesting to also provide a theoretical analysis. This is particularly challenging, since the mechanism is in fact a sequential auction.

Fig. 1 .

 1 Fig. 1. Mixed Integer Program formulation to allocate requests to vehicles within a company. The objective function minimizes costs.

Fig. 3 .

 3 Fig. 3. Average total costs (left) and QoS (right) for instances with a minimal QoS


-L Bryngelsson

MD Marie Carlsson

C.-M Ekström

MD, PhD Stellan Håkansson

MD, PhD Bo Jacobsson

PhD; Karin Källén

MD Eva Spetz

MD, PhD Margareta Granlund
email: margareta.granlund@climi.umu.se

MD, PhD Pia Axemo

MD, PhD Katarina Bremme

MD, PhD; Anna-Lena Bryngelsson

MD; Carl-Magnus Ekström

MD A-L Bryngelsson

MD M Carlsson Wallin

MD C-M Ekström

MD, PhD I Tessin

Antimicrobial resistance in colonizing Group B Streptococci before implementation of a Swedish intrapartum antibiotic prophylaxis

Keywords: GBS, Antibiotic Susceptibility testing, Swedish parturients GBS, Antibiotic Susceptibility testing, Swedish parturients

Antimicrobial resistance in colonizing group B Streptococci before the implementation of a Swedish intrapartum antibiotic prophylaxis program

The mobile elements GBSi1 and IS1548 is now presented in the Material and methods section, and the results of the characterization of the serotype III isolates in relation to the antibiotic resistance pattern is given in the result section and dicussed in the Discussion part. The penicillin G MIC should be 0,032mg/L, which now is corrected. The gene product of aad-6 is hopefully now better described. Discussion: Section 2; the part about the erronous penicillin E-test is removed. The Tables are rewritten and Figure 1 is omitted.

Reviewer 2.

We have tried to shorten the manuscript and have also made an effort to include data from AST with the EUCAST method on selected isolates. Materials and methods: The part discussing the prevoiusly published material has been extended including the methods for serotyping and MLST. Results: The paragraph on macrolide resistance has been rewritten and in addition to disk diffusion according to EUCAST MICs were determined. Since this gave new results, which showed a high-level of MLS resistance in four serotype V isolates these data are now presented in the result section. In the part regarding screening for penicillin resistance ceftibuten was included together with oxacillin in the disk diffusion made according to EUCAST. That test was made on 24 isolates with oxacillin inhibition zones on ISA-NAD <18,5 mm since ceftibuten disk diffusion results recently has been suggested to have 100% sensitivity and specificity for detection of penicillin resistance in GBS (Kimura et al,ref.25). Figure 1 is omitted, the tables I and II have been rewritten as well as the reference list.

Introduction

Group B streptococci (GBS) are recognized as a common cause of life-threatening infections in neonates. When the mother carries GBS in vagina and/or rectum, generally an asymptomatic condition, the infant is exposed to the bacteria during the passage in the birth canal. In an attempt to prevent GBS infection in neonates, most western countries have introduced programs for intrapartum antibiotic prophylaxis (IAP) [START_REF] Schrag | Group B streptococcal disease in the era of intrapartum antibiotic prophylaxis[END_REF][START_REF] Berardi | Group B streptococcus and preventive strategies in Europe[END_REF]. The use of IAP has drastically reduced neonatal invasive GBS infections during the first week of life [START_REF] Schrag | Group B streptococcal disease in the era of intrapartum antibiotic prophylaxis[END_REF][START_REF] Law | The prevention of neonatal group B streptococcal disease: a report by a working group of the Medical Screening Society[END_REF]. However, the increased use of antibiotics to women in labor has raised concerns about development of antibiotic resistance. For effective treatment and IAP it is important to monitor the prevalence of antibiotic resistance in GBS over time. Intravenous penicillin G is a first-choice drug for IAP and is given either to GBS colonized women or to women considered at risk. For treatment of established infections penicillin or ampicillin is often used in combination with an aminoglycoside as gentamicin [START_REF] Isaacs | Antibiotic use in the neonatal unit[END_REF]. Streptococci are intrinsically resistant to aminoglycosides and not treatable with aminoglycosides given as single therapy. However, the combination of a cell-wall active antibiotic as penicillin or ampicillin and gentamicin has been shown to enhance killing of GBS [START_REF] Baker | Synergism, killing kinetics, and antimicrobial susceptibility of group A and B streptococci[END_REF]. The synergistic effect between beta-lactam antibiotics and aminoglycosides is abolished if the isolate is high-level gentamicin resistant, a resistance mechanism best described in enterococci but also in a few GBS isolates [START_REF] Buu-Hoï | High-level chromosomal gentamicin resistance in Streptococcus agalactiae (group B)[END_REF][START_REF] Liddy | Group B Streptococcus highly resistant to gentamicin[END_REF][START_REF] Lopardo | Argentinian Streptococcus Study Group (2003) Six-month multicenter study on invasive infections due to group B streptococci in Argentina[END_REF][START_REF] Kaufhold | Identical genes confer high-level resistance to gentamicin upon Enterococcus faecalis, Enterococcus faecium, and Streptococcus agalactiae[END_REF]. GBS have long been considered as uniformly penicillin susceptible. Data regarding sporadic reports of isolates with phenotypically reduced susceptibility to penicillin have been difficult to interpret due to methological concerns and differences in recommended susceptibility breakpoints. However, two recent studies have reported alterations in the penicillin binding protein 2X gene (pbp2x) in GBS leading to decreased penicillin susceptibility [START_REF] Kimura | First molecular characterization of group B streptococci with reduced penicillin susceptibility[END_REF][START_REF] Dahesh | Point mutation in the group B streptococcal pbp2x gene conferring decreased susceptibility to beta-lactam antibiotics[END_REF].

The antibiotic most often used for IAP in case of penicillin allergy is clindamycin [START_REF] Schrag | Prevention of perinatal group B streptococcal disease. Revised guidelines from CDC[END_REF]. Macrolides as erythromycin, clarithromycin and azithromycin have also been suggested as an alternative. The resistance rates for the macrolides-lincosamides-streptogramin B (MLS B ) group of antibiotics in GBS exhibit geographic differences and vary over time [START_REF] Andrews | Group B streptococci causing neonatal bloodstream infection: antimicrobial susceptibility and serotyping results from SENTRY centers in the Western Hemisphere[END_REF]14).

During 2005 a Swedish, population-based study of GBS carriage in parturients and infants, and risk factors for colonization, was performed before a regular national IAP program had been implemented [START_REF] Håkansson | Swedish Working Group For The Prevention of Perinatal Group B Streptococcal Infections (2008) Group B streptococcal carriage in Sweden: a national study on risk factors for mother and infant colonisation[END_REF]. Of 1,569 mother/infant pairs examined the vaginal/rectal carriage rate of the mothers was 25,4%.

With phenotypic antibiotic susceptibility tests 5% of these isolates were found resistant to clindamycin and erythromycin. None of the isolates were resistant to penicillin G or showed high-level gentamicin resistance [START_REF] Håkansson | Swedish Working Group For The Prevention of Perinatal Group B Streptococcal Infections (2008) Group B streptococcal carriage in Sweden: a national study on risk factors for mother and infant colonisation[END_REF]. In the present study 396 colonizing GBS were further examined for genetic resistance determinants of clindamycin, erythromycin, kanamycin, streptomycin and tetracycline.

Material and methods

GBS isolates (n= 396), were from a nationwide surveillance study conducted in Sweden during 2005 [START_REF] Håkansson | Swedish Working Group For The Prevention of Perinatal Group B Streptococcal Infections (2008) Group B streptococcal carriage in Sweden: a national study on risk factors for mother and infant colonisation[END_REF]. The isolates were from vagina/rectum from parturient women, and from surface cultures from 44 newborns in whom the cultures from the mothers were negative. Since the surface cultures of the infants were taken immediately after birth, the vaginal samples in these mothers were assumed to be false negative. All GBS isolates were serotyped (types Ia, Ib, II-VIII) by co-agglutination (Essum AB, Umeå, Sweden) In non-typable isolates a PCR-based typing method was used [START_REF] Kong | Serotype identification of group B streptococci by PCR and sequencing[END_REF]. By multilocus sequence typing (MLST) a serotype III lineage, CC17, containing sequence type 17 (ST17), associated with neonatal invasive infections has been identified [START_REF] Luan | Multilocus sequence typing of Swedish invasive group B streptococcus isolates indicates a neonatally associated genetic lineage and capsule switching[END_REF][START_REF] Jones | Multilocus sequence typing system for group B streptococcus[END_REF]. The presence of the mobile genetic elements GBSi1 and IS1548 in serotype III isolates correlate with the phylogenetic lineages of clonal complexes 17 (CC17) and 19 (CC19) respectively [START_REF] Luan | Multilocus sequence typing of Swedish invasive group B streptococcus isolates indicates a neonatally associated genetic lineage and capsule switching[END_REF]. Serotype III isolates of the study were further characterized by PCR for the presence of these mobile genetic elements. The serotypes of mother/infant pair isolates were congruent. The distribution of serotypes among the GBS was as follow: Ia 11%, Ib 13%, II 16%, III 24% (CC19 11%, CC17 11%), IV 15%, V 19%, VI 0.5%, VII 1%, and 0.5% non-typable. No serotype VIII isolates was found [START_REF] Håkansson | Swedish Working Group For The Prevention of Perinatal Group B Streptococcal Infections (2008) Group B streptococcal carriage in Sweden: a national study on risk factors for mother and infant colonisation[END_REF].

Phenotypic antibiotic susceptibility testing

The isolates were cultured on blood agar plates containing Columbia agar base (Acumedia, Svenska Labfab, Ljusne, Sweden) and 5% defibrinated horse blood and were identified as GBS as previously described [START_REF] Luan | Multilocus sequence typing of Swedish invasive group B streptococcus isolates indicates a neonatally associated genetic lineage and capsule switching[END_REF]. Disk diffusion was performed on Iso-Sensitest Agar (ISA) (Oxoid Ltd, Basingstoke, United Kingdom) with 5% defibrinated horse blood and 20 mg/L of nicotinamide adenine dinucleotide (NAD) with a semi-confluent inoculum according to the Swedish Reference Group of Antibiotics (SRGA) (www.srga.org). Twenty-two isolates with MLS B resistance and 24 isolates with oxacillin inhibitions zones less than 18.5 mm on ISA-NAD agar were also tested with the disk diffusion method that during 2010 will be recommended by the European Committee on Antimicrobial Susceptibility Testing (EUCAST) (www.eucast.org). In this method streptococci are tested on Mueller-Hinton agar (MH) supplemented with 5% horse blood and 20 mg/L NAD with a confluent inoculum. Streptococcus pneumoniae ATCC 49619 was used for validation of the susceptibility tests. Screening for penicillin resistance was performed with 1 µg oxacillin disks and with the EUCAST method also with 30 µg ceftibuten disks. Minimum inhibitory concentrations (MICs) were tested with E-tests (AB Biodisk, Solna, Sweden). The plates were incubated for 18 h at 35 o C in 5 % CO 2 . To identify isolates with inducible MLS B resistance (iMLS B ) the double-disk diffusion test with an erythromycin disk and a clindamycin disk, both of 15 μg, placed 25 mm apart was used. Flattening of the clindamycin growth inhibition zone indicate iMLS B . To screen for high-level aminoglycosideresistance disks prepared with 1000 μg kanamycin and streptomycin respectively was used [START_REF] Lopardo | Argentinian Streptococcus Study Group (2003) Six-month multicenter study on invasive infections due to group B streptococci in Argentina[END_REF].

PCR amplification of resistance genes The occurrence of the tetracycline resistance genes tet(O)

and tet(M), the MLS B resistance genes erm(B), erm(A/TR) and mef(A), and the genes aad-6 and aphA-3 encoding aminoglycoside-modifying enzymes were determined with PCR according to Poyart et al [START_REF] Poyart | Genetic basis of antibiotic resistance in Streptococcus agalactiae strains isolated in a French hospital[END_REF]. The aad-6 gene is also known as ant-6, and is coding for a streptomycin adenylyltransferase. DNA was extracted by the guanidium thiocyanate metod [START_REF] Boom | Rapid and simple method for purification of nucleic acids[END_REF] for the PCR reactions with the aad-6 and aphA-3 primers, for the other reactions the samples were boiled in water for 10 min. The PCR mixtures of 50 μl contained 0,2 μM forward and reverse primers (DNA Technology A/S, Århus, Denmark), 1U of AmpliTaq Gold (Applied Biosystems, Stockholm, Sweden), 0.2 mM of each deoxynucleoside triphosphate (Amersham Biosciences, Buckinghamshire, UK), 1.5 mM MgCl 2 , and 100 ng of template DNA in PCR buffer II with bovine serum albumin (Applied Biosystems). DNA amplification was carried out by initial denaturation at 95°C for 10 min and then cycling at 95°C for 1 min, 60°C for 30s, and 72°C for 30s for 35 cycles, with a final incubation at 72°C for 5 min in a DNA Engine PTC-200 (MJ Research Inc., Watertown. Mass. USA). The amplicons were visualized by UV transillumination of ethidium bromide stained 1.75% agarose gels. PCR products were sequenced with the BigDye terminator cycle sequencing ready reaction kit (PE Applied Biosystems) on an ABI 377 (ABI prism sequencer, Applied Biosystems).

Results

Phenotypic tetracycline resistance was identified in 313 isolates (79%). Every forth of these isolates were tested for the presence of tetO and tetM by PCR. In 89 of 94 isolates (94.7%) tetM was found and in 3 of 94 (3%) tetO. Neither tetO nor tetM could be identified in two of 94 isolates (2%). MLS B resistance was detected in 22 of the 396 isolates (5, 5%). According to the breakpoints for erythromycin from SRGA beta-haemolytic streptococci with growth-inhibition zones of ≥ 23 mm are interpreted as susceptible and isolates with zones ≤ 19 mm as resistant. Nineteen GBS met the criteria for intermediate susceptibility or resistance with disk diffusion on ISA-NAD agar and had erythromycin MICs ≥ 1 mg/L indicating resistance (Table I). No cut-off values for the disk diffusion have been determined by EUCAST, but with the use of the EUCAST method those 19 GBS had erythromycin inhibition zones < 18 mm. In seven of these isolates a flattened clindamycin inhibition zone indicated iMLS B . The erm (A/TR) gene was amplified in all iMLS B isolates and in three additional isolates, which lacked clindamycin inhibition zones. The ermB gene was identified in nine isolates (Table I). GBS with MLS B resistance caused by an active efflux mediated by mef genes have been described. The Mphenotypes of such isolates, are erythromycin resistant and clindamycin susceptible without flattening of the clindamycin inhibition zone in the double diffusion test [START_REF] Arpin | Presence of mefA and mefE genes in Streptococcus agalactiae[END_REF]. The mef(A) gene could not be identified in any of the isolates of this study, which is in agreement with a lack of isolates with the M-phenotype.

Neither erm (A/TR), ermB nor the mef(A gene could be identified in three isolates that were susceptible to erythromycin but with clindamycin inhibition zones 1.5 -0.5 mm below the present breakpoint for resistance set at 24mm. The clindamycin MIC was 2 mg/L, which indicated resistance, while the erythromycin MICs were low (Table I). Seven of the 64 serotype II isolates (11%), five of 76 serotype V isolates (7%) and six of 92 serotype III isolates (6,5%) exhibited MLS B resistance but only single isolates of serotype Ia, Ib and IV. Four serotype V isolates harboring ermB, isolated from women from four different cities in Sweden, were the only isolates with MICs > 256 mg/L for both erythromycin and clindamycin. Tetracycline resistance was found in 89% of the 44 serotype III isolates that harbored the GBSi1 intron, corresponding to CC17 [START_REF] Luan | Multilocus sequence typing of Swedish invasive group B streptococcus isolates indicates a neonatally associated genetic lineage and capsule switching[END_REF], but none of these isolates were erythromycin or clindamycin resistant.

All GBS had penicillin MICs ≤ 0.064 mg/L [START_REF] Håkansson | Swedish Working Group For The Prevention of Perinatal Group B Streptococcal Infections (2008) Group B streptococcal carriage in Sweden: a national study on risk factors for mother and infant colonisation[END_REF]. The distribution of the inhibition zones from the screening of penicillin resistance with 1µg oxacillin disks suggested that all the isolates could belong to the wild type population (Table II). However, three GBS isolates gave inhibition zones ≤17 mm, the breakpoint set by SRGA to guard for penicillin resistance in beta-haemolytic streptococci. The oxacillin MIC 90 for the GBS isolates of the study was 1 mg/L. The three isolates with oxacillin inhibitory zones repeatedly less than 17 mm (range 16.2-16.9 mm) were further tested and showed the following MICs: oxacillin 1 mg/L, penicillin G 0,032-0,064mg/L, ampicillin 0,064-0,125mg/L, cefuroxime 0,064mg/L, cefotaxime 0,064-0,125mg/L, imipenem 0,032-0.125 mg/L and cefoxitin 2-4 mg/L. The identity of these isolates as GBS was confirmed with API-Strep (bioMériuex AB, Askim, Sweden). When tested with the EUCAST method the inhibition zone ranges of the three isolates were 15,7-18,5 mm and 16,2-19,2 mm for oxacillin and ceftibuten respectively, in agreement with results of the other isolates tested (Table II).

In 28 isolates with inhibitory zones for gentamicin of ≤ 8 mm the MICs ranged between 24-96 mg/L; i.e.

32 -128 mg/l when the results are rounded up to the next highest twofold dilution, indicating that none of the isolates had high-level gentamicin resistance ( www.srga.org). One of these 28 isolates, which had a gentamicin MIC of 64 mg/L, lacked an inhibition zone around the 1000 μg kanamycin disk and harboured the aphA-3 gene. Four additional isolates, with gentamicin inhibition zones > 8 mm, lacked inhibition zones around the highly loaded kanamycin disk and three of these also lacked inhibition zones around the 1000 μg streptomycin disk (Fig 1). The kanamycin phosphorylase gene aphA-3 was present in all of the kanamycin resistant isolates. In addition the aad-6 gene, encoding a nucleotidyltransferase that adenylylate streptomycin, was identified in the three streptomycin resistant isolates. The kanamycin phosphorylas mediate resistance against amikacin as well and accordingly the amikacin MICs in all of the kanamycin resistant isolates were >256mg/L. No zone around the 1000 μg kanamycin disk is indicative for resistance. None of 20 isolates with kanamycin inhibition diameters ranging from 12 to 15 mm harboured the aphA-3 or aad-6 gene. The 5 kanamycin resistant isolates were also macrolide resistant and had the erm(A/TR) gene (1 isolate) or the erm(B) gene (Table I).

Discussion

This study is, to our knowledge, the first report of high-level aminoglycoside resistance in GBS isolates from Scandinavia. Five of 396 GBS isolates (1.3%) from a nation wide study of colonizing GBS were kanamycin and amikacin resistant. Screening with kanamycin 1000 μg disks enabled a rapid and easy detection of these isolates. The breakpoint for the susceptible isolates was originally proposed as 17 mm (8). However, the distribution of the GBS population from this study suggests that a lower breakpoint, possibly at 12 mm would be more appropriate (Fig 1).

The kanamycin resistance gene aphA-3, present in these isolates, is in S. pneumoniae and Enterococcus faecalis located on transposons and plasmids, but the exact genetic organisation of the gene in these GBS isolates is not known. No isolates with high level gentamicin resistance was found.

Despite this, keeping the evolution in enterococci in mind, in which several aminoglycoside modifying enzymes have been described [START_REF] Chow | Aminoglycoside resistance in enterococci[END_REF], an active surveillance on the aminoglycoside resistance in GBS is warranted. The first gentamicin high level resistant (HLR) GBS, strain B128, was described in France in 1990 [START_REF] Buu-Hoï | High-level chromosomal gentamicin resistance in Streptococcus agalactiae (group B)[END_REF]. The gene of the bifunctional aminoglycoside modifying enzyme Aac(6´)-Aph (2´´) that mediate resistance to gentamicin and all other aminoglycosides besides streptomycin as well as homologes to aphA-3 and aad-6 genes was later identified in B128 [START_REF] Kaufhold | Identical genes confer high-level resistance to gentamicin upon Enterococcus faecalis, Enterococcus faecium, and Streptococcus agalactiae[END_REF]. The aminoglycoside resistant determinants were carried by the transposon Tn3706 located on the chromosome. Tn3706 could be transposed from its chromosomal location onto the plasmid IP501, a conjugative multiple antibiotic resistance plasmid that can be transferred and stably maintained in a variety of Gram-positive genera, including GBS [START_REF] Horaud | Chromosomal gentamicin resistance transposon Tn3706 in Streptococcus agalactiae B128[END_REF]. However, the transposition lead to a structural instability of the plasmid and the authors concluded that pIP501-like plasmids probably do not constitute appropriate vectors for dissemination of gentamicin HLR in GBS. The clinical impact of HLR aminoglycoside resistance is a loss of the synergistic bactericidal effect achieved in conjunction with cell wall active antibiotics as penicillin, which will compromise the effectiveness of therapy [START_REF] Baker | Synergism, killing kinetics, and antimicrobial susceptibility of group A and B streptococci[END_REF]. The combination of a cell wall active antibiotic and an aminoglycoside has been shown to greatly enhance the killing of GBS in vitro [START_REF] Baker | Synergism, killing kinetics, and antimicrobial susceptibility of group A and B streptococci[END_REF][START_REF] Cooper | Synergistic effects of ampicillinaminoglycoside combinations on group B streptococci[END_REF].

Penicillin is the main choice for prophylaxis and therapy of GBS infections. The methodology used for the antibiotic susceptibility test is of vital importance when resistance data are interpreted. An additional important factor for the comparison of susceptibility among isolates is the breakpoints set for classification of isolates. Screening for penicillin resistance with 1 μg oxacillin disks is recommended in Streptococcus pneumoniae and group A, B, C, and G streptococci by SRGA. The breakpoint to guard for penicillin resistance is at present set at 17mm. However, compared to the population distributions seen in pneumococci and group A, C, G streptococci, with a majority of isolates with oxacillin inhibition zones of 27-28 mm (www.srga.org), the GBS of this study exhibited inhibition zones with a mean zone size of 20mm (Table II). This is in agreement with data, presented by Baker et al almost thirty years ago, which showed that higher penicillin concentrations were needed for growth inhibition and killing of GBS than for group A streptococci [START_REF] Baker | Synergism, killing kinetics, and antimicrobial susceptibility of group A and B streptococci[END_REF]. The oxacillin breakpoint of 17mm divides what seems to be a susceptible (native) GBS population and possibly could a breakpoint of 14 or 15 mm be more suited for GBS. The results of the oxacillin screening according to the EUCAST method were in agreement with that suggestion. Recently, high sensitivity and specificity for detection of reduced penicillin susceptibility in GBS was reported with a provisional cut off value of 20 mm for ceftibuten in disk diffusion [START_REF] Kimura | Practical disk diffusion test for detecting group B streptococcus with reduced penicillin susceptibility[END_REF]. The tests were performed in accordance with the recommendation from the American Clinical and Laboratory Standards Institute (CLSI). From the results of our study a ceftibuten breakpoint for susceptibility of ≥ 15-16 mm seems to be more appropriate, a discrepancy possibly caused by the differences in methods used. However, studies on the alteration of Pbp genes in relation to penicillin susceptibility are needed to fully evaluate the isolates with smaller inhibition zones.

During 2008 a risk based program for IAP has been recommended by the National board of health in Sweden. Since this will lead to increased antibiotic use in the future it is of importance to follow the epidemiology of antibiotic resistance in GBS to be able to give guidance for the prophylaxis used. This is especially important when a risk based IAP program is used since no individual GBS isolates are cultured for examination of the antibiotic susceptibility in this regime. The overall degree of antibiotic resistance in the Swedish colonizing GBS isolates was low, with the exception for 79 % resistance against tetracycline. Only 5 % of the GBS were resistant to clindamycin, which can be compared to MLS B resistance rates around 15% in several European and Australian reports [START_REF] Jones | Multilocus sequence typing system for group B streptococcus[END_REF][START_REF] Zeng | Simultaneous detection of nine antibiotic resistance-related genes in Streptococcus agalactiae using multiplex PCR and reverse line blot hybridization assay[END_REF], and 5-32 % in the American continent [START_REF] Lopardo | Argentinian Streptococcus Study Group (2003) Six-month multicenter study on invasive infections due to group B streptococci in Argentina[END_REF][START_REF] Phares | Active bacterial core surveillance/emerging infections program network (2008) Epidemiology of invasive group B streptococcal disease in the United States, 1999-2005[END_REF].

An increased degree of MLS B resistance in serotype V isolates has been described [START_REF] Poyart | Genetic basis of antibiotic resistance in Streptococcus agalactiae strains isolated in a French hospital[END_REF][START_REF] Zeng | Simultaneous detection of nine antibiotic resistance-related genes in Streptococcus agalactiae using multiplex PCR and reverse line blot hybridization assay[END_REF]. This has also been shown in recent Swedish and Norwegian studies of invasive GBS isolates [START_REF] Persson | Antimicrobial susceptibility of invasive group B streptococcal isolates from south-west Sweden 1988-2001[END_REF][START_REF] Bergseng | Molecular and phenotypic characterization of invasive group B streptococcus strains from infants in Norway 2006-2007[END_REF].

However, in this nation wide collection of colonizing GBS from parturient women no serotype dominated among the clindamycin and/or erythromycin resistant isolates. Whether the high-level of MLS B resistance found in the four serotype V isolates that carried the ermB gene indicate that they have an additional resistance mechanism has to be further evaluated.

The serotype III lineage, CC17, containing sequence type 17 (ST17), is strongly associated with neonatal invasive infections [START_REF] Luan | Multilocus sequence typing of Swedish invasive group B streptococcus isolates indicates a neonatally associated genetic lineage and capsule switching[END_REF][START_REF] Jones | Multilocus sequence typing system for group B streptococcus[END_REF]. In a recent study serotype III isolates of ST17 were shown to carry less antibiotic resistance genes than the other GBS serotypes (14). The lack of MLS B resistance in this lineage was corroborated in our study.

We here provide a baseline description of resistance levels and resistance genes present among colonizing GBS in Sweden before implementation of a novel prophylactic regiment that will increase the use of intrapartum antibiotics. This kind of information will be useful in future evaluations of changes of resistance in GBS. We also suggest that a change of breakpoints for GBS oxacillin susceptibility tests should be considered. The results of this study partially disagree with some previous studies. We found no particular serotype to dominate among the MLS B resistant isolates. In contrast, other studies, in particular those that have included invasive isolates (14, 27, 28), indicate serotype V to be predominant among the MLS B resistant GBS. In Norway an increase in fatality rate among neonates with GBS infection has been observed which coincided with an increase in MLS B resistance; predominantly in serotype V isolates [START_REF] Bergseng | Molecular and phenotypic characterization of invasive group B streptococcus strains from infants in Norway 2006-2007[END_REF]. A possible explanation for the discrepancy between our study and others is that a clonal dissemination of MLS B resistant serotype V strains account for the increase among the invasive cases. We conclude that in this Swedish colonizing material, serotype V is a poor predictor of antibiotic resistance. However, the occurrence of high level erythromycin and clindamycin resistance found in all the four serotype V isolates containing the ermB gene merits further examination. In summary, among Swedish colonizing GBS isolates 5, 5% MLS B resistance and 1, 3% aminoglycoside resistance was found among the evenly distributed serotypes Ia to V.

  The genes aad-6 and aphA-3 encode aminoglycoside-modifying enzymes. The genes erm (B), erm (A/TR) and mef (A) mediate resistance to the macrolides-lincosamides-streptogramin B group of antibiotics. ISA-NAD is Iso-Sensitest Agar with 5% blood and 20 mg/L of nicotinamide adenine dinucleotide. MH-NAD is Mueller-Hinton agar with 5% horse blood and 20 mg/L nicotinamide adenine dinucleotide E and EM: erythromycin DA and CM:clindamycin

	Figure
	Figure 1.
	Table I
	Sample Resistance genes				Disk-diffusion, inhibition zones (mm)	Etest, MIC (mg/L)
	number										ISA-NAD ISA-NAD MH-NAD MH-NAD MH-NAD MH-NAD
			aad-6		aphA-3	erm B	erm A/TR	mef A	E	DA	E	DA	EM	CM	Serotype
			pos				pos	pos	neg	neg	12.8	17.3	11.9	14	2	0.5	III
	302	No. of isolates	neg pos neg				pos pos pos	pos pos pos pos	neg neg neg neg	neg neg neg neg	14.2 15 13.8 6	21.1 19.3 16.2 23.7	Kanamycin Streptomycin 11.1 12.5 12.3 6	12.8 14.3 14.2 21	2 4 4 >256	0.5 0.5 0.5 1	II II III III
								pos	neg	neg	6	6	6	6	>256	>256	V
								pos	neg	neg	6	6	6	6	>256	>256	V
								pos	neg	neg	6	6	6	6	>256	>256	V
								pos	neg	neg	6	6	6	6	>256	>256	V
	188		pos				pos	neg	pos	neg	20.1	31,6 D	10.8	22,7D	1	0.25	III
								neg	pos	neg	19.8	33,5 D	12.6	23,4D	1	0.12	III
								neg	pos	neg	15	31,2 D	12.9	29,5D	2	0.12	II
	846		6	7	8	9	neg 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 pos neg 15.5 31,9 D neg pos neg 16.7 32,4 D Zone diameters (mm) neg pos neg 17.7 34,8 D	11.8 11.8 12.8	28,0D 17,3D 30,1D	4 4 4	0.12 0.12 0.12	II V Ia
								neg	pos	neg	20.2	32,6 D	NT	NT	NT	NT	III
								neg	pos	neg	18.6	6	17	6	4	>256	II
	neg Fig.1. Zone diameter distributions for 1000 µg disks of kanamycin and streptomycin against 396 group pos neg 21.3 6 17.2 neg pos neg 13.9 6 6 B streptococci. neg neg neg 29.1 23.5 27.8	6 6 24	4 8 0.12	>256 >256 2	Ia Ib II
								neg	neg	neg	30.4	23.1	26.8	23.5	0.12	2	II
	865							neg	neg	neg	31	22.5	26.8	22.8	0.25	2	IV

Table I Table II

 III

	Oxacillin	Penicillin G MIC (Number of isolates)	Oxacillin	Ceftibuten
	Zone				Zone	Zone
	diameter				diameter	diameter
	range				range	range
	ISA-NAD	0,016 mg/L	0,032 mg/L	0,064 mg/L	MH-NAD	MH-NAD
	(mm)				(mm)	(mm)
	16,3-16,9	0	0	3	15,7-18,5	16,2-19,2
	17,7-18,4	0	10	11	16,1-20,7	16,9-20,5
	18,5-19,4	0	71	44	NT	NT
	19,5-20,4	2	73	33	NT	NT
	20,5-21,4	0	68	18	NT	NT
	21,5-22,4	7	38	2	NT	NT
	22,5-23,4	1	10	0	NT	NT
	23,5-24,4	1	0	0	NT	NT
	24,5-25,4	2	1	0	NT	NT

Table II

 II

Acknowledgments

Åsa Hedlund and Helén Edebro for technical assistance. This study was supported by a grant (ALF) from Västerbottens County Council.