竞争性选址问题：平衡的设施位置和

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Competitive Location Problems: Balanced Facility Location and the
  One-Round Manhattan Voronoi Game》
---
作者：
Thomas Byrne, S\\\'andor P. Fekete, J\\\"org Kalcsics, and Linda Kleist
---
最新提交年份：
2020
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computational Geometry        计算几何
分类描述：Roughly includes material in ACM Subject Classes I.3.5 and F.2.2.
大致包括ACM课程I.3.5和F.2.2中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Discrete Mathematics        离散数学
分类描述：Covers combinatorics, graph theory, applications of probability. Roughly includes material in ACM Subject Classes G.2 and G.3.
涵盖组合学，图论，概率论的应用。大致包括ACM学科课程G.2和G.3中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Economics        经济学
二级分类：Theoretical Economics        理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--
一级分类：Mathematics        数学
二级分类：Optimization and Control        优化与控制
分类描述：Operations research, linear programming, control theory, systems theory, optimal control, game theory
运筹学，线性规划，控制论，系统论，最优控制，博弈论
--

---
英文摘要：
  We study competitive location problems in a continuous setting, in which facilities have to be placed in a rectangular domain $R$ of normalized dimensions of $1$ and $\\rho\\geq 1$, and distances are measured according to the Manhattan metric. We show that the family of \'balanced\' facility configurations (in which the Voronoi cells of individual facilities are equalized with respect to a number of geometric properties) is considerably richer in this metric than for Euclidean distances. Our main result considers the \'One-Round Voronoi Game\' with Manhattan distances, in which first player White and then player Black each place $n$ points in $R$; each player scores the area for which one of its facilities is closer than the facilities of the opponent. We give a tight characterization: White has a winning strategy if and only if $\\rho\\geq n$; for all other cases, we present a winning strategy for Black.
---
PDF下载：
--> Competitive_Location_Problems:_Balanced_Facility_Location_and_the_One-Round_Manh.pdf (3.26 MB)

2022-4-24 15:53:30 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：竞争性 Applications Environments Contribution Coordination

竞争定位问题：平衡设施定位与爱丁堡大学的数学Kingdomtbyrne@ed.ac.ukS兰多·P·费克特德国布伦瑞克大学计算机科学系。fekete@tu-bs。爱丁堡大学数学系KalCSICS。kalcsics@ed.ac.ukLinda克莱斯特计算机科学系，德国布伦瑞克大学。kleist@tu-bs。正规维数为1和ρ的矩形域中的去抽象≥1，距离根据曼哈顿度量标准进行测量。我们表明，与欧几里得距离相比，该度量中的平衡设施配置族（其中单个设施的Voronoi单元在许多几何属性上是相等的）要丰富得多。我们的主要结果考虑了一轮沃罗诺游戏与曼哈顿距离，其中第一名白人玩家和第二名黑人玩家各占1卢比；每名球员得分的区域，其一项设施比对手的设施更接近。

我们给出了一个严格的刻画：White有一个winningstrategy当且仅当ρ≥ N对于所有其他情况，我们提出了黑人获胜的策略。2012年ACM学科分类计算理论→计算几何；应用计算→ 基于该预印本内容的操作研究关键词和短语设施位置、竞争位置、曼哈顿距离、Voronoi游戏、几何优化相关版本、扩展摘要将出现在国际会议和算法和计算研讨会（Walcom）2021〔6〕。通过满足需求点集合，他们获得了巨大的重要性；在几何环境中，欧几里得距离或曼哈顿距离在竞争环境中，两个或两个以上的玩家争夺最佳位置。这种向竞争性、多玩家版本的转变可能会对优化问题的算法难度产生严重影响：例如，经典的旅行商问题是NP难问题，而竞争性的两人版本甚至是PSPACE完全[10]。arXiv:2011.13275v1[cs.CG]20202年11月26日竞争性位置问题（a）白位3分。（b） 黑色得3分。（c） 占主导地位的地区。图1曼哈顿沃罗诺一轮游戏示例。在设施争夺客户的环境中，注意力有限。我们研究了一个自然rρ≥而不是任何其他设施，即相应的（开放的）Voronoi电池，受应用测量的限制。对于欧几里德距离，平分线（与两个设施距离相等的一组点）是开放Voronoi单元的边界，因此其面积为零，而曼哈顿区域可能具有正面积，如图2所示。

如下所示，Voronoi单元的计算是相等的。利用Voronoi细胞的几何性质，我们完全解决了一个经典问题，以获得更高的分数。由于曼哈顿指标的不同性质，两个层的主导地位可能严格低于ρ/2，其余区域属于中性区。1.1德雷兹纳[8]的相关工作手册，引文超过1200篇，或拉波特等人[17]的最新著作。许多应用程序产生于具有异构维度的多维数据集。随之而来的问题也受到了算法方面的关注。Fekete等人[12]研究了各种条件设施位置问题。由Ahn等人[1]提出，两名玩家轮流放置一个设施。最后，每个玩家都要计算他们所有沃罗诺地区的总面积。（对于所有[18]的概述显示，问题是PSPACE完成，即使在离散的图形设置中也是如此。立即放置设备。Cheong等人[7]显示，对于平面中的欧几里德距离，白色总是能赢得一维区域，而黑色总是赢。Byrne，S.P.Fekete，J.Kalcsics，L.Kleist 3通过在1×ρ和ρ的矩形中显示这一点≥1.布莱克赢了≥ρ<n/√nρ</√由于几何形状不同，这需要几个额外的工具。对于第二个玩家。正如Fekete和Meijer[11]所示，对于变量和结果，这个问题是NP难的，参见[5,9,13,14]。1.2主要结果我们的主要结果是双重的。我们证明了平衡配置的多样性要大得多。我们给出了长宽比为ρ的矩形中一轮曼哈顿Voronoi对策的完整刻画≥1.我们证明了White有一个获胜策略，当且仅当ρ≥ N对于所有其他情况，布莱克都有一个获胜的策略。2.准备工作：在一个直角器中指定一组有限的点。

对于两点sp=（x，y）和p=（x，y），我们定义x（p，p）：=|x- x |和y（p，p）：=| y- y |。然后他们的曼哈坦距离由dM（p，p）给出：x（p，p）+y（p，p）。定义（p，p）：={p∈ R | dM（p，p）<dM（p，p）}作为一组比p更接近p的点，p中p的Voronoi单元是vp（p）：=\\q∈P\\{P}D（P，q）。VPofP。与欧几里德情形不同，对于欧几里德情形，Voronoi图有度量零，每个Voronoi单元都是凸的：曼哈顿Voronoi图可能包含正度量的中性区域，曼哈顿Voronoi单元不需要是凸的，但它们是星形的。与pand p距离相等的所有点的集合，即B（p，p）：={q∈ R | dM（q，p）=dM（q，p）}。有三种类型的平分线，如图2所示。通常，平分线由一段坡度为±1的线段组成；参见图2（a）。如果x（p，p）=0或y（p，p）=0，则对角线段收缩到一个点，平分线由（垂直或水平）xp、pyp、pBp、p包含两个区域组成；见图2（c）。我们称这种类型的平分线为退化的。此外，如果非退化平分线包含垂直（水平）线段，则它是垂直（水平）的。ar X i v4竞争位置问题十、Y十、-y2十、-y2（a）一般垂直平分线。x2（b）情况：y（p，p）=0。（c） 退化平分线。图2三种平分线的图示。pxp，yp∈ P`vp`hppVPpall半细胞由垂直线byH |和水平线byH获得-. 此外，我们定义：=H|∪ H-作为P的所有半细胞的集合。应用“vp”hppQipi∈ {, . . . ,}; 参见图3（a）。此外，Ci（p）：=VP（p）∩ 气（p）被称为p的第四个四分之一细胞。我们还考虑了EPP的八个区域。∈ 由Cuttingrang得出，`vp`hp±p（开放）区域作为Oi（p）fori表示的八分之一∈ {，…}，见图3（b）；亲密医生用Oi（p）表示。

R的子集S的面积用面积（S）表示。为了一分∈ P、 我们称这四条水平和垂直射线为atp，包含VP（P），VP（P）（或ofp）的四个臂。如果两个臂的端点接触R的边界，则它们是相邻的；否则它是内在的。为了便于以后参考，我们注意到以下几点。我喜欢观察1。以下性质适用：（i）如果平分线b（p，q）是非退化且垂直（水平）的，那么它不与p的左半单元和右半单元（顶部和底部）相交。（ii）iq，q∈ OipBp、qBp、qtype（垂直/水平）。（iii）Voronoi单元包含在由其臂跨越的轴对齐矩形中。证据XY被它的手臂跨过，因此，财产（iii）持有。JC2C1C3C4Q1Q2Q4（a）象限和四分之一单元格。O1O2O3O4O5O6O7O8（b）辛烷。（c） 2×3的网格。图3关键定义的说明。T.Byrne，S.P.Fekete，J.Kalcsics，L.Kleist 53平衡点设置了对每个设施相同的影响量。第二个局部最优性来自Prare Satified：公平性：适用于所有p，p∈ P，VP（P）和VP（P）有相同的面积。局部最优性：适用于所有p∈ P，P最小化到VP（P）中各点的平均距离。对于曼哈顿距离，根据半个和四分之一单元的面积，局部最优性有一个简单的几何特征；参见图3（a）。我是引理2。仅当下列任一性质成立时：（i）p是VP（p）的曼哈顿中值：VP（p）的所有四个半单元具有相同的面积。（ii）psatis定义了四分之一单元的属性：VP（p）的对角四分之一单元具有相同的面积。证据有关说明，请参考图3（a）。请注意四分之一细胞的面积（p）。首先，我们考虑一个PoPTCP＝（XP，YP），它将平均MhanthTaN距离最小化到所有点VIp（p）。

假设上半个单元格的面积超过下半个单元格的面积，即a+a>a+a。然后将GpbyP=（xp，yp+ε）替换为适当小的ε>0会减少平均距离，并使平均X距离Paa<aasoa+a=a+a，使VP（p）的支付中值变小。类似地，我们得出的结论是a+a=a+a，使Vp（p）的panx中值。这表明VP（p）的所有半细胞都是xpyp，所以这是必要的，也是有效的。我们现在证明（i）等价于（ii）。通过添加方程式a+a=a+aa+a=a+aaaaaaaaa<==> 啊，拿一个- a=a- A.<==> a=a。因此，四分之一单元格属性已满。相反，a=a和a=a=a+a=a+a=a+a=a+a=a+a。JLemma 2立即暗示了以下特征。我相信推论3。当且仅当所有半细胞具有相同面积时，矩形上的点集保持平衡。一个简单的平衡集族由正则A×bgrids产生；参见图3（c）。无单元格为矩形的平衡点集。我是引理4。图4所示的结构r2，ρ，R，R，R是平衡的。此外，R2，ρ，ρ∈[1，/2]，以及分别具有两个和三个点的唯一平衡非网格点集。ar X i v6竞争位置问题 1212+p21p212+p21p2R2，对于 2.（1,3/2]R3R2,1r4r5图4基数为2,3,4和5的平衡点集的非网格示例。简单计算表明，配置是平衡的。为了证明唯一性，我们使用引理2。虽然n=2的分析可以很容易地手动进行，但对于n=3，相对点位置导致了大约20种结构不同的Voronoi图，这些图是经过检查的使用MATLAB(R)编程。我们在附录A中给出了详细信息。观察到R2、ρ、R、R和稀有原子，即它们不能分解为构建块，从而产生大量平衡构型。定理5。nn 6RPNTHp是平衡的，没有Voronoi单元是矩形的。证据nk`k，`∈ {,, . .

.}kblocks of rand`blocks of r，如图5（a）所示。这将产生与NKK的配置≥nkk-K≥nkk-K≥N≥n、 ，nkk∈ NKR图4中的配置。J（a）组合矩形R中n=3k+5l点的配置的随机块的K块，ρ（R）=/49（36k+60l）。（b） n=2k点的组合kblocks。图5定理5证明的图解。包含许多相同原子成分的直接重复。事实上，存在过大的非重复平衡配置，没有直接相邻的同余原子子配置。T.Byrne，S.P.Fekete，J.Kalcsics，L.Kleist 7I定理6。在0-1串和无矩形Voronoi单元的非重复平衡配置之间存在注入。证据对于给定的0-1串长度，如果S在位置i中有一个1，我们使用块S的间距及其反射的第i对；否则，块序列将保留。JR3R03R03R3R03图6定理6证明的图示。配置代表每个玩家要玩的字符串01.4曼哈顿沃罗诺游戏点数。在不丧失一般性的情况下，Rhas高度1和宽度ρ≥1.玩家白色选择一组白色点inR，然后玩家黑色选择一组黑色点，带W∩ B=. 每个玩家都为对手得分。因此，如果一个玩家的两个点共享退化平分线，则可能的椭圆区域将分配给该玩家。因此，通过替换每个退化平分线，可以计算出其（水平放大的）曼哈顿Voronoi单元的面积。有点滥用大众汽车∪比蒂。R、 nWBnBBbareaVW∪Bb/2n·areaRWWwinning set，如果黑人既没有平局也没有获胜盘。

如果黑人或白人渠道确定了一套获胜方案，我们就说他们有一套获胜策略。尽管曼哈顿距离可能存在退化平分线，但我们证明了黑人有一个获胜策略当且仅当黑人有一个获胜点。我们利用以下两个引理。我是引理7。考虑一个带有一组白色点的矩形。然后，对于每一个ε>和每半个细胞，黑色可以放置一个点，比如VW的面积∪{b} （b）∩ 他的至少（面积（H）- ε).证据在不损失一般性的情况下，我们考虑了左半部分。∈ 如图7所示。通过将b轻轻地放在w的左侧，平分线b（b，w）是一个垂直段BWVW∪{b} bHBb，wVW∪{b} b∩HHHbwb足够接近时，差异降至任何固定ε>0以下。Jar X i v8竞争性位置问题事实上，白人必须在比赛中保持平衡；否则黑人会赢。我是引理8。让我们在一个矩形中画一组白点。如果哈桑区域的任何半个单元与/2n·区域（R）不同，那么黑色有一个获胜的策略。证据如果不是所有的半细胞都有相同的面积，那么就存在一个半细胞，其面积（H）>/2n·面积（R）。我们假设w.l.o.g.是H |的半个细胞；否则我们会考虑-. 表示h | byH，…，的最大半个单元格，因此，存在δ>0，使得pni=1Hi=/2·面积（R）+δ。biHiε>ε<δ/nnb点，B这样NXI=1区域（大众汽车）∪B（bi）∩ 嗨）≥nXi=1（面积（Hi）- ε） =面积（R）+δ- nε>面积（R）。因此，布莱克有一个获胜的策略，把这些点。这些见解使我们能够证明本节的主要结果。我知道定理9。WnRif，而且只有在布莱克赢得一分的情况下。证据如果黑人获胜，并且他们的得分超过/2·面积（R），那么根据鸽子洞原理，一个黑色单元格的面积超过/2n·面积（R），从而确定一个获胜点。

除此之外，布莱克有一套得分最多为R.BB/2n·area面积一半的决胜局。此外，还有一套布莱克得分超过R.BB/2n·area面积一半的决胜局。证据b在最大/2n·面积（R）处，黑点和白点之间存在中性区和退化平分线。wbxw，byw，B通过选择一个轻微扰动的位置来计算简并度。通过在直角线两侧移动，黑色可以赢得任意ε>0的中性区域。如果中性点的净损失ε>0。然而，由于布莱克获胜，它可以考虑一些净损失ε>0。他们不强迫中立地区。因此，布莱克的得分超过了/2n·面积（R）。C（a）一个左半单元H（b）一个捕捉H的点，直到ε>0。图7引理7证明的图解。T.Byrne，S.P.Fekete，J.Kalcsics，L.Kleist 9bareaVW∪{b} b/2n·面积Δδ>nbn≥N-要点：考虑wi∈ 通过引理8，我们可以假设每个半细胞的面积为/2n·arearwivw∪{b} bLemma 7，黑色可以放置一个点位来捕捉高达每ε>0的区域。选择ε<δ/n-1n-聚丙烯∈巴列夫∪Bp（/2n·面积（R）+δ）n-（/2n·面积（R）- ε） >/2·区域（右）。因此，布莱克有一个获胜的策略。J5不败胜局的属性在本节中，我们确定了不败白局的必要属性，对于这些白局，游戏以平局或白局胜局结束。如果一个细胞有两个相对的边界臂，我们称它为桥。我相信定理11。如果W是矩形中无可比拟的白点集，则它具有以下性质：（P1）W的每半个单元的面积为/2n·面积（R）。（P2）单元长度相等，如果| W |>1，则它们是所有臂中最短的。证据W | W |即（P2）保持为| W |=1。它仍然需要证明| W |的属性（P2）≥2.根据定理9，如果（P2）被违反，则有必要确定一个后退赢点。