Cover Image

A Strongly Polynomial Algorithm for Arctic Auctions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Garg, Jugal, Taherijam, Shayan, Vazirani, Vijay V
Format:	Preprint
Published:	2026
Subjects:	Computer Science and Game Theory Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fair Rent Division: New Budget and Rent Constraints
by: Gangam, Rohith Reddy, et al.
Published: (2025)

Arctic Auctions, Linear Fisher Markets, and Rational Convex Programs
by: Vazirani, Vijay V.
Published: (2025)

A Generalization of von Neumann's Reduction from the Assignment Problem to Zero-Sum Games
by: Adler, Ilan, et al.
Published: (2024)

Improved MMS Approximations for Few Agent Types
by: Garg, Jugal, et al.
Published: (2025)

Approximating Nash Social Welfare by Matching and Local Search
by: Garg, Jugal, et al.
Published: (2022)

Prophet Upper Bounds for Online Matching and Auctions
by: Soto, José, et al.
Published: (2024)

Repeated Descent: A Framework for Online Budget-Feasible Auctions
by: Charalampopoulos, Andreas, et al.
Published: (2026)

A Competitive Posted-Price Mechanism for Online Budget-Feasible Auctions
by: Charalampopoulos, Andreas, et al.
Published: (2025)

Truthful, Credible, and Optimal Auctions for Matroids via Blockchains and Commitments
by: Ganesh, Aadityan, et al.
Published: (2025)

Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids
by: Eden, Alon, et al.
Published: (2024)

Complexity of Auctions with Interdependence
by: Loiseau, Patrick, et al.
Published: (2026)

Fairness and Efficiency in Online Class Matching
by: Hajiaghayi, MohammadTaghi, et al.
Published: (2024)

Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More
by: Bowers, Robin, et al.
Published: (2025)

Bi-Criteria Metric Distortion
by: Banihashem, Kiarash, et al.
Published: (2024)

Algorithmic Persuasion with Evidence
by: Hoefer, Martin, et al.
Published: (2020)

On the Core of the $b$-Matching Game
by: Gangam, Rohith Reddy, et al.
Published: (2025)

Online Combinatorial Allocations and Auctions with Few Samples
by: Dütting, Paul, et al.
Published: (2024)

Improved Parallel Algorithms for EF1 Allocations
by: Gowda, Kishen N, et al.
Published: (2026)

Strategizing against No-Regret Learners in First-Price Auctions
by: Rubinstein, Aviad, et al.
Published: (2024)

Procurement Auctions via Approximately Optimal Submodular Optimization
by: Deng, Yuan, et al.
Published: (2024)

An Algorithm-to-Contract Framework without Demand Queries
by: Doron-Arad, Ilan, et al.
Published: (2025)

Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem
by: Glitzner, Frederik, et al.
Published: (2024)

Combinatorial Pen Testing (or Consumer Surplus of Deferred-Acceptance Auctions)
by: Ganesh, Aadityan, et al.
Published: (2023)

The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
by: Cesa-Bianchi, Nicolò, et al.
Published: (2023)

Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
by: Bei, Xiaohui, et al.
Published: (2025)

Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms
by: Ezra, Tomer, et al.
Published: (2024)

Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three
by: Pashkovich, Kanstantsin, et al.
Published: (2026)

Bipartiteness in Progressive Second-Price Multi-Auction Networks with Perfect Substitute
by: Blazek, Jordana, et al.
Published: (2025)

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
by: Golrezaei, Negin, et al.
Published: (2024)

Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs
by: Brown, Adam, et al.
Published: (2024)

Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning
by: Podimata, Chara, et al.
Published: (2020)

Computing a Fixed Point of Contraction Maps in Polynomial Queries
by: Chen, Xi, et al.
Published: (2024)

Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems
by: Kevi, Eniko, et al.
Published: (2024)

Weighted Proportional Allocations of Indivisible Goods and Chores: Insights via Matchings
by: V., Vishwa Prakash H., et al.
Published: (2023)

Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings
by: Cheng, Christine T., et al.
Published: (2026)

A Minimax Perspective on Almost-Stable Matchings
by: Glitzner, Frederik, et al.
Published: (2026)

A symmetric recursive algorithm for mean-payoff games
by: Ohlmann, Pierre
Published: (2026)

A Little Aggression Goes a Long Way
by: Krishnan, Jyothi, et al.
Published: (2024)

MATWA: A Web Toolkit for Matching under Preferences
by: Glitzner, Frederik, et al.
Published: (2024)

A Reduction from Chores Allocation to Job Scheduling
by: Huang, Xin, et al.
Published: (2023)