Research map / Learning theory and algorithms / Submodular and game algorithms
Optimizing Multiple Simultaneous Objectives for Voting and Facility Location
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Choose one of the objective-optimal locations O_k or O_p rather than a single weighted-sum objective | Facility location with two l-centrum objectives · Two l-centrum objectives, general metric | simultaneous approximation ratio: 1+√2 | Helped |
| Keep the two objective indices closer (smaller p/k) | Facility location with two l-centrum objectives · Two l-centrum objectives | simultaneous approximation ratio: f(1) = 1; f(∞) = 1 + √2 | Helped |
| Optimize q objectives by selecting one of their objective-optimal locations | Facility location with q l-centrum objectives · q l-centrum objectives, general metric | simultaneous approximation ratio: β_q < 3 | Helped |
| Select the sum-optimal location O_n | Facility location with all l-centrum objectives · All l-centrum objectives, general metric | simultaneous approximation ratio: 3 | Helped |
| Restrict facilities to client locations | Facility location with multiple l-centrum objectives · Arbitrarily many l-centrum objectives, C = F | simultaneous approximation ratio: 3 to 2 | Helped |
| Restrict facilities to client locations | Facility location with two l-centrum objectives · Two l-centrum objectives, p/k > 4, C = F | simultaneous approximation ratio: 2 | Helped |
| Increase the number of simultaneous objectives | Facility location with q l-centrum objectives · q l-centrum objectives, general metric | simultaneous approximation ratio: β_2 = 1 + √2; β_q approaches 3 | Hurt |
| Consider three objectives instead of two | Facility location with l-centrum objectives · Three objectives {1, k, n}, constructed instance | worst simultaneous approximation ratio: β_3 = 1/2(3 + √5) | Hurt |
Closest papers by meaning
- Spatial Voting with Incomplete Voter Information (AAAI 2024 · similarity 0.87)
- Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems (AAAI 2024 · similarity 0.85)
- Facility Location Games with Optional Preferences: A Revisit (AAAI 2025 · similarity 0.85)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.85)
- Nearly Tight Bounds on Approximate Equilibria in Spatial Competition on the Line (AAAI 2025 · similarity 0.85)
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.