Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e

No abstract is available for this paper.

• Publication year

  2006

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2006-10-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FOCS.2006.14
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On maximizing welfare when utility functions are subadditive

  2006influential reference
• Tight approximation algorithms for maximum general assignment problems

  2006cited by this paper
• An improved approximation algorithm for combinatorial auctions with submodular bidders

  2006influential reference
• Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions

  2005cited by this paper
• Approximation algorithms for combinatorial auctions with complement-free bidders

  2005cited by this paper
• Truth revelation in approximately efficient combinatorial auctions

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

  2001cited by this paper
• Truth revelation in rapid, approximately efficient combinatorial auctions

  2001cited by this paper
• Approximating the domatic number

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

  2000cited by this paper
• Fair Division: From Cake-Cutting to Dispute Resolution

  1996cited by this paper
• An approximation algorithm for the generalized assignment problem

  1993cited by this paper
• Winner Dete rmina t ion i n Combina tor ia l Auct ions

  year unknowncited by this paper

• Scheduling Problems with Constrained Rejections

  2025influential citation
• An exact solver for submodular knapsack problems

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

  2025cites this paper
• Improved Online Load Balancing in the Two-Norm

  2025cites this paper
• Data Auctions for Retrieval Augmented Generation

  2025influential citation
• Dynamic Detection and Classification of Critical Attention Objects under Crisis Events

  2025cites this paper
• Pandora's box problem with time constraints

  2024cites this paper
• Decomposable Submodular Maximization in Federated Setting

  2024cites this paper
• Pandora's Box Problem Over Time

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

  2024cites this paper
• Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization

  2024cites this paper
• Mini-batch Submodular Maximization

  2024cites this paper
• Pairwise-Independent Contention Resolution

  2024cites this paper
• On contention resolution for the hypergraph matching, knapsack, and k-column sparse packing problems

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

  2023cites this paper
• Cut Sparsification and Succinct Representation of Submodular Hypergraphs

  2023cites this paper
• Cost-Aware Joint Caching and Forwarding in Networks with Heterogeneous Cache Resources

  2023cites this paper
• Size-stochastic Knapsack Online Contention Resolution Schemes

  2023cites this paper
• Dependent Rounding with Strong Negative-Correlation, and Scheduling on Unrelated Machines to Minimize Completion Time

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

  2023cites this paper
• Constrained Submodular Maximization via New Bounds for DR-Submodular Functions

  2023cites this paper
• Uncertainty with UAV Search of Multiple Goal-oriented Targets

  2022cites this paper
• Sparsification of Decomposable Submodular Functions

  2022cites this paper
• Simplicity in Auctions Revisited: The Primitive Complexity

  2022cites this paper
• Maximizing Modular plus Non-monotone Submodular Functions

  2022cites this paper
• Approximation algorithm for generalized budgeted assignment problems and applications in transportation systems

  2022cites this paper
• Online and Bandit Algorithms Beyond $\ell_p$ Norms

  2022cites this paper
• Approximation Algorithms for Capacitated Assignment with Budget Constraints and Applications in Transportation Systems

  2022cites this paper
• CS 583: Approximation Algorithms

  2021cites this paper
• Dynamic VM Scaling: Provisioning and Pricing through an Online Auction

  2021cites this paper
• Primal-Dual Algorithms for Indivisible Concave Allocation with Bounded Local Curvature

  2021cites this paper
• A Simple Optimal Contention Resolution Scheme for Uniform Matroids

  2021cites this paper
• An Optimal Monotone Contention Resolution Scheme for Uniform and Partition Matroids

  2021influential citation
• Mobility-Aware Computation Offloading in Edge Computing Using Machine Learning

  2021cites this paper
• Online Combinatorial Auctions

  2021cites this paper
• A 0.3622-Approximation Algorithm for the Maximum k-Edge-Colored Clustering Problem

  2020cites this paper
• Display Optimization for Vertically Differentiated Locations Under Multinomial Logit Preferences

  2020cites this paper
• Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier

  2020cites this paper
• Sensitivity Analysis of Submodular Function Maximization

  2020cites this paper
• Differentially Private Decomposable Submodular Maximization

  2020cites this paper
• Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution

  2020influential citation
• A Generic Truthful Mechanism for Combinatorial Auctions

  2020cites this paper
• Combinatorial Auctions Do Need Modest Interaction

  2020cites this paper
• A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function

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

  2019cites this paper
• Online Truthful Mechanisms for Combinatorial Auctions

  2019cites this paper
• Joint patient selection and scheduling under no‐shows: Theory and application in proton therapy

  2019cites this paper
• Generalized Assignment via Submodular Optimization with Reserved Capacity

  2019cites this paper
• Distributed approximation of k-service assignment

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

  2019cites this paper
• XX : 2 Generalized Assignment via Submodular Optimization bins

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

  2019cites this paper
• Approximability and Inapproximability for Maximum k-Edge-Colored Clustering Problem

  2019cites this paper
• On the approximability of the two-phase knapsack problem

  2019cites this paper
• Beyond submodular maximization via one-sided smoothness

  2019cites this paper
• Submodular Maximization Under A Matroid Constraint: Asking more from an old friend, the Greedy Algorithm

  2018cites this paper
• Combinatorial Auctions with Endowment Effect

  2018influential citation
• Approximation Algorithms for a Two-Phase Knapsack Problem

  2018cites this paper
• Multiagent Coverage Problems : The Trade-off Between Anarchy and Stability

  2018cites this paper
• Combinatorial Optimization On Massive Datasets: Streaming, Distributed, And Massively Parallel Computation

  2018cites this paper
• A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints

  2018cites this paper
• Generalized Assignment of Time-Sensitive Item Groups

  2018cites this paper
• A General Framework for Bounding Approximate Dynamic Programming Schemes

  2018cites this paper
• On the Network Visibility Problem

  2018cites this paper
• Optimization for Approximate Submodularity

  2018cites this paper
• Non-submodular Function Maximization subject to a Matroid Constraint, with Applications

  2018cites this paper
• UAV/UGV Search and Capture of Goal-Oriented Uncertain Targets*This research was supported in part by ISF grant #1337/15 and part by a grant from MOST, Israel and the JST Japan

  2018cites this paper
• The risks and rewards of conditioning noncooperative designs to additional information

  2017cites this paper
• Combinatorial Auctions Do Need Modest Interaction

  2017cites this paper
• Multiagent Maximum Coverage Problems: The Trade-off Between Anarchy and Stability

  2017cites this paper
• The Impact of Local Information on the Performance of Multiagent Systems

  2017cites this paper
• Allocations in Large Markets

  2017cites this paper
• Submodular Memetic Approximation for Multiobjective Parallel Test Paper Generation

  2017cites this paper
• Approximating Geometric Knapsack via L-Packings

  2017cites this paper
• The Role of Information in Distributed Resource Allocation

  2017cites this paper
• Oracle-based algorithms for optimizing sophisticated decision criteria in sequential, robust and fair decision problems

  2017cites this paper
• Approximation Algorithms for Rectangle Packing Problems (PhD Thesis)

  2017cites this paper
• Flexible Resource Allocation for Network Problems

  2017cites this paper
• The Importance of System-Level Information in Multiagent Systems Design: Cardinality and Covering Problems

  2017cites this paper
• Fair Allocation of Indivisible Goods: Improvements and Generalizations

  2017cites this paper
• Beating 1-1/e for ordered prophets

  2017cites this paper
• Submodular Optimization under Noise

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

  2016cites this paper
• Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding

  2016cites this paper
• Constrained Submodular Maximization via a Non-symmetric Technique

  2016cites this paper
• Flexible Cell Selection in Cellular Networks

  2016cites this paper
• Computational Efficiency Requires Simple Taxation

  2016cites this paper
• Algorithms for Scheduling and Routing Problems

  2016cites this paper
• Performance Bounds with Curvature for Batched Greedy Optimization

  2016cites this paper
• Resource Allocation for elastic traffic in mobilenetworks shared by multiple operators

  2015cites this paper
• The hypergraph assignment problem

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

  2015cites this paper
• Collective Biobjective Optimization Algorithm for Parallel Test Paper Generation

  2015cites this paper
• On Lagrangian Relaxation and Reoptimization Problems

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

  2015cites this paper
• Efficient Use of Exponential Size Linear Programs

  2015cites this paper
• Performance bounds for the k-batch greedy strategy in optimization problems with curvature

  2015cites this paper
• Packing items into several bins facilitates approximating the separable assignment problem

  2015cites this paper
• Approximability of Two Variants of Multiple Knapsack Problems

  2015cites this paper
• A polynomial-time approximation scheme for the airplane refueling problem

  2015cites this paper