帶背包約束的基數(shù)公平分配問題

王 浩，劉沁玲，李偉東**

(1. 云南大學(xué) 附屬中學(xué)，云南 昆明 650091；2. 云南大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，云南 昆明 650504)

背包問題是經(jīng)典的組合優(yōu)化問題之一[1]，在云計算、邊緣計算、區(qū)塊鏈、人工智能和流數(shù)據(jù)處理[2-6]等領(lǐng)域有著廣泛的應(yīng)用. 其中，多背包問題的研究成果最為豐富，其定義如下：給定n個物品的集合A={a1,a2,···,an}和m個背包的集合B={b1,b2,···,bm}.每個物品aj∈A的大小為sj，價值為pj；每個背包bi∈B的容量為Ci. 目標(biāo)為尋找物品子集A′?A，在不超過背包容量的情況下將A′中的所有物品放入背包，使得A′中物品的總價值達到最大.

眾所周知，多背包問題是NP-難的，因此需設(shè)計近似算法來尋找多背包問題的可行解.設(shè)∏是一個最大化的優(yōu)化問題，I表示該問題的任意一個實例，令 A表示求解優(yōu)化問題 ∏的一個多項式時間算法，A(I)和 OPT(I)分別表示算法 A求解實例I所得到的可行解的目標(biāo)函數(shù)值和最優(yōu)解的目標(biāo)函數(shù)值，則算法A的近似比（又稱為最壞情形界）[7]定義為

若對任意的實數(shù) ε＞0，算法族 Aε都能得到優(yōu)化問題 ∏ 的一個 (1-ε)-近似解，并且對于每一個固定的 ε，算法的時間復(fù)雜度是關(guān)于實例I大小的多項式函數(shù)，則稱算法族 Aε是關(guān)于優(yōu)化問題的一個多項式時間近似方案.

當(dāng)背包容量相等且物品的大小與價值相等時，Caprara等[8]給出多背包問題的一個多項式時間近似方案. 當(dāng)背包容量不等且物品的大小與價值相等時，Caprara等[9]給出多背包問題的一個多項式時間近似方案. 當(dāng)背包容量相等且物品的大小與價值無關(guān)時，Kellerer[10]給出多背包問題的一個多項式時間近似方案.當(dāng)背包容量不等且物品的大小與價值無關(guān)時，Chekuri等[11]給出多背包問題的一個多項式時間近似方案；Jansen[12-13]給出了運行時間更低的多項式時間近似方案，當(dāng)前的最佳結(jié)果為運行時間為poly(n)的多項式時間近似方案；Jansen等[14]證明了多背包問題不存在運行時間為+poly(|I|) 的多項式時間近似方案，這里的 poly(|I|)是指關(guān)于 |I| 的多項式函數(shù).

同時，公平分配問題也是經(jīng)典的組合優(yōu)化問題之一，并在最近幾年受到了廣泛的關(guān)注. 其定義如下：給定n個物品的集合和m個無容量限制的背包的集合，每個物品aj的價值為pj，將物品放入背包，使得背包的最小收益盡可能地大，這里背包的收益是指放入該背包物品的價值之和. 當(dāng)物品放入不同背包的價值相等時，Woeginger[15]給出了一個多項式時間近似方案. 當(dāng)物品放入不同背包的價值相等且具有等級約束時，Li等[16]給出了一個多項式時間近似方案. 當(dāng)物品放入不同背包的價值不等時，Bezakova等[17]證明了公平分配問題不存在近似比大于的近似算法；Asadpour等[18]給出了公平分配問題的一個近似算法. 黃彥等[19]討論了特殊網(wǎng)絡(luò)中帶懲罰的魯棒公平分配問題.

實際上，背包的容量通常有限，因此，帶背包約束的公平分配問題應(yīng)運而生. 其定義如下：給定n個物品的集合和m個背包的集合，每個物品aj的大小為sj，價值為pj；每個背包bi∈B的容量為Ci. 目標(biāo)為尋找物品子集A′?A，在不超過背包容量的情況下將A′中的所有物品放入背包，使得背包的最小收益盡可能地大. 當(dāng)背包容量相等且物品的大小與價值相等時，Caprara等[8]等給出帶背包約束的公平分配問題的一個近似算法，并證明了該問題不存在近似比大于的多項式時間算法. Li等[20]給出帶二部圖和背包約束的公平分配問題的一個近似算法，并證明了該問題不存在近似比大于的多項式時間算法.

本文研究了物品的價值全為 1 時的帶背包約束的公平分配問題，稱之為帶背包約束的基數(shù)公平分配問題，分別對背包容量相等和不等的情形，給出了近似比的下界和幾乎最佳的近似算法. 本文結(jié)構(gòu)如下：第1節(jié)描述帶背包約束的基數(shù)公平分配問題；第2節(jié)給出背包容量相等情形下，帶背包約束的基數(shù)公平分配問題近似比的下界和一個多項式時間近似算法；第3節(jié)給出背包容量不等情形下，帶背包約束的基數(shù)公平分配問題近似比的下界和一個多項式時間近似算法；第4節(jié)對全文進行了總結(jié)，并指出未來的研究方向.

1 問題描述

帶背包約束的基數(shù)公平分配問題定義為：給定n個物品的集合A={a1,a2,···,an} 和m個背包的集合B={b1,b2,···,bm}，其中物品aj∈A的大小為sj，背包bi∈B的容量為Ci.尋找一個物品的集合A′?A，將A′中的物品全部裝入這m個背包里，即找到A′的一個完全劃分，使得

這里Si表示放入背包bi中的物品集合. 目標(biāo)函數(shù)為最大化背包中裝入的最小物品數(shù), 即

引入0-1變量xij，這里xij=1當(dāng)且僅當(dāng)可行解中物品aj放入背包bi， 則帶背包約束的基數(shù)公平分配問題的整數(shù)規(guī)劃形式為：

顯然，當(dāng)物品個數(shù)n＜m時，至少存在著一個背包沒有放入任何物品，最優(yōu)值為0，則任何可行解都是最優(yōu)解. 不失一般性，假定n≥m.

定理1當(dāng)m≤n＜2m時，帶背包約束的基數(shù)公平分配問題存在多項式時間最優(yōu)算法.

證明給定帶背包約束的基數(shù)公平分配問題的一個實例I=(A,B,s,C)，當(dāng)m≤n＜2m時，至少存在著一個背包放入至多一個物品，則最優(yōu)值為0或1. 構(gòu)造一個二部圖G=(A∪B,E)，這里頂點集A對應(yīng)物品集A，頂點B對應(yīng)物品集B，邊 (aj,bi)∈E當(dāng)且僅當(dāng)物品aj的大小不超過背包bi的容量，即sj≤Ci.

若實例I的最優(yōu)值為1， 丟掉背包中多余的物品，可以構(gòu)造出每個背包恰好包含一個物品的最優(yōu)解.由可行性知，在最優(yōu)解中， 放入背包bi的物品aj滿足 (aj,bi)∈E. 因此， 可以構(gòu)造二部圖G的一個匹配M，這里 (aj,bi)∈M當(dāng)且僅當(dāng)在最優(yōu)解中物品aj放入背包bi.容易驗證， 匹配M的基數(shù)為m.

若二部圖G中存在著一個基數(shù)為m匹配M，對每一條邊 (aj,bi)∈M?E，由G的構(gòu)造方式知， 物品aj的大小不超過背包bi的容量. 可以構(gòu)造實例I的一個可行解， 其中物品aj放入背包bi當(dāng)且僅當(dāng)(aj,bi)∈M. 容易驗證，每個背包中恰有一個物品， 即其目標(biāo)函數(shù)值為1， 這意味著實例I的最優(yōu)值為1.

因此， 實例I的最優(yōu)值為1當(dāng)且僅當(dāng)二部圖G中存在著一個基數(shù)為m匹配M. 利用二部圖最大基數(shù)匹配問題的多項式時間最優(yōu)算法[21]可以求得實例I的最優(yōu)解， 即帶背包約束的基數(shù)公平分配問題存在多項式時間最優(yōu)算法. 證畢.

定理2當(dāng)n=mk+l時，這里 0＜l＜m，帶背包約束的基數(shù)公平分配問題存在一個裝入前mk*個物品的最優(yōu)解， 這里k*表示最優(yōu)值.

證明對任意一個最優(yōu)解，若存在一個背包中放入的物品數(shù)大于k*，丟棄該背包中下標(biāo)最大的物品，直到該背包內(nèi)的物品數(shù)恰為k*，可以得到一個至多使用mk*個物品的最優(yōu)解. 若存在一個背包裝有下標(biāo)大于mk*的物品，可以用一個下標(biāo)最小的未放入物品進行替換，直到所有背包中裝入的物品的下標(biāo)都不超過mk*.最終可以得到一個裝入前mk*個物品的最優(yōu)解. 證畢.

因此，不失一般性，本文基于如下假設(shè)進行討論.

基本假設(shè)n=mk(k≥2)，且存在著一個目標(biāo)函數(shù)值為k的最優(yōu)解.

2 背包容量相同的情形

本節(jié)考慮所有背包的容量均相同的情形. 首先給出k=2 時，帶背包約束的基數(shù)公平分配問題的一個多項式時間最優(yōu)算法. 接著通過對3-劃分問題的多項式歸約，證明帶背包約束的基數(shù)公平分配問題是+ε不可近似的，這里 ?ε＞0，除非 P=NP. 最后，基于貪婪思想給出最佳的近似算法.

定理3當(dāng)所有的背包容量均相同且k=2 時，帶背包約束的基數(shù)公平分配問題存在多項式時間最優(yōu)算法.

證明當(dāng)所有的背包容量均相同時，對i=1,2,···,m，設(shè)Ci=C. 給定帶背包約束的基數(shù)公平分配問題的一個實例I=(A,B,s,C)，當(dāng)n=2m時，由基本假設(shè)知，最優(yōu)值為2. 構(gòu)造一個無向圖G=(A,E)，這里頂點集A對應(yīng)物品集A，邊 (aj1,aj2)∈E當(dāng)且僅當(dāng)物品aj1和aj2的大小不超過背包容量，即sj1+sj2≤C.

給定實例I的一個最優(yōu)解，易知每一個背包中恰好裝有2個物品ai1和ai2，且這2個物品的大小之和不超過背包容量，因此對應(yīng)的邊 (ai1,ai2)∈E. 這意味著，圖G=(A,E)中存在一個基數(shù)為m的完美匹配. 給定G=(A,E)的任意一個基數(shù)為m的完美匹配M?E，對每一條邊 (ai1,ai2)∈M，由圖G=(A,E) 的構(gòu)造知，對應(yīng)的物品ai1和ai2的大小不超過C，因此，每一條邊對應(yīng)的2個物品可以放入同一個背包，從而構(gòu)造出實例I的一個目標(biāo)函數(shù)值為2的最優(yōu)解. 利用圖G的完美匹配算法[21]可以在多項式時間內(nèi)求出完美匹配M，進而求出實例I的最優(yōu)解. 因此，帶背包約束的基數(shù)公平分配問題存在多項式時間最優(yōu)算法. 證畢.

定理4當(dāng)所有的背包容量均相同且k≥3 時，帶背包約束的基數(shù)公平分配問題不存在近似算法，這里 ε＞0 是任意常數(shù).

證明3-劃分問題[22]定義為：給定一個有3m個元素的集合Z={z1,z2,···,z3m}，且滿足=mB，其中zj為非負整數(shù)且滿足問集合Z能否被劃分為m個子集Z1,Z2,···,Zm，使得每個子集Zi恰好包含3個Z中的元素，且對任意i∈{1,2,···,m}，有

給定3-劃分問題的一個實例I，按如下方式構(gòu)造帶背包約束的基數(shù)公平分配問題的一個實例τ(I)：m個容量均為C=B的背包b1,b2,···,bm和 3m個物品，對任意的j=1,2,···,3m，實例I中的元素zj對應(yīng)一個物品aj，其大小為sj=zj.

下面證明3-劃分問題的實例I有解的充分必要條件是帶背包約束的基數(shù)公平分配問題的實例τ(I) 的最優(yōu)值為 3.

必要性設(shè)3-劃分問題有解構(gòu)造實例τ(I) 的一個可行解：對所有i(i=1,2,···,m)，把Zi={zi1,zi2,zi3}中的元素所對應(yīng)的物品ai1,ai2,ai3放入背包bi之中，此時有

因此該方案可行且每個背包中裝有3個物品. 因為實例 τ(I) 中含有3m個物品，m個背包，故實例τ(I)的最優(yōu)值為 3.

充分性假設(shè)實例τ(I) 的最優(yōu)值為3. 在最優(yōu)解中，對所有i(i=1,2,···,m)，背包bi中放入3個物品，記為ai1,ai2,ai3.下面構(gòu)造實例I的一個可行解：對所有i(i=1,2,···,m)，把背包bi中的物品ai1,ai2,ai3所對應(yīng)的元素zi1,zi2,zi3置于集合Zi中，即. 因為，且sik=zik，所以，故. 又由于

故對所有i(i=1,2,···,m)，=B.因此Z1,Z2,···,Zm為實例I的可行解.

因此，(3-劃分)問題的實例I有解當(dāng)且僅當(dāng)τ(I) 的最優(yōu)值為3. 假設(shè)帶背包約束的基數(shù)公平分配問題存在著一個近似算法 A. 若算法 A的輸出解的目標(biāo)函數(shù)值為3，則 τ(I) 的最優(yōu)值為3，這意味著3-劃分問題有可行解. 若算法 A 的輸出解的目標(biāo)函數(shù)值不超過2，則 τ(I) 的最優(yōu)值至多為，這意味著3-劃分問題無可行解. 這與3-劃分問題的NP困難性矛盾. 因此，帶背包約束的基數(shù)公平分配問題是不可近似的. 證畢.

當(dāng)n≥3m即k≥3時，可以利用貪婪法的思想對背包進行輪處理. 每一輪中，在本輪未放入物品的背包中，選擇一個剩余容量最小的背包，放入一個下標(biāo)最小的一個物品，直至超過背包容量或者無剩余物品. 對t=1,2,···,和i=1,2,···,m，令表示進行t輪分配后第i個背包中的物品集，表示中的物品的大小之和. 算法的具體描述如下：

貪婪算法

輸入：n個物品構(gòu)成的集合A，物品aj∈A的大小為sj，m個容量均為C的背包構(gòu)成的集合B.

輸出：m個互不相交的物品子集S1,S2,···,Sm.

第1步：令t=1，且對i=1,2,···,m，令

第3步：將物品atm+1,atm+2,···,a(t+1)m依次放入背包b1,b2,···,bm. 若所有物品均能放入相應(yīng)的背包，對i=1,2,···,m，令，且t←t+1；否則，算法終止，輸出i=1,2,···,m.

第4步：若t=k，則算法終止，輸出i=1,2,···,m；否則，轉(zhuǎn)第2步.

定理5對任意2個背包bi1和bi2，均有

證明數(shù)學(xué)歸納法. 當(dāng)t=1時，結(jié)論顯然成立. 假設(shè)當(dāng)t′=t-1(t≥2)時成立，即

設(shè)在t輪時放入背包bi1和bi2的物品的大小分別為s1和s2，則

下面分2種情況討論：

且

且

定理6當(dāng)所有背包的容量均相同且k≥3 時，貪婪算法可以在多項式時間內(nèi)找到一個目標(biāo)函數(shù)值至少為k-1 的可行解.

證明若算法終止時，t=k或t=k-1，則每個背包中至少裝有k-1 個物品，貪婪算法找到一個目標(biāo)函數(shù)值至少為k-1的可行解. 若算法終止時，t=≤k-2，則每個背包中恰好裝有個物品. 由算法的選擇知，存在一個最小的m0(1≤m0≤m)，使得物品無法放入背包，因此，對i=1,2,···,m0-1 有

對i=m0+1,m0+2,···,m，由定理5知，

容易驗證，貪婪算法至多進行k輪循環(huán)，每次循環(huán)的計算時間至多O(mlogm). 因此，貪婪算法的運行時間為O(kmlogm).證畢.

算例 1考慮一個m=2，k=3 且C=10的實例，其中6個物品的大小分別為1,1,3,3,4和8. 將物品a1，a2和a6放入背包b1，其余3個物品放入背包b2，可得一個目標(biāo)函數(shù)值為3的最優(yōu)解. 貪婪算法進行2輪分配后輸出一個可行解，其中物品a1和a3放入背包b1，物品a2和a4放入背包b2，從而得到一個目標(biāo)函數(shù)值為2的可行解.

3 背包容量不同的情形

本節(jié)討論背包容量不同的情形. 首先通過對3維數(shù)值匹配問題的多項式歸約，證明了帶背包約束的基數(shù)公平分配問題是不可近似的，這里除非 P=NP.最后，分別給出k=2和k≥3 時的幾乎最佳近似算法.

定理7當(dāng)背包的容量不同時，帶背包約束的基數(shù)公平分配問題不存在近似算法.

證明3維數(shù)值匹配問題[22]定義為：給定3個均包含m個元素的集合X={x1,x2,···,xm}，Y={y1,y2,···,ym}，Z={z1,z2,···,zm}，且滿足

問集合X∪Y∪Z能否被劃分為m個子集A1,A2,···,Am，使得每個子集Ai恰好包含X,Y和Z中各一個元素，且對任意i∈{1,2,···,m}，有

給定3維數(shù)值匹配問題的一個實例I，按如下方式構(gòu)造帶背包約束的基數(shù)公平分配問題的一個實例τ(I)：對任意的i=1,2,···,m，背包bi的容量Ci=M+B-zi；對任意的j=1,2,···,m，集合X中的元素xj對應(yīng)一個物品aj，其大小為sj=xj，集合Y中的元素yj對應(yīng)一個物品am+j，其大小為sm+j=M+yj，這里M是足夠大的常數(shù).

下面我們證明3維數(shù)值匹配問題的實例I有解的充分必要條件是帶背包約束的基數(shù)公平分配問題的實例 τ(I) 的最優(yōu)值為2.

必要性設(shè)3維數(shù)值匹配問題有解A1={x(1),y(1),z1}，A2={x(2),y(2),z2},···，Am={x(m),y(m),zm}，這里zi包含在集合Ai中，則對i=1,2,···,m，有x(i)+y(i)+zi=B.構(gòu)造 τ(I) 的一個可行解：對所有i(i=1,2,···,m)，將Ai中的元素所對應(yīng)的物品a(i)和am+(2)放入背包bi，此時有

因此該方案可行且每個背包中裝有2個物品. 因為共有 2m個物品,m個背包, 故實例 τ(I) 的最優(yōu)值為2.

充分性假設(shè)實例 τ(I) 的最優(yōu)值為2. 對所有i(i=1,2,···,m)，由實例 τ(I) 的構(gòu)造方式知，背包bi放入的2個物品分別屬于物品集 {a1,a2,···,am} 和 {am+1,am+2,···,a2m}，記為a(i),am+(i).下面構(gòu)造實例I的可行解：對所有i(i=1,2,···,m)，將背包bi中的物品a(i),am+(i)所對應(yīng)的元素x(i),y(i)和背包bi所對應(yīng)的元素zi置于集合Ai中，即Ai={x(i),y(i),zi}.對所有的i=1,2,···,m，因為s(i)+sm+(i)≤Ci=M+B-zi，所以x(i)+y(i)+zi≤B.又由于

故對所有i(i=1,2,···,m)，x(i)+y(i)+zi=B.因此A1,A2,···,Am為實例I的一個可行解.

因此，3維數(shù)值匹配問題的實例I有解當(dāng)且僅當(dāng) τ(I) 的最優(yōu)值為2. 假設(shè)帶背包約束的基數(shù)公平分配問題存在著一個近似算法 A.若算法 A的輸出解的目標(biāo)函數(shù)值為2，則 τ(I) 的最優(yōu)值為2，這意味著實例I有可行解. 若算法 A 的輸出解的目標(biāo)函數(shù)值不超過1，則τ(I) 的最優(yōu)值至多為，這意味著實例I無可行解. 這與3維數(shù)值匹配問題的NP困難性矛盾. 因此，帶背包約束的基數(shù)公平分配問題是不可近似的. 證畢.

定理8當(dāng)背包的容量不同且k=2 時，可以在多項式時間內(nèi)找到帶背包約束的基數(shù)公平分配問題的一個目標(biāo)函數(shù)值至少為 1 的可行解.

證明給定帶背包約束的基數(shù)公平分配問題的一個實例I=(A,B,s,C)，當(dāng)k=2 時，由基本假設(shè)知，最優(yōu)值為2. 構(gòu)造一個二部圖G=(A∪B,E)，這里頂點集A和B分別對應(yīng)物品集A和背包集B，邊(aj,bi)∈E當(dāng)且僅當(dāng)物品aj的大小不超過背包bi的容量，即sj≤Ci.

給定實例I的一個最優(yōu)解，易知每一個背包中恰好裝有2個物品ai1和ai1，且這2個物品的大小都不超過背包容量，因此對應(yīng)的邊 (aj1,bi),(aj2,bi)∈E. 這意味著，二部圖G=(A∪B,E) 中存在一個基數(shù)為m的匹配. 給定G=(A∪B,E) 的任意一個基數(shù)為m的匹配M?E，對每一條邊 (aj,bi)∈M，由圖G=(A∪B,E) 的構(gòu)造知，對應(yīng)的物品aj的大小不超過Ci，因此，將每一條邊 (aj,bi)∈M對應(yīng)的物品放入背包bi，從而構(gòu)造出實例I的一個目標(biāo)函數(shù)值為1的可行解. 利用二部圖的完美匹配算法[21]可以在多項式時間內(nèi)求出圖G的完美匹配M，因此，可以在多項式時間內(nèi)找到帶背包約束的基數(shù)公平分配問題的一個目標(biāo)函數(shù)值至少為1的可行解. 證畢.

對一個給定的實例I=(A,B,s,C)，帶背包約束的基數(shù)公平分配問題的整數(shù)規(guī)劃的松弛形式[23]

利用線性規(guī)劃求解算法可以得到 RLP(I)的一個最優(yōu)分數(shù)解對i=1,2,···,m，令在 RLP(I) 的最優(yōu)解中，可以證明至少存在一個滿足 |Ai|≥k-2的背包bi.將Ai中的物品放入背包bi，并在實例I刪除背包bi和Ai中的物品. 對剩余的物品和背包重新構(gòu)造一個整數(shù)規(guī)劃的松弛形式 RLP(I). 重復(fù)此過程，直至所有的背包中都至少裝有k-2 個物品. 算法具體描述如下：

迭代取整算法

輸入：n個物品構(gòu)成的集合A，m個背包構(gòu)成的集合B；物品aj∈A的大小為sj.

輸出：m個互不相交的物品子集S1,S2,···,Sm.

第1步：若背包集非空，則求解 RLP(I),得到分數(shù)最優(yōu)解

第2步：對i=1,2,···,m，置

第3步：令i*∈argmax |Ai|，B←B{bi*}，Si*=Ai*，且A←AAi* 中下標(biāo)最小的k(m-1)個物品. 置I=(A′,B′,s,C)，并轉(zhuǎn)第1步.i

定理9當(dāng)背包的容量均相同且n≥3m 時，迭代取整算法可以在多項式時間內(nèi)找到一個目標(biāo)函數(shù)值至少為k-2 的可行解.

證明由基本假設(shè)知，數(shù)學(xué)規(guī)劃 RLP(I)存在目標(biāo)函數(shù)值為k的分數(shù)最優(yōu)解對j=1,2,···,km，若存在一個背包bi滿足，則稱物品aj是分離的. 由于 RLP(I)的約束個數(shù)為 (k+2)m，最優(yōu)解中至多有 (k+2)m個非零變量又因為每一個物品至少產(chǎn)生一個非零變量，且km個物品都被分配，所以最優(yōu)解中至多有 2m個分離的物品. 對一個背包bi(i=1,2,···,m)，令表示裝入背包bi的非分離的物品集，則有

因此存在著一個背包bi滿足 |Ai|≥k-2. 由于

將Ai的物品放入背包bi，不會超過該背包的容量，且背包bi中至少裝有k-2 個物品. 由算法的選擇知，迭代取整算法中所選擇的背包bi* 中至少裝有k-2 個物品.

令A(yù)′表示AAi* 中下標(biāo)最小的k(m-1)個物品，且B′=B{bi*}.對每一個背包bi∈B′，若中的所有物品的下標(biāo)都不超過k(m-1)，則由的定義知

重復(fù)上述分析過程，最后可以證明迭代取整算法的輸出解中，所有的背包中都至少裝有k-2 個物品.證畢.

4 總結(jié)

本文研究了帶背包約束的基數(shù)公平分配問題，并分別設(shè)計了背包容量相同和背包容量不同時的不可近似比與幾乎最佳的近似算法. 未來可以考慮更一般情況下的帶背包約束的公平分配問題，例如物品的價值不等、帶指派約束等.