Second Price Matching with Complete Allocation and Degree Constraints

Jiaye Wei; Lukas Vogl; Neta Singer; Rom Pinchasi

REVIEW 3 major objections 4 minor 22 references

Second Price Matching with Complete Allocation and Degree Constraints

T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read When every bidder bids on exactly two goods, second-price matching is 9/10-approximable for degree 3 and exact for higher degree.

desk verdict Solid general 2PPM results and d≥4 exact algorithms, but the d=3 proof rests on an unproved (and likely false) cycle/forest decomposition, plus a numerical error in the APX-hardness constant. read the letter →

arxiv 2505.06005 v1 pith:IMOQ5MH5 submitted 2025-05-09 cs.DS cs.CCcs.DM

Rom Pinchasi , Neta Singer , Lukas Vogl , Jiaye Wei This is my paper · ORCID

classification cs.DScs.CCcs.DM MSC 05C7068Q1768W2590C27

keywords second-pricematchingperfectvariant(d2)-regulargraphsapproximationalgorithmsTutte-BergeformulasubmodularmaximizationmatroidconstraintAPX-hardness

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Second-price matching asks for a set of goods $W$ and a set of bidders $S$ such that the bidders not in $S$ can be matched to all goods in $W$, and profit is the number of goods that also have a neighbor in $S$. In general the problem is APX-hard and the best known guarantee is $1/2$. This paper claims that when every bidder bids on exactly two goods and every good is bid on by exactly $d$ bidders, the structure changes completely: for $d\ge 4$ both second-price matching and its perfect-matching variant are solvable exactly in polynomial time, and for $d=3$ the perfect variant is exact while the original admits a $9/10$ approximation. It also proves that the perfect variant is, in general, hard to approximate beyond $1-1/e$ and that the matching $1-1/e$ upper bound is achieved by submodular maximization over a matroid. If the claims hold, degree regularity is a dividing line between computational intractability and polynomial-time solvability for this auction mechanism.

What carries the argument

The load-bearing construction is the auxiliary graph $G'$: since every bidder $b$ has degree 2, it connects exactly two goods, so each bidder becomes the edge between those two goods in $G'$. A matching in $G'$ selects a set $B'$ of bidders whose two neighbors are both profitable; because the matching bidders are disjoint, those goods can still be matched by the remaining bidders. The algorithm finds a maximum matching $M'$ in $G'$ with the blossom algorithm, removes the corresponding bidders, and decomposes what remains into even cycles and a forest; paths between leaves are then harvested, and the leaf-removal claims guarantee every good is covered exactly once. For the $9/10$ bound on $d=3$, the Tutte-Berge formula is applied to the 3-regular auxiliary graph to prove $\nu(G')\ge 2|A|/5$, which yields the target ratio.

What would settle it

Take any (3,2)-regular instance and compute $\nu(G')$; if the optimal 2PPM value ever differs from $|A|/2+\nu(G')$, Theorem 4 fails. More directly, search for a (3,2)-regular input whose leftover graph $H$ contains a 2-core with a vertex of degree 3, since the paper's decomposition requires the 2-core to be a disjoint union of even cycles; the leaf-removal argument would break on that instance.

Watch

Extended reading notes

Core claim

The central discovery is that the hardness of second-price matching disappears when the bidder side is 2-regular. The paper's main theorem states that for input graphs with $\deg(a)=d$ for every good $a$ and $\deg(b)=2$ for every bidder $b$: if $d=3$, a polynomial-time algorithm yields a $9/10$-approximation for 2PM and solves 2PPM exactly; if $d\ge 4$, the algorithm solves both 2PM and 2PPM exactly, with optimal value $n=|A|$. The argument builds an auxiliary graph whose vertices are goods and whose edges are bidders, takes a maximum matching in it, and then augments the chosen bidder set through a cycle-and-path decomposition of the remaining graph. For the perfect variant in the $d=3$ case, the optimal value is characterized by the formula $n/2+\nu(G')$, where $\nu(G')$ is the maximum matching size in the auxiliary graph.

Load-bearing premise

For $d=3$, the proof relies on the assertion that after removing the bidders selected by a maximum matching of the auxiliary graph, the leftover graph splits into vertex-disjoint even cycles and paths that cover every good exactly once; if some leftover graph resisted that decomposition, the construction would not be guaranteed to cover all goods.

Editorial extensions

If this is right

For $(d,2)$-regular inputs with $d\ge 4$, both 2PM and 2PPM are solved exactly in polynomial time, so the optimal value is always $|A|$; every good can be made profitable even when the matching must be perfect.
For $(3,2)$-regular inputs, 2PPM is solved exactly and 2PM is approximated within $9/10$ in polynomial time, improving the previous $1/2$ guarantee on this class.
In general, 2PPM cannot be approximated within $1-1/e+\varepsilon$ unless P=NP, and the submodular-maximization algorithm reaches the matching $1-1/e$ guarantee, so the perfect variant is no easier than max $k$-cover.
2PPM remains APX-hard even with goods of degree 2 or 3 and bidders of degree at most 4, showing that bounded degree alone is not enough; one side must be 2-regular.
When all goods have degree at least $d_A$ and all bidders at most $d_B$, every feasible perfect allocation is a $(1-d_B/d_A)$-approximation, which beats the generic bounds when the gap is large.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The auxiliary-graph reduction may extend to bidders with a fixed number $t>2$ of bids by replacing each bidder with a small gadget in a non-bipartite graph; if so, the tractability boundary would be a function of the bidder's bid count rather than its exact value.
Since the $d=3$ optimum is pinned by the maximum matching number of a 3-regular multigraph, any improvement beyond $9/10$ would have to come from a sharper matching lower bound, not from auction-specific reasoning.
Because the general $1-1/e$ hardness is coverage-based, the regular-degree cases identified here are a rare natural class where the generic submodular hardness does not apply; similar one-sided regularity assumptions may tame other allocation problems.
A direct numerical check on random $(3,2)$-regular instances should show the greedy submodular maximizer trailing the new algorithm on the 10-good tight multigraph; that example is the test case that pins the $9/10$ ratio.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the 2PPM variant and the d≥4 algorithms are real contributions, but the d=3 results rest on a structural claim that is not proven and is probably false as stated, so the paper is not ready as is.

What is good. The general 2PPM story is clean: the Max k-Cover reduction with private and dummy nodes gives the (1−1/e) hardness, and the transversal matroid/submodular reformulation gives the matching upper bound. That part checks out. The exact algorithm for (d,2)-regular graphs with d≥4 is also sound—the Hall arguments work by degree counting, including with parallel edges, and the perfect matching step after removing S is correct. The lower bound on maximum matchings in 3-regular multigraphs (Claim 6) is correct and gives the 9n/10 bound once the exact d=3 formula is established.

The problem is Theorem 4. The proof asserts that H can be partitioned into vertex-disjoint even cycles plus a forest F. But H has no leaves, and the vertices in A\N(B′) have degree 3. If the 2-core of H is a theta graph—two degree-3 A-vertices joined by three internally disjoint paths—no such vertex-disjoint cycle decomposition exists. Maximality of M′ only forbids a B-vertex adjacent to two vertices in A\N(B′); it does not forbid longer theta structures. The text gives no argument excluding them. Since the matching construction and the count N(S)=n/2+ν(G′) both depend on this decomposition, the exact d=3 result and the 9/10 approximation are unsupported. This is a load-bearing gap, not a missing minor detail.

There is also a numerical error in Theorem 2's proof: for 3-regular vertex cover, OPT_VC ≥ n/2, so n/OPT_VC ≤ 2, not 1/2. Correcting it yields the stronger constant 593/594, so the theorem may be recoverable, but the stated derivation of 293/297 is wrong.

Who this is for: people working on matching algorithms, auction revenue, and submodular maximization will find the general 2PPM results and the d≥4 algorithms valuable. I would not cite the d=3 claims until the structural issue is resolved. I would send this to a serious referee, with the message that the d=3 section needs a real proof, not a patch.

Referee Report

3 major / 4 minor

Summary. This paper studies the Second Price Matching problem (2PM) and its perfect-matching variant (2PPM) on degree-constrained bipartite inputs. The main algorithmic claims are: for inputs in which every bidder has degree 2 and every good has degree d, there is an exact polynomial-time algorithm for both 2PM and 2PPM when d≥4; and for d=3, there is an algorithm that solves 2PPM exactly with optimal value n/2+ν(G′), where G′ is an auxiliary graph on the goods, which in turn yields a 9/10 approximation to 2PM. For general 2PPM, the paper gives a (1−1/e)-approximation via submodular maximization over a matroid and proves that this ratio is best possible unless a corresponding Max k-Cover hardness assumption holds. It also proves an APX-hardness result for degree-constrained 2PPM with a stated inapproximability factor of 293/297, and an exact polynomial-time algorithm for the case deg(a)=2 for all a∈A. The proofs combine maximum matching in non-bipartite graphs via the blossom algorithm, the Tutte-Berge formula, Hall's theorem, and a gap-preserving reduction from Max k-Cover.

Significance. If all results were fully established, they would constitute a significant advance: the d≥4 exact algorithm for 2PM and 2PPM is a clean and convincing result, and the (1−1/e) tight characterization of general 2PPM via matroid duality is elegant and valuable. The 9/10 approximation for (3,2)-regular inputs would markedly improve the known 1/2 upper bound for 2PM on these inputs. Strengths of the paper include the explicit auxiliary graph construction, the parameter-free use of the Tutte-Berge formula in the lower bound, the submodularity reformulation, and the explicit gap-preserving reduction for the general 2PPM hardness. However, the d=3 exactness proof rests on a structural decomposition that is asserted without proof and appears inconsistent with the paper's own tight example, and the proof of Theorem 2 contains an arithmetically incorrect inequality. These are load-bearing issues for two of the paper's headline claims, so the paper is not acceptable in its present form.

major comments (3)

[§2.1.1, proof of Theorem 4] The proof begins by asserting that H can be partitioned into vertex-disjoint even cycles and a forest F, and the rest of the construction—the leaf-removal process, Claims 1–4, the path decomposition P_j, and the construction of the A-perfect matching M—depends on this decomposition. The only justification offered is that the maximum degree in H is 3, which is not sufficient: a theta graph has maximum degree 3 and is not a disjoint union of vertex-disjoint cycles plus a forest. More seriously, the asserted decomposition is inconsistent with the authors' own tight example for Claim 6. If G′ is the 10-vertex 3-regular multigraph with ν(G′)=4 and M′ is a maximum matching, then H has exactly two vertices in A of degree 3, all remaining vertices in A of degree 2, and all vertices in B\B′ of degree 2. Thus H has no leaves and its 2-core is the whole graph; it contains a component that is not a cycle and cannot be a forest. For such an input the path/cycle construction is not defined. Since Theorem 4 is used to prove Proposition 5 and then the 9/10 guarantee in Theorem 6, the d=3 part of Theorem 3 is not proved as written. The authors need either a proof of a correct structural statement about the 2-core of H under the maximality of M′, or a different argument for the formula n/2+ν(G′).
[§2.1.1, Claim 2] Independently of the decomposition issue, the proof of Claim 2 asserts that an internal vertex a of a path P removed from F′ has degree 3 in H because its degree in P is 2. This is not justified: if a∈N(B′), then a has degree 2 in H and it can still have degree 2 in P. The subsequent conclusion that a lies in A\N(B′) is used to show that each leaf b of the remaining forest has one neighbor in N(B′) and one in A\N(B′), and this is exactly what the counting argument in Claim 5 needs. The proof requires an additional reason why such an internal vertex cannot belong to N(B′); none is supplied.
[§3.2, proof of Theorem 2] The derivation of the inapproximability ratio 293/297 contains an arithmetic error. The text states: 'Since G is 3-regular, we have 3n = 2m and 3OPT_VC ≥ m, i.e., n/OPT_VC ≤ 1/2.' From 3n=2m and 3OPT_VC≥m one obtains OPT_VC≥n/2, hence n/OPT_VC≤2, not ≤1/2. Consequently the upper bound in inequality (9), namely |U|/OPT_VC ≤ 7/4(1−α)+α, does not follow from the stated hypotheses, and the conclusion α≤293/297 is not established by the displayed argument. The reduction may be salvageable, but the proof of Theorem 2 must be reworked with a correct bound before the stated constant can be accepted.

minor comments (4)

[§2.1.1, paragraph after defining F] The sentence 'a leaf x of F must belong to exactly one of the cycles C_i' is confusing under the claimed vertex-disjoint partition of H into cycles plus a forest; a leaf of the forest cannot also belong to a cycle. This sentence appears to be a typo or a sign that the intended structure is different and should be clarified.
[§2.2 and §3.1] The hardness proof for general 2PPM should state precisely which hardness variant of Max k-Cover is being cited from [10]. If Feige's (1−1/e+ε) inapproximability is stated under a quasi-polynomial-time assumption, then the phrase 'unless P=NP' in Theorem 1 needs a justification or a more careful qualification.
[§2.1.2, proof of Theorem 7] The Hall argument for the multigraph G′′ is terse. Since G′′ may have parallel edges, the text should explicitly say that degrees are counted with multiplicity and that M′′ is a matching in the multigraph, so that each vertex in N(B′) is incident to at most one edge of M′′. The current proof is correct but would benefit from this clarification.
[Throughout] There are several typos and formatting glitches: 'lto' in the proof of Claim 2, '˝' in Section 2.3, 'B{a∈A' in Definition 1, and inconsistent spacing in 'OPTV C'. These should be corrected in a revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central claims are derived from external matching theorems and hardness results, with no fitted input renamed as a prediction.

full rationale

The paper's derivation chain is self-contained against external standards: the auxiliary-graph construction and maximum matching in G' are defined directly from the input graph, and Theorem 4's value n/2 + nu(G') is established via the blossom algorithm and a maximality argument rather than by assuming the conclusion. The 9/10-approximation follows from external Tutte-Berge matching lower bounds on 3-regular graphs, not from a parameter fitted to the same instances. The exact algorithms for d >= 4 rely on Hall's theorem applied to degree counts, and the hardness results reduce from Max k-Cover and 3-regular Vertex Cover using standard gap-preserving reductions. No self-citation carries a load-bearing premise, no uniqueness theorem is imported from the authors' prior work, and no equation is equivalent to its input by construction. The possible concern that the cycle/forest decomposition in Theorem 4 is asserted without proof is a correctness gap, not circularity, and does not meet the standard of a quoted reduction from an output back to an input.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No free parameters or invented entities. The paper rests on standard matching theorems and two hardness assumptions from prior work. The only non-standard structural premise is the cycle/forest decomposition of H in the d=3 proof, which is asserted rather than derived.

assumptions (7)

standard math Tutte-Berge formula for maximum matching size
Used in Claim 6 to lower bound ν(G′) for 3-regular multigraphs, Section 2.1.1.
standard math Hall's theorem
Used to prove existence of A-perfect matchings in H and in G′′, Sections 2.1.2 and 2.3.
standard math Correctness of the blossom algorithm for maximum matching in general (multi)graphs
Used to compute maximum matching in the auxiliary graph G′, Section 2.1.
standard math Greedy (1-1/e) approximation for monotone submodular maximization under a matroid constraint
Used in Section 2.2 for general 2PPM.
domain assumption Feige's hardness of Max k-Cover: no approximation better than 1-1/e unless P=NP
Used in the gap-preserving reduction in Section 3.1.
domain assumption Chlebík-Chlebíková hardness: Vertex Cover on 3-regular graphs is hard to approximate within 100/99
Used in the bounded-degree reduction in Section 3.2.
domain assumption The 2-core of H is a disjoint union of even cycles, with the remaining forest attaching only at A\N(B′)
Asserted at the start of the proof of Theorem 4; not proven explicitly and load-bearing for the d=3 decomposition.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Second Price Matching with Complete Allocation and Degree Constraints." pith.science (2026). https://pith.science/paper/IMOQ5MH5

@misc{pith2026250506005,
  author       = {Pith},
  title        = {Pith review of: Second Price Matching with Complete Allocation and Degree Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IMOQ5MH5}},
  note         = {Machine review of arXiv:2505.06005}
}

abstract

We study the Second Price Matching problem, introduced by Azar, Birnbaum, Karlin, and Nguyen in 2009. In this problem, a bipartite graph (bidders and goods) is given, and the profit of a matching is the number of matches containing a second unmatched bidder. Maximizing profit is known to be APX-hard and the current best approximation guarantee is $1/2$. APX-hardness even holds when all degrees are bounded by a constant. In this paper, we investigate the approximability of the problem under regular degree constraints. Our main result is an improved approximation guarantee of $9/10$ for Second Price Matching in $(3,2)$-regular graphs and an exact polynomial-time algorithm for $(d,2)$-regular graphs if $d\geq 4$. Our algorithm and its analysis are based on structural results in non-bipartite matching, in particular the Tutte-Berge formula coupled with novel combinatorial augmentation methods. We also introduce a variant of Second Price Matching where all goods have to be matched, which models the setting of expiring goods. We prove that this problem is hard to approximate within a factor better than $(1-1/e)$ and show that the problem can be approximated to a tight $(1-1/e)$ factor by maximizing a submodular function subject to a matroid constraint. We then show that our algorithm also solves this problem exactly on regular degree constrained graphs as above.

Figures

Figures reproduced from arXiv: 2505.06005 by the authors.

**Figure 1.** Instance of 2PPM where all edges correspond to weight 1 bids on the goods of A. The perfect matching taken corresponds to the set of red edges, the unmatched nodes are shaded in blue, and the profit gained by the second highest bidder per good is the set of blue edges. As the matching is perfect over the 6 nodes of A, and there exists 6 blue edges of second price bids, the profit gained here is 6 which is maximum po… view at source ↗

**Figure 2.** The construction of the auxiliary graph G′ 1The construction of G′ requires no degree constraints on A. 6 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** A tight example of 3-regular graph G (with multiple edges) with 𝜈 (G) = 2|V (G)|/5. One of the maximum matchings in G is colored in red. We have shown that through the auxiliary graph G′ , we are able to solve for an optimal solution to 2PPM on (3, 2)-regular graphs. We may now conclude the first part of Theorem 3 by showing that this solution is also a 9/10-approximation of the optimum for 2PM . Theorem 6. There ex… view at source ↗

Figures from the paper (7 more)

**Figure 4.** Figure 4: An example of the construction of the auxiliary graph [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]

**Figure 5.** Figure 5: An instance Iof Max k-Cover formulated as a bipartite graph: the part on top represents the set of elements U and the part at bottom represents the set of subsets S. From the given instance I, we construct an instance G of the Second Price Perfect Matching as follows. …

**Figure 6.** Figure 6: N copies of U all with the same connections to S. Proof of Claim. We first prove that OPT2PPM ≥ N · OPTMC + (m − k). Start with an optimal solution of the Max k-Cover instance I, which is a sub-collection T ⊆ S of size k. Construct the A-perfect matching by matching ea…

**Figure 7.** Figure 7: Add a “private" node for each u in all N copies of Uand m −k dummies connected completely to S. hence we conclude that it is NP-hard to approximate the Second Price Perfect Matching within a factor (1 − 1/e + 𝜀) for any 𝜀 > 0. 3.2 APX-Hardness of Degree-Constrained 2PP…

**Figure 8.** Figure 8: An instance G = K4 of Vertex Cover problem on 3-regular graphs. bv1 bv2 bv3 bv4 a 1 v1 b 1 v1 a 2 v1 b 2 v1 a 1 v2 b 1 v2 a 2 v2 b 2 v2 a 1 v3 b 1 v3 a 2 v3 b 2 v3 a 1 v4 b 1 v4 a 2 v4 b 2 v4 be1 ae1 be2 ae2 be3 ae3 be4 ae4 be5 ae5 be6 ae6 [PITH_FULL_IMAGE:figures/ful…

**Figure 9.** Figure 9: The construction of instance G′ of Second Price Perfect Matching, based on the instance G = K4 of 3-regular Vertex Cover shown in [PITH_FULL_IMAGE:figures/full_fig_p018_9.png]

**Figure 10.** Figure 10: The last step of transformation from M to M′ . By applying the transformation described above to an optimal solution S ⊆ B of Second Price Perfect Matching, we get a vertex cover U of G. The nodes in A that are covered by the unsaturated nodes in B are {ae : e ∈ E} ∪ …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 20 canonical work pages

[1]

Online vertex-weighted bipartite matching and single-bid budgeted allocations

Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1253–1264. SIAM, 2011

work page 2011
[2]

Auctions with budget constraints

Nir Andelman and Yishay Mansour. Auctions with budget constraints. In Scandinavian Workshop on Algorithm Theory, pages 26–38. Springer, 2004

work page 2004
[3]

Improved approximation algorithms for budgeted allocations

Yossi Azar, Benjamin Birnbaum, Anna R Karlin, Claire Mathieu, and C Thach Nguyen. Improved approximation algorithms for budgeted allocations. In International Colloquium on Automata, Lan- guages, and Programming, pages 186–197. Springer, 2008

work page 2008
[4]

Karlin, and C

Yossi Azar, Benjamin Birnbaum, Anna R. Karlin, and C. Thach Nguyen. On revenue maximiza- tion in second-price ad auctions. In Amos Fiat and Peter Sanders, editors,Algorithms - ESA 2009, pages 155–166, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg

work page 2009
[5]

Online primal-dual algorithms for maximizing ad-auctions revenue

Niv Buchbinder, Kamal Jain, and Joseph Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms, pages 253–264. Springer, 2007

2007
[6]

Maximizing a submodular set function subject to a matroid constraint

Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to a matroid constraint. In International Conference on Integer Programming and Combinatorial Optimization, pages 182–196. Springer, 2007

work page 2007
[7]

On the approximability of budgeted allocations and im- proved lower bounds for submodular welfare maximization and gap.SIAM Journal on Computing, 39(6):2189–2211, 2010

Deeparnab Chakrabarty and Gagan Goel. On the approximability of budgeted allocations and im- proved lower bounds for submodular welfare maximization and gap.SIAM Journal on Computing, 39(6):2189–2211, 2010

work page 2010
[8]

Complexity of approximating bounded variants of opti- mization problems

Miroslav Chlebík and Janka Chlebíková. Complexity of approximating bounded variants of opti- mization problems. Theoretical Computer Science, 354(3):320–338, 2006. Foundations of Compu- tation Theory (FCT 2003)

work page 2006

Show all 22 references

[9]

Internet advertising and the gen- eralized second-price auction: Selling billions of dollars worth of keywords

Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the gen- eralized second-price auction: Selling billions of dollars worth of keywords. American economic review, 97(1):242–259, 2007

2007
[10]

A threshold of ln n for approximating set cover

Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634–652, July 1998

1998
[11]

Second-price ad auctions with binary bids and markets with good competition

Cristina G Fernandes and Rafael CS Schouery. Second-price ad auctions with binary bids and markets with good competition. Theoretical Computer Science, 540:103–114, 2014

2014
[12]

Approximation algorithms for budget- constrained auctions

Rahul Garg, Vijay Kumar, and Vinayaka Pandit. Approximation algorithms for budget- constrained auctions. In International Workshop on Randomization and Approximation Techniques in Computer Science, pages 102–113. Springer, 2001

2001
[13]

An improved approximation guarantee for the maximum budgeted allocation problem

Christos Kalaitzis. An improved approximation guarantee for the maximum budgeted allocation problem. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1048–1066. SIAM, 2016. 21

2016
[14]

Inapproximability results for combinatorial auctions with submodular utility functions

Subhash Khot, Richard J Lipton, Evangelos Markakis, and Aranyak Mehta. Inapproximability results for combinatorial auctions with submodular utility functions. In International Workshop on Internet and Network Economics, pages 92–101. Springer, 2005

2005
[15]

Combinatorial auctions with decreasing marginal utilities

Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. In Proceedings of the 3rd ACM conference on Electronic Commerce , pages 18–28, 2001

2001
[16]

3-regular graph maximum matching.https://math.stackexchange

Mattias and Misha Lavrov. 3-regular graph maximum matching.https://math.stackexchange. com/questions/3410007/3-regular-graph-maximum-matching . Mathematics Stack Exchange, version: 2025-03-27

2025
[17]

Online matching and ad allocation

Aranyak Mehta et al. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science, 8(4):265–368, 2013

2013
[18]

Adwords and generalized online matching

Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22–es, 2007

2007
[19]

Combinatorial Optimization: Polyhedra and Efficiency

Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer Berlin, Heidel- berg, 2003

2003
[20]

Budgeted allocations in the full-information setting

Aravind Srinivasan. Budgeted allocations in the full-information setting. InInternational Workshop on Approximation Algorithms for Combinatorial Optimization, pages 247–253. Springer, 2008

2008
[21]

Position auctions

Hal R Varian. Position auctions. international Journal of industrial Organization, 25(6):1163–1178, 2007

2007
[22]

Optimal approximation for the submodular welfare problem in the value oracle model

Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 67–74, 2008. 22

2008

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Online vertex-weighted bipartite matching and single-bid budgeted allocations

Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1253–1264. SIAM, 2011

work page 2011

[2] [2]

Auctions with budget constraints

Nir Andelman and Yishay Mansour. Auctions with budget constraints. In Scandinavian Workshop on Algorithm Theory, pages 26–38. Springer, 2004

work page 2004

[3] [3]

Improved approximation algorithms for budgeted allocations

Yossi Azar, Benjamin Birnbaum, Anna R Karlin, Claire Mathieu, and C Thach Nguyen. Improved approximation algorithms for budgeted allocations. In International Colloquium on Automata, Lan- guages, and Programming, pages 186–197. Springer, 2008

work page 2008

[4] [4]

Karlin, and C

Yossi Azar, Benjamin Birnbaum, Anna R. Karlin, and C. Thach Nguyen. On revenue maximiza- tion in second-price ad auctions. In Amos Fiat and Peter Sanders, editors,Algorithms - ESA 2009, pages 155–166, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg

work page 2009

[5] [5]

Online primal-dual algorithms for maximizing ad-auctions revenue

Niv Buchbinder, Kamal Jain, and Joseph Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms, pages 253–264. Springer, 2007

2007

[6] [6]

Maximizing a submodular set function subject to a matroid constraint

Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to a matroid constraint. In International Conference on Integer Programming and Combinatorial Optimization, pages 182–196. Springer, 2007

work page 2007

[7] [7]

On the approximability of budgeted allocations and im- proved lower bounds for submodular welfare maximization and gap.SIAM Journal on Computing, 39(6):2189–2211, 2010

Deeparnab Chakrabarty and Gagan Goel. On the approximability of budgeted allocations and im- proved lower bounds for submodular welfare maximization and gap.SIAM Journal on Computing, 39(6):2189–2211, 2010

work page 2010

[8] [8]

Complexity of approximating bounded variants of opti- mization problems

Miroslav Chlebík and Janka Chlebíková. Complexity of approximating bounded variants of opti- mization problems. Theoretical Computer Science, 354(3):320–338, 2006. Foundations of Compu- tation Theory (FCT 2003)

work page 2006