On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP

No abstract is available for this paper.

• Publication year

  2008

• Venue

  2008 49th Annual IEEE Symposium on Foundations of Computer Science

• Publication date

  2008-10-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/080735503
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximation Algorithms

  2021cited by this paper
• Optimal approximation for the submodular welfare problem in the value oracle model

  2008cited by this paper
• Budgeted Allocations in the Full-Information Setting

  2008cited by this paper
• Improved Approximation Algorithms for Budgeted Allocations

  2008cited by this paper
• Algorithmic Game Theory: Combinatorial Auctions

  2007cited by this paper
• Survivable network design with degree or order constraints

  2007cited by this paper
• Approximating the spanning star forest problem and its applications to genomic sequence alignment

  2007cited by this paper
• Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue

  2007cited by this paper
• Combinatorial auctions

  2007cited by this paper
• Tight approximation algorithms for maximum general assignment problems

  2006cited by this paper
• Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e

  2006cited by this paper
• Online and strategic aspects of network resource management algorithms

  2006cited by this paper
• Side constraints and non-price attributes in markets

  2006cited by this paper
• Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions

  2005cited by this paper
• AdWords and generalized on-line matching

  2005cited by this paper
• Auctions with Budget Constraints

  2004cited by this paper
• Approximation Hardness for Small Occurrence Instances of NP-Hard Problems

  2003cited by this paper
• Approximation Hardness of the Steiner Tree Problem on Graphs

  2002cited by this paper
• Randomized metarounding

  2002cited by this paper
• Some optimal inapproximability results

  2001cited by this paper
• Approximation Algorithms for Budget-Constrained Auctions

  2001cited by this paper
• Combinatorial auctions with decreasing marginal utilities

  2001cited by this paper
• Approximation Algorithms

  2001cited by this paper
• A PTAS for the multiple knapsack problem

  2000influential reference
• Multiple-Object Auctions with Budget Constrained Bidders

  1998cited by this paper
• A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem

  1998influential reference
• An approximation algorithm for the generalized assignment problem

  1993cited by this paper
• Approximation algorithms for scheduling unrelated parallel machines

  1987cited by this paper
• Combinatorial Auctions

  year unknowncited by this paper

• Optimal Online Bipartite Matching in Degree-2 Graphs

  2025cites this paper
• Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems

  2025cites this paper
• Scheduling Problems with Constrained Rejections

  2025cites this paper
• Second Price Matching with Complete Allocation and Degree Constraints

  2025cites this paper
• To Trust or Not to Trust: Assignment Mechanisms with Predictions in the Private Graph Model

  2024cites this paper
• A unified embedding-based relation completion framework for knowledge graph

  2024cites this paper
• The Average-Value Allocation Problem

  2024cites this paper
• Approximations for Indivisible Concave Allocations with Applications to Nash Welfare Maximization

  2023influential citation
• No Ascending Auction can find Equilibrium for SubModular valuations

  2023cites this paper
• A Primal-Dual Analysis of Monotone Submodular Maximization

  2023cites this paper
• A Tight Competitive Ratio for Online Submodular Welfare Maximization

  2023cites this paper
• Designing Approximately Optimal Search on Matching Platforms

  2021influential citation
• Online Matching in Advertisement Auctions ∗

  2021cites this paper
• Approximations for Allocating Indivisible Items with Concave-Additive Valuations

  2021influential citation
• APPROXIMATION ALGORITHMS FOR A GENERALIZATION OF THE MAXIMUM BUDGET ALLOCATION

  2021influential citation
• Primal-Dual Algorithms for Indivisible Concave Allocation with Bounded Local Curvature

  2021influential citation
• On the Max-Min Fair Stochastic Allocation of Indivisible Goods

  2020cites this paper
• Local Search Algorithms for the Maximum Carpool Matching Problem

  2020cites this paper
• AdWords in a Panorama

  2020cites this paper
• Earning and Utility Limits in Fisher Markets

  2019cites this paper
• Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders

  2019cites this paper
• Approximation Algorithms for Submodular Maximization and Network Design Problems

  2019cites this paper
• On the star forest polytope for trees and cycles

  2019cites this paper
• Complexity and approximability of extended Spanning Star Forest problems in general and complete graphs

  2019cites this paper
• A General Framework for Endowment Effects in Combinatorial Markets

  2019cites this paper
• D S ] 1 4 O ct 2 01 8 Maximizing Stochastic Monotone Submodular Functions by using Test Scores

  2018cites this paper
• Revenue Maximization and Ex-Post Budget Constraints

  2018influential citation
• A Simple Mechanism for a Budget-Constrained Buyer

  2018cites this paper
• Combinatorial Auctions with Endowment Effect

  2018cites this paper
• Weighted Upper Edge Cover: Complexity and Approximability

  2018cites this paper
• Throughput-Efficient Channel Allocation Algorithms in Multi-Channel Cognitive Vehicular Networks

  2017cites this paper
• Extended Spanning Star Forest Problems

  2017cites this paper
• Satiation in Fisher Markets and Approximation of Nash Social Welfare

  2017cites this paper
• Segmenting Two-Sided Markets

  2017influential citation
• Approximating the Nash Social Welfare with Budget-Additive Valuations

  2017influential citation
• Computing Equilibria in Markets with Budget-Additive Utilities

  2016cites this paper
• Generalized assignment problem: Truthful mechanism design without money

  2016cites this paper
• Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders

  2016cites this paper
• Algorithms for Scheduling and Routing Problems

  2016cites this paper
• Group-Aware Weighted Bipartite B-Matching

  2016cites this paper
• Social network ad allocation and optimization: a geometric mapping-based approach

  2016cites this paper
• The maximum weight spanning star forest problem on cactus graphs

  2015cites this paper
• An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem

  2015cites this paper
• On the Greedy Algorithm for Combinatorial Auctions with a Random Order

  2015cites this paper
• Truthful mechanism design via correlated tree rounding

  2015cites this paper
• Sponsored Search Auctions

  2015cites this paper
• Revenue Maximization and Ex-Post Budget Constraints

  2015influential citation
• X Revenue Maximization and Ex-Post Budget Constraints

  2015influential citation
• Efficient Use of Exponential Size Linear Programs

  2015cites this paper
• On the configuration LP for maximum budgeted allocation

  2014cites this paper
• J an 2 01 4 Clearing Markets via Bundles

  2014influential citation
• Throughput-efficient channel allocation in multi-channel cognitive vehicular networks

  2014cites this paper
• A Truthful Mechanism for the Generalized Assignment Problem

  2014influential citation
• Clearing Markets via Bundles

  2014cites this paper
• A Truthful-in-Expectation Mechanism for the Generalized Assignment Problem

  2014cites this paper
• On the Complexity of Computing an Equilibrium in Combinatorial Auctions

  2014cites this paper
• Cellular multi-coverage with non-uniform rates

  2014cites this paper
• Competitive Algorithms for Ad Allocation in Cellular Networks ( AdCell ) ?

  2014cites this paper
• Truthful Generalized Assignments via Stable Matching

  2014cites this paper
• Approximation for maximizing monotone non-decreasing set functions with a greedy method

  2014cites this paper
• String Submodular Functions With Curvature Constraints

  2013cites this paper
• A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation

  2013cites this paper
• Limitations of Deterministic Auction Design for Correlated Bidders

  2013cites this paper
• Near optimality of greedy strategies for string submodular functions with forward and backward curvature constraints

  2013cites this paper
• How to Sell Hyperedges: The Hypermatching Assignment Problem

  2013cites this paper
• Combinatorial walrasian equilibrium

  2013influential citation
• Communication Complexity of Combinatorial Auctions with Submodular Valuations

  2013cites this paper
• Online Matching and Ad Allocation

  2013cites this paper
• MATHEMATICAL ENGINEERING TECHNICAL REPORTS Valuated Matroid-Based Algorithm for Submodular Welfare Problem

  2013cites this paper
• Online Submodular Welfare Maximization: Greedy is Optimal

  2012influential citation
• Improved approximation for spanning star forest in dense graphs

  2012cites this paper
• On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations

  2012cites this paper
• Second-Price Ad Auctions with Binary Bids and Markets with Good Competition

  2012cites this paper
• Online Matching with Stochastic Rewards

  2012cites this paper
• Allocation problems with partial information

  2012influential citation
• Submodular and Linear Maximization with Knapsack Constraints

  2011cites this paper
• AdCell: Ad Allocation in Cellular Networks

  2011influential citation
• On Variants of the Spanning Star Forest Problem

  2011cites this paper
• Iterative Methods in Combinatorial Optimization: Bibliography

  2011influential citation
• Lecture : Online Matching and Adwords June 16 , 2011

  2011cites this paper
• A Unified Continuous Greedy Algorithm for Submodular Maximization

  2011cites this paper
• Limitations of Randomized Mechanisms for Combinatorial Auctions

  2011cites this paper
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

  2011cites this paper
• An Improved Approximation Algorithm for Spanning Star Forest in Dense Graphs

  2010cites this paper
• Online Stochastic Packing Applied to Display Ad Allocation

  2010cites this paper
• Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations

  2010cites this paper
• Linear Programming Tools and Approximation Algorithms for Combinatorial Optimization

  2010cites this paper
• A new approximation technique for resource‐allocation problems

  2010cites this paper
• Multiarmed Bandit Problems with Delayed Feedback

  2010cites this paper
• Selective Call Out and Real Time Bidding

  2010cites this paper
• The Submodular Welfare Problem with Demand Queries

  2010cites this paper
• Iterated Allocations with Delayed Feedback

  2010cites this paper
• An Improved Approximation Bound for Spanning Star Forest and Color Saving

  2009cites this paper
• Online Ad Assignment with Free Disposal

  2009cites this paper
• On Revenue Maximization in Second-Price Ad Auctions

  2009influential citation
• Approximability of Sparse Integer Programs

  2009cites this paper
• Offline Optimization for Online Ad Allocation [ Extended

  2009cites this paper
• Approximating the Spanning k-Tree forest Problem

  2009influential citation
• Algorithms for budgeted auctions and multi-agent covering problems

  2009influential citation
• Online Stochastic Matching: Beating 1-1/e

  2009cites this paper