Compatibility of Max and Sum Objectives for Committee Selection and $k$-Facility Location

• URL: http://arxiv.org/abs/2507.17063v1
• Date: Tue, 22 Jul 2025 22:47:35 GMT
• Title: Compatibility of Max and Sum Objectives for Committee Selection and $k$-Facility Location
• Authors: Yue Han, Elliot Anshelevich,
• Abstract summary: We consider four different objectives, where each client tries to minimize either the sum or the maximum of its distance to the chosen facilities.<n>Rather than optimizing a single objective at a time, we study how compatible these objectives are with each other.<n>Our results show that when choosing a set of facilities or a representative committee, it is often possible to form a solution which is good for several objectives at the same time.
• Score: 12.43373306175797
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a version of the metric facility location problem (or, equivalently, variants of the committee selection problem) in which we must choose $k$ facilities in an arbitrary metric space to serve some set of clients $C$. We consider four different objectives, where each client $i\in C$ attempts to minimize either the sum or the maximum of its distance to the chosen facilities, and where the overall objective either considers the sum or the maximum of the individual client costs. Rather than optimizing a single objective at a time, we study how compatible these objectives are with each other, and show the existence of solutions which are simultaneously close-to-optimum for any pair of the above objectives. Our results show that when choosing a set of facilities or a representative committee, it is often possible to form a solution which is good for several objectives at the same time, instead of sacrificing one desideratum to achieve another.

Related papers

• Standardization of Multi-Objective QUBOs [2.285821277711785]
  Multi-objective optimization involving Quadratic Unconstrained Binary Optimization (QUBO) problems arises in various domains.<n>We propose a novel technique for scaling QUBO objectives that uses an exact computation of the variance of each individual QUBO objective.
  arXiv  Detail & Related papers  (2025-04-16T18:35:07Z)
• Covering Multiple Objectives with a Small Set of Solutions Using Bayesian Optimization [7.504371299651926]
  A motivating example for this problem setting occurs in drug design.<n>We propose Multi-Objective Coverage Bayesian Optimization (MOCOBO), a principled algorithm designed to efficiently find a covering set.<n>The results show that the coverage of the K T solutions found by MOCOBO matches or nearly matches the coverage of T solutions obtained by optimizing each objective individually.
  arXiv  Detail & Related papers  (2025-01-31T17:43:30Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  We consider a multi-armed bandit setting in which each arm yields an $M$-dimensional vector reward upon selection.<n>The end goal is to identify the best arm of em every objective in the shortest (expected) time subject to an upper bound on the probability of error.<n>We propose an algorithm that uses the novel idea of em surrogate proportions to sample the arms at each time step, eliminating the need to solve the max-min optimisation problem at each step.
  arXiv  Detail & Related papers  (2025-01-23T12:28:09Z)
• Decoding-Time Language Model Alignment with Multiple Objectives [116.42095026960598]
  Existing methods primarily focus on optimizing LMs for a single reward function, limiting their adaptability to varied objectives. Here, we propose $textbfmulti-objective decoding (MOD)$, a decoding-time algorithm that outputs the next token from a linear combination of predictions. We show why existing approaches can be sub-optimal even in natural settings and obtain optimality guarantees for our method.
  arXiv  Detail & Related papers  (2024-06-27T02:46:30Z)
• Many-Objective Multi-Solution Transport [36.07360460509921]
  Many-objective multi-solution Transport (MosT) is a framework that finds multiple diverse solutions in the Pareto front of many objectives. MosT formulates the problem as a bi-level optimization of weighted objectives for each solution, where the weights are defined by an optimal transport between the objectives and solutions.
  arXiv  Detail & Related papers  (2024-03-06T23:03:12Z)
• Facility Location Games with Scaling Effects [63.421996606381164]
  We take the classic facility location problem and consider a variation in which each agent's individual cost function is equal to their distance from the facility multiplied by a scaling factor.<n>We focus on the objectives of total and maximum cost, describing the computation of the optimal solution.<n>We characterize the conditions on scaling functions which ensure that agents have single-peaked preferences.
  arXiv  Detail & Related papers  (2024-02-29T07:08:18Z)
• Multi-Target Multiplicity: Flexibility and Fairness in Target Specification under Resource Constraints [76.84999501420938]
  We introduce a conceptual and computational framework for assessing how the choice of target affects individuals' outcomes. We show that the level of multiplicity that stems from target variable choice can be greater than that stemming from nearly-optimal models of a single target.
  arXiv  Detail & Related papers  (2023-06-23T18:57:14Z)
• Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback [76.7007545844273]
  We propose a multi-objective decision making framework that accommodates different user preferences over objectives. Our model consists of a Markov decision process with a vector-valued reward function, with each user having an unknown preference vector. We suggest an algorithm that finds a nearly optimal policy for the user using a small number of comparison queries.
  arXiv  Detail & Related papers  (2023-02-07T23:58:19Z)
• Knowledge Gradient for Multi-Objective Bayesian Optimization with Decoupled Evaluations [0.0]
  In some cases, it is possible to evaluate the objectives separately, and a different latency or evaluation cost can be associated with each objective.<n>We propose a scalarization based knowledge acquisition function which accounts for the different evaluation costs of the objectives.
  arXiv  Detail & Related papers  (2023-02-02T18:33:34Z)
• Optimizing Multiple Simultaneous Objectives for Voting and Facility Location [7.0579376123869935]
  We study the classic facility location setting, where we are given $n$ clients and $m$ possible facility locations in some arbitrary metric space. We consider the $l$-centrum family of objectives, which includes the total distance, max distance, and many others.
  arXiv  Detail & Related papers  (2022-12-07T05:12:40Z)
• Alleviating Search Bias in Bayesian Evolutionary Optimization with Many Heterogeneous Objectives [9.139734850798124]
  We deal with multi-objective optimization problems with heterogeneous objectives (HE-MOPs) A new acquisition function that mitigates search bias towards the fast objectives is suggested. We demonstrate the effectiveness of the proposed algorithm by testing it on widely used multi-/many-objective benchmark problems.
  arXiv  Detail & Related papers  (2022-08-25T17:07:40Z)
• Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functions [74.00030431081751]
  We formalize the notion of user-specific cost functions and introduce a new method for identifying actionable recourses for users. Our method satisfies up to 25.89 percentage points more users compared to strong baseline methods.
  arXiv  Detail & Related papers  (2021-11-01T19:49:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.