• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar

information for practice

news, new scholarship & more from around the world


advanced search
  • gary.holden@nyu.edu
  • @ Info4Practice
  • Archive
  • About
  • Help
  • Browse Key Journals
  • RSS Feeds

Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions

Abstract

We consider the facility location problem in two dimensions. In particular, we consider a setting where agents have Euclidean preferences, defined by their ideal points, for a facility to be located in

(mathbb {R}^2)

. We show that for the p–norm (

(p ge 1)

) objective, the coordinate-wise median mechanism (CM) has the lowest worst-case approximation ratio in the class of deterministic, anonymous, and strategyproof mechanisms. For the minisum objective and an odd number of agents n, we show that CM has a worst-case approximation ratio (AR) of

(sqrt{2}frac{sqrt{n^2+1}}{n+1})

. For the p–norm social cost objective (

(pge 2)

), we find that the AR for CM is bounded above by

(2^{frac{3}{2}-frac{2}{p}})

. We conjecture that the AR of CM actually equals the lower bound

(2^{1-frac{1}{p}})

(as is the case for

(p=2)

and

(p=infty)

) for any

(pge 2)

.

Read the full article ›

Posted in: Journal Article Abstracts on 11/01/2022 | Link to this post on IFP |
Share

Primary Sidebar

Categories

Category RSS Feeds

  • Calls & Consultations
  • Clinical Trials
  • Funding
  • Grey Literature
  • Guidelines Plus
  • History
  • Infographics
  • Journal Article Abstracts
  • Meta-analyses - Systematic Reviews
  • Monographs & Edited Collections
  • News
  • Open Access Journal Articles
  • Podcasts
  • Video

© 1993-2023 Dr. Gary Holden. All rights reserved.

gary.holden@nyu.edu
@Info4Practice