Proportionality from Sampled Approvals

Gregory Kehne

REVIEW 2 major objections 2 minor 300 references

Proportionality from Sampled Approvals

T0 review · 2 major / 2 minor · reviewed 2026-06-27 · grok-4.3

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

Pith's one-line read A new sampling rule achieves justified representation in committee selection with Õ(k^4 log m/δ) approval ballots.

desk verdict The paper cuts JR sample complexity to Õ(k^4 log m/δ) and separates it from CC's Θ(k^5) requirement under i.i.d. sampling. read the letter →

arxiv 2606.10446 v1 pith:N3JOB4TT submitted 2026-06-09 cs.GT cs.DS

Gregory Kehne This is my paper · ORCID

classification cs.GTcs.DS

keywords justifiedrepresentationsamplecomplexitymultiwinnervotingapprovalballotsproportionalitycommitteeselectionChamberlin-Courant

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

The paper studies the number of randomly drawn approval ballots needed to select a proportional k-candidate committee with high probability over the draws. Standard adaptations of rules satisfying justified representation require Õ(k^5 log m/δ) samples. The authors give a rule that succeeds with only Õ(k^4 log m/δ) samples and prove that additive approximations to the Chamberlin-Courant coverage objective still need Θ(k^5 log m/δ) samples. They also show that Ω(k^3) samples are necessary in the worst case over instances with polynomially many candidates and failure probability, and that a logarithmic dependence on the number of candidates cannot be avoided.

What carries the argument

A sample-based committee selection rule that outputs a JR committee from independently drawn approval ballots with the stated high-probability guarantee.

What would settle it

A concrete instance with m and 1/δ polynomial in k on which the presented rule outputs a non-JR committee with probability greater than δ after drawing the claimed number of ballots.

Watch

Extended reading notes

Core claim

The paper establishes a sampling rule for which the sample complexity of JR-family proportional committee selection is Õ(k^4 log m/δ). This separates the sample complexity of JR from that of the natural corresponding additive approximation to the voter coverage (Chamberlin-Courant) objective, which requires Θ(k^5 log m/δ) samples. For lower bounds, a family of instances with m and 1/δ polynomial in k requires Ω(k^3) sampled ballots to identify a JR committee, and a dependence on log m is necessary.

Load-bearing premise

Approval ballots are drawn independently and uniformly at random from an underlying population distribution.

Editorial extensions

If this is right

JR proportionality can be achieved with asymptotically fewer samples than additive approximation of the Chamberlin-Courant objective.
Ω(k^3) samples are necessary in the worst case even when m and 1/δ are polynomial in k.
A logarithmic dependence on m is required for any rule to succeed with high probability.
No finite number of samples suffices for the stronger Droop JR axiom with high probability.
Mild relaxations of JR and certain beyond-worst-case domains require fewer samples.

Reading between the lines

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

The separation suggests that proportionality axioms can sometimes be easier to certify from samples than direct coverage objectives.
In real-world approval data the required sample sizes may be even smaller than the worst-case bounds indicate.
The lower-bound technique may extend to other proportionality notions such as PSC for ranked ballots beyond the cases already shown.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The main thing here is a new sampling rule that gets justified representation with high probability from only Õ(k^4 log m/δ) approval ballots, down from the prior Õ(k^5) bound. It also shows that additive approximation to the Chamberlin-Courant objective needs the full Θ(k^5) samples, and it gives Ω(k^3) lower bounds plus a log m dependence that carries over to PSC on ranked ballots.

The construction and the separation are the actual advances. The upper bound follows from applying concentration to empirical approval frequencies on the sample, and the lower bounds come from explicit instance families where m and 1/δ are polynomial in k. The paper is clear that stronger Droop versions of JR and PSC cannot be guaranteed no matter how many samples you take.

The central limitation is the i.i.d. sampling model. Every concentration step relies on it, so the claimed gap between JR and CC disappears if samples can be chosen adversarially or dependently. That modeling choice is stated in the abstract, so it is not concealed. The beyond-worst-case experiments are mentioned but not the focus.

This is for people working on sample-efficient proportionality in multiwinner voting. The arguments look technically standard rather than flashy, with no circularity. It deserves peer review because the separation and the concrete bounds are new and falsifiable.

Referee Report

2 major / 2 minor

Summary. The paper claims that a new sampling-based rule achieves Õ(k^4 log m/δ) sample complexity for selecting a k-committee satisfying the JR proportionality axiom with high probability over i.i.d. draws from an underlying approval distribution, improving on Õ(k^5 log m/δ) for standard JR rules. It establishes a separation by showing that additive approximation of the Chamberlin-Courant objective requires Θ(k^5 log m/δ) samples. Lower bounds prove Ω(k^3) samples and log m dependence are necessary for JR (with m, 1/δ polynomial in k), extend to PSC on ranked ballots, show impossibility for Droop JR/PSC, and evaluate that mild relaxations and beyond-worst-case domains require fewer samples.

Significance. If the proofs hold, the work is significant for tightening sample-complexity bounds on proportionality in multiwinner voting under sampling and for the explicit separation from a related optimization objective. The versatile lower-bound construction (applicable to both JR and PSC) and the impossibility result for Droop variants are notable strengths, as is the explicit invocation of concentration inequalities under the i.i.d. model to obtain high-probability guarantees.

major comments (2)

Abstract and the section defining the new rule: the central separation between the Õ(k^4) JR upper bound and the Θ(k^5) CC lower bound is load-bearing; the manuscript must explicitly identify the section proving the CC lower bound and confirm that the additive approximation is defined with respect to the same i.i.d. sampling model used for the JR upper bound.
The section containing the Ω(k^3) lower-bound construction: the family of instances with m, 1/δ ∈ poly(k) is used to show that Ω(k^3) samples are necessary to identify a JR committee w.h.p.; the proof must verify that the construction forces any sampled rule to fail JR on the true distribution with constant probability when fewer than that many ballots are drawn.

minor comments (2)

The abstract refers to 'JR-family' without a forward reference; the precise family of axioms should be defined in the model or preliminaries section.
The evaluation on real approval preferences would benefit from a table listing the datasets, number of candidates, and observed sample sizes needed in practice.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thoughtful review and recommendation for minor revision. We address each major comment below and will incorporate the necessary clarifications into the revised manuscript.

read point-by-point responses

Referee: Abstract and the section defining the new rule: the central separation between the Õ(k^4) JR upper bound and the Θ(k^5) CC lower bound is load-bearing; the manuscript must explicitly identify the section proving the CC lower bound and confirm that the additive approximation is defined with respect to the same i.i.d. sampling model used for the JR upper bound.

Authors: We agree with this observation. The CC lower bound is proved in Section 5 of the manuscript. In the revision, we will explicitly reference this section both in the abstract and in the section defining the new rule. We will also add a statement confirming that the additive approximation to the Chamberlin-Courant objective uses the identical i.i.d. sampling model from the underlying approval distribution as the JR upper bound. revision: yes
Referee: The section containing the Ω(k^3) lower-bound construction: the family of instances with m, 1/δ ∈ poly(k) is used to show that Ω(k^3) samples are necessary to identify a JR committee w.h.p.; the proof must verify that the construction forces any sampled rule to fail JR on the true distribution with constant probability when fewer than that many ballots are drawn.

Authors: The lower bound construction is presented in Section 4. We will revise the proof to include an explicit verification step showing that, with o(k^3) samples, there exists a constant probability that the sampled ballots lead to a committee violating JR with respect to the true distribution. This follows from the fact that the construction ensures insufficient samples fail to identify the necessary candidates with high enough probability. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; derivation relies on independent concentration bounds and explicit instance constructions

full rationale

The paper derives sample-complexity upper and lower bounds via standard Chernoff/Hoeffding inequalities applied to an explicitly stated i.i.d. sampling model, plus explicit adversarial instance families for the Ω(k^3) lower bound. No equation or claim reduces by construction to a fitted parameter, self-definition, or self-citation chain; the i.i.d. assumption is an input modeling choice, not an output derived from the results. The separation between JR and CC sample complexities follows directly from the differing approximation guarantees and is not forced by renaming or ansatz smuggling.

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

The paper relies on standard probabilistic tools and the random sampling model common in computational social choice; no free parameters or new entities are introduced in the abstract.

assumptions (2)

standard math Standard concentration inequalities (e.g., Chernoff bounds) for independent random samples
Used to guarantee high probability success with the given sample sizes.
domain assumption Existence of a population distribution over approval ballots from which samples are drawn
Central to the sampling model for multiwinner elections.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Proportionality from Sampled Approvals." pith.science (2026). https://pith.science/paper/N3JOB4TT

@misc{pith2026260610446,
  author       = {Pith},
  title        = {Pith review of: Proportionality from Sampled Approvals},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N3JOB4TT}},
  note         = {Machine review of arXiv:2606.10446}
}

abstract

How much voter input is necessary in order to ensure representation in multiwinner elections? If voters are randomly selected from an underlying population, how many draws are necessary to find a proportional committee of $k$ candidates, with high probability? Sample-based adaptations of standard multiwinner voting rules that satisfy the justified representation (JR) proportionality axiom use $\tilde O(k^5 \log \frac{m}{\delta})$ sampled approval ballots over $m$ candidates, where $\delta$ is a probability of failure and $\tilde O$ suppresses $\mathrm{polylog}(k)$ factors. We present a rule for which the sample complexity of JR-family proportional committee selection is $\tilde O(k^{4}\log \frac{m}{\delta})$. This separates the sample complexity of JR from that of the natural corresponding additive approximation to the voter coverage (Chamberlin-Courant) objective, which we show requires $\Theta(k^5\log \frac{m}{\delta})$ samples. For lower bounds, we present a family of instances with $m, \frac{1}{\delta} \in \mathrm{poly}(k)$ for which $\Omega(k^3)$ sampled ballots are necessary in order to identify a JR committee. We also show a dependence on $\log m$ is necessary. This lower bound is versatile, and also applies to Hare proportionality for solid coalitions (PSC) for ranked ballots. Unfortunately, no number of sampled ballots suffices to satisfy the slightly stronger Droop JR and Droop PSC axioms with high probability. But mild relaxations of JR require fewer samples, as do the beyond-worst-case domains and actual approval preferences we evaluate.

Figures

Figures reproduced from arXiv: 2606.10446 by the authors.

**Figure 1.** The partition profile Ii. Here C = [k + 1], each approval set is Aj = {j}, and Pi(Aj ) is below each bloc. A1 1 k+1 − ε/k A2 1 k+1 − ε/k . . . Ai 1 k+1 + ε . . . Ak+1 1 k+1 − ε/k [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗

**Figure 3.** Success probability of satisfying JR and EJR+ for various rules on approvals from the “Poland Warszawa 2017 rejon B” participatory budgeting election, as the number of samples increases. Empirical probabilities are out of 500 trials for various rules selecting a committee of size k = 12, out of 53 candidates overall. For each instance, we created 500 ballot samples At for t = 10, 20, . . . , 250 approval ballots uni… view at source ↗

**Figure 4.** Success probability of satisfying JR and EJR+ for various rules on approvals from the “Poland Warszawa 2017 rejon B” participatory budgeting election, for even k up to k = 30, out of 53 candidates overall. Empirical probabilities are out of 500 trials for various rules from n = 50 samples. relative to AV. One possible explanation is that sets of multiple candidates with high but highly correlated support are prevale… view at source ↗

Figures from the paper (5 more)

**Figure 5.** Figure 5: Success probability of satisfying JR and EJR+ for various rules on approvals from the “Poland Warszawa 2022 Mokotów” participatory budgeting election, as the number of samples increases. Empirical probabilities are out of 500 trials for various rules selecting a commit…

**Figure 6.** Figure 6: Success probability of satisfying JR and EJR+ for various rules on approvals from the “Netherlands Amsterdam 622” participatory budgeting election, as the number of samples increases. Empirical probabilities are out of 500 trials for various rules selecting a committee…

**Figure 7.** Figure 7: Success probability of satisfying JR and EJR+ for various rules on approvals from the “Netherlands Amsterdam 621” participatory budgeting election, as the number of samples increases. Empirical probabilities are out of 500 trials for various rules selecting a committee…

**Figure 8.** Figure 8: Success probability of satisfying JR and EJR+ for various rules on approvals from the “Netherlands Amsterdam 631” participatory budgeting election, as the number of samples increases. Empirical probabilities are out of 500 trials for various rules selecting a committee…

**Figure 9.** Figure 9: Success probability of satisfying JR and EJR+ for various rules on approvals from the “Poland Warszawa 2017 rejon B” participatory budgeting election, as the number of samples increases. Empirical probabilities are out of 500 trials each for committee sizes k ∈ {10, 20…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

300 extracted references · 3 canonical work pages

[1]

PhD thesis, Charles University, Prague, Czech Republic , year =

Submodularity in combinatorial optimization , author =. PhD thesis, Charles University, Prague, Czech Republic , year =
[2]

Jakulin, Aleks , journal =
[3]

1985 , publisher =

A simple probabilistic approximation algorithm for vertex cover , author =. 1985 , publisher =

1985
[4]

Master's thesis, Weizmann Institute of Science, Rehovot, Israel , year =

On the use of randomization in the online set cover problem , author =. Master's thesis, Weizmann Institute of Science, Rehovot, Israel , year =
[5]

Polyhedral Combinatorics: Dedicated to the memory of D.R

An analysis of approximations for maximizing submodular set functions---II. Polyhedral Combinatorics: Dedicated to the memory of D.R. Fulkerson. 1978

1978
[6]

1988 , publisher =

Tsallis, Constantino , journal = jsp, volume =. 1988 , publisher =

1988
[7]

Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences , volume =

Cand\`. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences , volume =. 2006 , publisher =

2006
[8]

Sayan Bhattacharya and Janardhan Kulkarni , title =

Show all 300 references

[9]

What To Do With Your Free Time: Algorithms for Infrequent Requests and Randomized Weighted Caching , author =
[10]

Competitive analysis of paging: A survey , author =. Proc. of the Dagstuhl Seminar on Online Algorithms , year =
[11]

David Peleg and Shay Solomon , title =
[12]

Bertinoro workshop 2014, problem 63 , howpublished =

2014
[13]

2007 , publisher =

Submodularity in combinatorial optimization , author =. 2007 , publisher =

2007
[14]

ACM Trans

Andreev, Konstantin and Garrod, Charles and Golovin, Daniel and Maggs, Bruce and Meyerson, Adam , title =. ACM Trans. Algorithms , issue_date =. 2009 , issn =

2009
[15]

Approximate and incremental network function placement

Tam\'as Lukovszki and Matthias Rost and Stefan Schmid. Approximate and incremental network function placement. 2018

2018
[16]

Samir Khuller and Jian Li and Barna Saha , title =
[17]

Poularakis and G

K. Poularakis and G. Iosifidis and G. Smaragdakis and L. Tassiulas , booktitle = infocom, title =. 2017 , volume =

2017
[18]

Wolsey, L. A. An analysis of the greedy algorithm for the submodular set covering problem. 1982

1982
[19]

IEICE Transactions on Information and Systems , volume =

Approximation algorithms for submodular set cover with applications , author =. IEICE Transactions on Information and Systems , volume =. 2000 , publisher =

2000
[20]

2011 , publisher =

The design of approximation algorithms , author =. 2011 , publisher =

2011
[21]

Goyal, Amit and Bonchi, Francesco and Lakshmanan, Laks V. S. and Venkatasubramanian, Suresh. On minimizing budget and time in influence propagation over social networks. Social Network Analysis and Mining. 2013

2013
[22]

Data Science and Advanced Analytics (DSAA), 2016 IEEE International Conference on , pages =

Limiting the diffusion of information by a selective PageRank-preserving approach , author =. Data Science and Advanced Analytics (DSAA), 2016 IEEE International Conference on , pages =. 2016 , organization =

2016
[23]

IEEE Journal on Selected Areas in Communications , volume =

Trading data in the crowd: Profit-driven data acquisition for mobile crowdsensing , author =. IEEE Journal on Selected Areas in Communications , volume =. 2017 , publisher =

2017
[24]

Robust submodular observation selection , author =
[25]

ACM SIGCOMM Computer Communication Review , volume =

It's a match!: Near-optimal and incremental middlebox deployment , author =. ACM SIGCOMM Computer Communication Review , volume =. 2016 , publisher =

2016
[26]

Decision and Control (CDC), 2017 IEEE 56th Annual Conference on , pages =

The risk-sensitive coverage problem: Multi-robot routing under uncertainty with service level and survival constraints , author =. Decision and Control (CDC), 2017 IEEE 56th Annual Conference on , pages =. 2017 , organization =

2017
[27]

2018 IEEE 26th International Conference on Network Protocols (ICNP) , pages =

Virtual Network Function Deployment in Tree-structured Networks , author =. 2018 IEEE 26th International Conference on Network Protocols (ICNP) , pages =. 2018 , organization =

2018
[28]

, author =

Robust landmark selection for mobile robot navigation. , author =. IROS , pages =
[29]

IEEE Transactions on Control of Network Systems , volume =

Minimal actuator placement with bounds on control effort , author =. IEEE Transactions on Control of Network Systems , volume =. 2016 , publisher =

2016
[30]

Optimization Letters , volume =

On positive-influence target-domination , author =. Optimization Letters , volume =. 2017 , publisher =

2017
[31]

Liu and A

Z. Liu and A. Clark and P. Lee and L. Bushnell and D. Kirschen and R. Poovendran , booktitle =. MinGen: Minimal generator set selection for small signal stability in power systems: A submodular framework , year =
[32]

A. D. Mafuta and T. Walingo , booktitle =. Spatial Relay Node Placement in Wireless Sensor Networks , year =
[33]

Yang and L

Y. Yang and L. Chen and W. Dong and W. Wang , journal =. Active Base Station Set Optimization for Minimal Energy Consumption in Green Cellular Networks , year =
[34]

, author =

Detection and Isolation of Failures in Directed Networks of LTI Systems. , author =. IEEE Trans. Control of Network Systems , volume =
[35]

American Control Conference (ACC), 2015 , pages =

Minimal actuator placement with optimal control constraints , author =. American Control Conference (ACC), 2015 , pages =. 2015 , organization =

2015
[36]

Approximability and inapproximability of the minimum certificate dispersal problem

Tomoko Izumi and Taisuke Izumi and Hirotaka Ono and Koichi Wada. Approximability and inapproximability of the minimum certificate dispersal problem. 2010

2010
[37]

Minimizing receivers under link coverage model for device-free surveillance

Pan Wu and Guihai Chen and Xiaojun Zhu and Xiaobing Wu. Minimizing receivers under link coverage model for device-free surveillance. Computer Communications. 2015

2015
[38]

International Workshop on Graph-Theoretic Concepts in Computer Science , pages =

Approximating source location and star survivable network problems , author =. International Workshop on Graph-Theoretic Concepts in Computer Science , pages =. 2015 , organization =

2015
[39]

, title =

Hochbaum, D. , title =. 1982 , eprint =

1982
[40]

2005 , publisher =

Approximation algorithms facility location problems , author =. 2005 , publisher =

2005
[41]

1984 , publisher =

Covering problems , author =. 1984 , publisher =

1984
[42]

2009 , publisher =

An Online Algorithm for Maximizing Submodular Functions , author =. 2009 , publisher =

2009
[43]

2011 , publisher =

Online Submodular Set Cover, Ranking, and Repeated Active Learning , author =. 2011 , publisher =

2011
[44]

Adaptive submodularity: Theory and applications in active learning and stochastic optimization , author =
[45]

ACM Trans

Deshpande, Amol and Hellerstein, Lisa and Kletenik, Devorah , title =. ACM Trans. Algorithms , issue_date =. 2016 , issn =

2016
[46]

Revisiting the Approximation Bound for Stochastic Submodular Cover , author =
[47]

International Workshop on Approximation and Online Algorithms , pages =

Scenario submodular cover , author =. International Workshop on Approximation and Online Algorithms , pages =. 2016 , organization =

2016
[48]

2019 , organization =

Stochastic submodular cover with limited adaptivity , author =. 2019 , organization =

2019
[49]

Mathematics of Operations Research , volume =

Online primal-dual algorithms for covering and packing , author =. Mathematics of Operations Research , volume =. 2009 , publisher =

2009
[50]

2009 , publisher =

The online set cover problem , author =. 2009 , publisher =

2009
[51]

2020 , organization =

The online submodular cover problem , author =. 2020 , organization =

2020
[52]

2014 , organization =

Changing bases: Multistage optimization for matroids and matchings , author =. 2014 , organization =

2014
[53]

A note on concentration of submodular functions , journal =

Jan Vondr. A note on concentration of submodular functions , journal =. 2010 , eprinttype =

2010
[54]

Ehsani Banafati, Soheil , title =
[55]

2003 , publisher =

Combinatorial optimization: polyhedra and efficiency , author =. 2003 , publisher =

2003
[56]

Mathematics of Operations Research , volume =

Approximating sparse covering integer programs online , author =. Mathematics of Operations Research , volume =. 2014 , publisher =

2014
[57]

2014 , organization =

Competitive algorithms for restricted caching and matroid caching , author =. 2014 , organization =

2014
[58]

Handbook of Approximation Algorithms and Metaheuristics , volume =

Submodular Functions Maximization Problems , author =. Handbook of Approximation Algorithms and Metaheuristics , volume =
[59]

Operations Research Letters , volume =

A note on maximizing a submodular set function subject to a knapsack constraint , author =. Operations Research Letters , volume =. 2004 , publisher =

2004
[60]

Nemhauser, G. L. and Wolsey, L. A. and Fisher, M. L. An analysis of approximations for maximizing submodular set functions---I. Mathematical Programming. 1978

1978
[61]

Fisher, M. L. and Nemhauser, G. L. and Wolsey, L. A. An analysis of approximations for maximizing submodular set functions---II. Polyhedral Combinatorics: Dedicated to the memory of D.R. Fulkerson. 1978

1978
[62]

2008 , organization =

Set covering with our eyes closed , author =. 2008 , organization =

2008
[63]

Fabrizio Grandoni and Anupam Gupta and Stefano Leonardi and Pauli Miettinen and Piotr Sankowski and Mohit Singh , title =
[64]

Theory of Computing , volume =

The multiplicative weights update method: a meta-algorithm and applications , author =. Theory of Computing , volume =. 2012 , publisher =

2012
[65]

2019 , organization =

k-Servers with a smile: Online algorithms via projections , author =. 2019 , organization =

2019
[66]

1998 , publisher =

Feige, Uriel , journal = jacm, volume =. 1998 , publisher =

1998
[67]

2014 , isbn =

Dinur, Irit and Steurer, David , title =. 2014 , isbn =

2014
[68]

Mathematics of operations research , volume =

A greedy heuristic for the set-covering problem , author =. Mathematics of operations research , volume =. 1979 , publisher =

1979
[69]

1974 , publisher =

Approximation algorithms for combinatorial problems , author =. 1974 , publisher =

1974
[70]

2018 , organization =

Greedy algorithms for online survivable network design , author =. 2018 , organization =

2018
[71]

Beyond the Worst-Case Analysis of Algorithms , pages =

Random-order models , author =. Beyond the Worst-Case Analysis of Algorithms , pages =. 2020 , publisher =

2020
[72]

Statistical science , volume =

Who solved the secretary problem? , author =. Statistical science , volume =. 1989 , publisher =

1989
[73]

2011 , publisher =

Introduction to stochastic programming , author =. 2011 , publisher =

2011
[74]

Primal beats dual on online packing LPs in the random-order model , author =
[75]

2001 , organization =

Online facility location , author =. 2001 , organization =

2001
[76]

2001 , organization =

Designing networks incrementally , author =. 2001 , organization =

2001
[77]

ACM Transactions on Algorithms (TALG) , volume =

A general approach to online network optimization problems , author =. ACM Transactions on Algorithms (TALG) , volume =. 2006 , publisher =

2006
[78]

Discrete & Computational Geometry , volume =

Almost optimal set covers in finite VC-dimension , author =. Discrete & Computational Geometry , volume =. 1995 , publisher =

1995
[79]

2021 , organization =

Constrained-order prophet inequalities , author =. 2021 , organization =

2021
[80]

A sub-constant error-probability low-degree test, and a sub-constant error-probability

Raz, Ran and Safra, Shmuel , booktitle = stoc, publisher =. A sub-constant error-probability low-degree test, and a sub-constant error-probability. 1997 , pages =

1997
[81]

2014 , publisher =

Submodular function maximization via the multilinear relaxation and contention resolution schemes , author =. 2014 , publisher =

2014
[82]

2009 , organization =

On maximum coverage in the streaming model & application to multi-topic blog-watch , author =. 2009 , organization =

2009
[83]

Shipra Agrawal and Zizhuo Wang and Yinyu Ye , title =
[84]

Marco Molinaro , title =
[85]

Anupam Gupta and Marco Molinaro , title =. Math. Oper. Res. , year =
[86]

Devanur , title =

Shipra Agrawal and Nikhil R. Devanur , title =
[87]

, title =

Molinaro, Marco and Ravi, R. , title =. Math. Oper. Res. , fjournal =. 2014 , number =

2014
[88]

Discrete mathematics , volume =

On the ratio of optimal integral and fractional covers , author =. Discrete mathematics , volume =. 1975 , publisher =

1975
[89]

2014 , publisher =

On streaming and communication complexity of the set cover problem , author =. 2014 , publisher =

2014
[90]

Towards tight bounds for the streaming set cover problem , author =
[91]

ACM Transactions on Algorithms (TALG) , volume =

Semi-streaming set cover , author =. ACM Transactions on Algorithms (TALG) , volume =. 2016 , publisher =

2016
[92]

2020 , organization =

Scheduling in the Random-Order Model , author =. 2020 , organization =

2020
[93]

Algorithmica , volume =

Improved Online Algorithms for Knapsack and GAP in the Random Order Model , author =. Algorithmica , volume =. 2021 , publisher =

2021
[94]

2014 , publisher =

Michele Conforti and G. 2014 , publisher =

2014
[95]

Naveen Garg and Anupam Gupta and Stefano Leonardi and Piotr Sankowski , title =
[96]

Haim Kaplan and David Naori and Danny Raz , title =
[97]

Probability on Banach spaces , volume =

On semiamarts, amarts, and processes with finite value , author =. Probability on Banach spaces , volume =. 1978 , publisher =

1978
[98]

A survey of prophet inequalities in optimal stopping theory , author =. Contemp. Math , volume =
[99]

Argue and Alan Frieze and Anupam Gupta and Christopher Seiler , title =

C.J. Argue and Alan Frieze and Anupam Gupta and Christopher Seiler , title =
[100]

Haris Aziz and Markus Brill and Vincent Conitzer and Edith Elkind and Rupert Freeman and Toby Walsh , title =. Soc. Choice Welf. , volume =
[101]

Markus Brill and Jannik Peters , title =
[102]

Sonja Kraiczy and Edith Elkind , title =
[103]

Quantitative Projection Coverage for Testing ML-enabled Autonomous Systems , booktitle =

Chih. Quantitative Projection Coverage for Testing ML-enabled Autonomous Systems , booktitle =
[104]

, year =

Thiele, Thorvald N. , year =. Om Flerfoldsvalg , booktitle =
[105]

Adam Breuer and Eric Balkanski and Yaron Singer , title =
[106]

Wei Chen and Xiaoming Sun and Jialin Zhang and Zhijie Zhang , title =
[107]

Conference on Learning Theory , pages =

Information complexity in bandit subset selection , author =. Conference on Learning Theory , pages =. 2013 , publisher =

2013
[108]

Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining , pages =

Optimal distributed submodular optimization via sketching , author =. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining , pages =
[109]

Tight space-approximation tradeoff for the multi-pass streaming set cover problem , author =
[110]

Conference on Learning Theory , pages =

Learning coverage functions and private release of marginals , author =. Conference on Learning Theory , pages =. 2014 , publisher =

2014
[111]

Piotr Skowron and Piotr Faliszewski , title =
[112]

Pasin Manurangsi , title =
[113]

Uriel Feige , title =
[114]

CoRR , volume =

Lirong Xia , title =. CoRR , volume =. 2025 , eprinttype =

2025
[115]

Oliver Johnson and Lampros Gavalakis and Ioannis Kontoyiannis , title =. J. Appl. Probab. , volume =
[116]

CoRR , volume =

Johannes Brustle and Simone Fioravanti and Tomasz Ponitka and Jeremy Vollen , title =. CoRR , volume =. 2504.20508 , year =
[117]

Yusuf Hakan Kalayci and Jiasen Liu and David Kempe , title =
[118]

Generative Social Choice , booktitle = ec, pages =

Sara Fish and Paul G. Generative Social Choice , booktitle = ec, pages =
[119]

2023 , publisher =

Multi-winner voting with approval preferences , author =. 2023 , publisher =

2023
[120]

Approval-Based Committee Voting in Practice:

Niclas Boehmer and Markus Brill and Alfonso Cevallos and Jonas Gehrlein and Luis S. Approval-Based Committee Voting in Practice:
[121]

Piotr Faliszewski and Martin Lackner and Krzysztof Sornat and Stanislaw Szufa , title =
[122]

Robust Committee Voting, or The Other Side of Representation , author =
[123]

Procaccia and Jamie Tucker

Daniel Halpern and Gregory Kehne and Ariel D. Procaccia and Jamie Tucker. Representation with Incomplete Votes , booktitle = aaai, pages =
[124]

Statistics & Probability Letters , volume =

Tail bounds for sums of geometric and exponential variables , author =. Statistics & Probability Letters , volume =. 2018 , publisher =

2018
[125]

An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation , booktitle =

Scarlett, Jonathan and Cevher, Volkan , year =. An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation , booktitle =
[126]

10/36-702: Minimax Theory [Lecture Notes]

Ryan Tibshirani. 10/36-702: Minimax Theory [Lecture Notes]
[127]

CoRR , volume =

A short note on an inequality between KL and TV , author =. CoRR , volume =. 2202.07198 , year =
[128]

Tsybakov , title =

Alexandre B. Tsybakov , title =. 2009 , isbn =

2009
[129]

CoRR , volume =

Nearly tight universal bounds for the binomial tail probabilities , author =. CoRR , volume =. 2211.01688 , year =
[130]

abcvoting:

Martin Lackner and Peter Regner and Benjamin Krenn , year =. abcvoting:
[131]

1984 , publisher =

Voting Procedures , author =. 1984 , publisher =

1984
[132]

On methods of electing representatives , author =
[133]

2011 , publisher =

Geometric approximation algorithms , author =. 2011 , publisher =

2011
[134]

Casey and Edith Elkind , title =

Matthew M. Casey and Edith Elkind , title =. CoRR , volume =. 2025 , eprinttype =

2025
[135]

Nature , volume =

Fair algorithms for selecting citizens' assemblies , author =. Nature , volume =. 2021 , publisher =

2021
[136]

Advances in Neural Information Processing Systems , volume =

Neutralizing self-selection bias in sampling for sortition , author =. Advances in Neural Information Processing Systems , volume =
[137]

Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger , volume =

Om flerfoldsvalg , author =. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger , volume =
[138]

Proportional Selection in Networks , journal =

Georgios Papasotiropoulos and Oskar Skibski and Piotr Skowron and Tomasz W. Proportional Selection in Networks , journal =. 2025 , eprinttype =

2025
[139]

2019 , publisher =

Proportionally fair clustering , author =. 2019 , publisher =

2019
[140]

Beyond the Worst-Case Analysis of Algorithms , pages =

Anupam Gupta and Sahil Singla , title =. Beyond the Worst-Case Analysis of Algorithms , pages =
[141]

Geometric Algorithms and Combinatorial Optimization , series =

Martin Gr. Geometric Algorithms and Combinatorial Optimization , series =. 1988 , isbn =

1988
[142]

Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 1: Methologies and Traditional Applications , pages =

Niv Buchbinder and Moran Feldman , title =. Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 1: Methologies and Traditional Applications , pages =
[143]

Dickerson and Karthik Abinav Sankararaman and Aravind Srinivasan and Pan Xu , title =

John P. Dickerson and Karthik Abinav Sankararaman and Aravind Srinivasan and Pan Xu , title =
[144]

Mirrokni and Morteza Zadimoghaddam , title =

Nitish Korula and Vahab S. Mirrokni and Morteza Zadimoghaddam , title =
[145]

Bilmes , title =

Hui Lin and Jeff A. Bilmes , title =. The 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Proceedings of the Conference, 19-24 June, 2011, Portland, Oregon,

2011
[146]

Iyer and Ninad Khargoankar and Jeff A

Rishabh K. Iyer and Ninad Khargoankar and Jeff A. Bilmes and Himanshu Asanani , title =. Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide , series =

2021
[147]

Micah Corah and Nathan Michael , title =. 57th
[148]

Zengfu Wang and William Moran and Xuezhi Wang and Quan Pan , title =. J. Comb. Optim. , volume =
[149]

Zengfu Wang and Xuezhi Wang and Yan Liang and Quan Pan , title =
[150]

Gibbons and Bernhard Haeupler and Charles McGuffey , title =

Nathan Beckmann and Phillip B. Gibbons and Bernhard Haeupler and Charles McGuffey , title =
[151]

Nikhil Bansal and Joseph (Seffi) Naor and Ohad Talmon , title =
[152]

Crouch and Daniel M

Michael S. Crouch and Daniel M. Stubbs , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,
[153]

Approximation, Randomization, and Combinatorial Optimization

Xiangyu Guo and Janardhan Kulkarni and Shi Li and Jiayi Xian , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,
[154]

Fully Dynamic Consistent Facility Location , booktitle = nips, pages =

Vincent Cohen. Fully Dynamic Consistent Facility Location , booktitle = nips, pages =
[155]

Andrew McGregor , title =. Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems,
[156]

Algorithms -

Niv Buchbinder and Shahar Chen and Joseph Naor , title =. Algorithms -
[157]

Algorithms -

Moran Feldman and Joseph Naor and Roy Schwartz and Justin Ward , title =. Algorithms -
[158]

Lujun Jia and Guolong Lin and Guevara Noubir and Rajmohan Rajaraman and Ravi Sundaram , title =
[159]

Sampling Bounds for Stochastic Optimization , booktitle =

Moses Charikar and Chandra Chekuri and Martin P. Sampling Bounds for Stochastic Optimization , booktitle =
[160]

Anupam Gupta and Gregory Kehne and Roie Levin , title =
[161]

Anupam Gupta and Roie Levin , title =
[162]

Nicholas J. A. Harvey and Jelani Nelson and Krzysztof Onak , title =
[163]

Adam Meyerson , title =
[164]

Plotkin , title =

Adam Meyerson and Kamesh Munagala and Serge A. Plotkin , title =
[165]

Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract) , booktitle = focs, pages =

Andrew Chi. Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract) , booktitle = focs, pages =
[166]

Moab Arar and Shiri Chechik and Sarel Cohen and Cliff Stein and David Wajc , title =
[167]

Manoj Gupta and Richard Peng , title =
[168]

Italiano , title =

Sayan Bhattacharya and Monika Henzinger and Giuseppe F. Italiano , title =
[169]

Automata, Languages, and Programming - 42nd International Colloquium,

Aaron Bernstein and Cliff Stein , title =. Automata, Languages, and Programming - 42nd International Colloquium,
[170]

Aaron Bernstein and Cliff Stein , title =
[171]

Automata, Languages, and Programming - 42nd International Colloquium,

Chandra Chekuri and Shalmoli Gupta and Kent Quanrud , title =. Automata, Languages, and Programming - 42nd International Colloquium,
[172]

Moran Feldman and Amin Karbasi and Ehsan Kazemi , title =
[173]

CoRR , volume =

Archit Bubna and Ashish Chiplunkar , title =. CoRR , volume =. 2022 , eprinttype =

2022
[174]

Bo Peng and Zhihao Gavin Tang , title =
[175]

Variable Decomposition for Prophet Inequalities and Optimal Ordering , booktitle = ec, pages =

Allen Liu and Renato Paes Leme and Martin P. Variable Decomposition for Prophet Inequalities and Optimal Ordering , booktitle = ec, pages =
[176]

Sina Dehghani and Soheil Ehsani and MohammadTaghi Hajiaghayi and Vahid Liaghat and Saeed Seddighin , title =
[177]

Automata, Languages, and Programming - 41st International Colloquium,

Anupam Gupta and Kunal Talwar and Udi Wieder , title =. Automata, Languages, and Programming - 41st International Colloquium,
[178]

Yevgeny Seldin and Aleksandrs Slivkins , title =
[179]

Sitaraman , title =

Syed Hasan and Sergey Gorinsky and Constantine Dovrolis and Ramesh K. Sitaraman , title =
[180]

Berger and Kai Li and Wyatt Lloyd , title =

Zhenyu Song and Daniel S. Berger and Kai Li and Wyatt Lloyd , title =
[181]

Ashwinkumar Badanidiyuru and Baharan Mirzasoleiman and Amin Karbasi and Andreas Krause , title =
[182]

Ehsan Kazemi and Marko Mitrovic and Morteza Zadimoghaddam and Silvio Lattanzi and Amin Karbasi , title =
[183]

Nguyen and Andrew Suh , title =

Naor Alaluf and Alina Ene and Moran Feldman and Huy L. Nguyen and Andrew Suh , title =
[184]

Matthew Weinberg , title =

Pablo Daniel Azar and Robert Kleinberg and S. Matthew Weinberg , title =
[185]

Baharan Mirzasoleiman and Stefanie Jegelka and Andreas Krause , title =
[186]

Brendan McMahan and Carlos Guestrin and Anupam Gupta , title =

Andreas Krause and H. Brendan McMahan and Carlos Guestrin and Anupam Gupta , title =
[187]

Chen and Mark B

Stefan Jorgensen and Robert H. Chen and Mark B. Milam and Marco Pavone , title =. 56th
[188]

Robust landmark selection for mobile robot navigation , booktitle =

Maximilian Beinhofer and J. Robust landmark selection for mobile robot navigation , booktitle =
[189]

Baharan Mirzasoleiman and Amin Karbasi and Rik Sarkar and Andreas Krause , title =
[190]

Streeter and Daniel Golovin , title =

Matthew J. Streeter and Daniel Golovin , title =
[191]

Bilmes , title =

Andrew Guillory and Jeff A. Bilmes , title =
[192]

Proceedings of the

Barna Saha and Lise Getoor , title =. Proceedings of the
[193]

Demaine and Piotr Indyk and Sepideh Mahabadi and Ali Vakilian , title =

Erik D. Demaine and Piotr Indyk and Sepideh Mahabadi and Ali Vakilian , title =. Distributed Computing - 28th International Symposium,
[194]

Towards Tight Bounds for the Streaming Set Cover Problem , booktitle = pods, pages =

Sariel Har. Towards Tight Bounds for the Streaming Set Cover Problem , booktitle = pods, pages =
[195]

Semi-Streaming Set Cover , journal =

Yuval Emek and Adi Ros. Semi-Streaming Set Cover , journal =
[196]

Niv Buchbinder and Moran Feldman and Joseph Naor and Roy Schwartz , title =
[197]

Niv Buchbinder and Anupam Gupta and Marco Molinaro and Joseph (Seffi) Naor , title =
[198]

Devanur and Kamal Jain and Robert D

Nikhil R. Devanur and Kamal Jain and Robert D. Kleinberg , title =
[199]

2nd Symposium on Simplicity in Algorithms,

Mohsen Ghaffari and David Wajc , title =. 2nd Symposium on Simplicity in Algorithms,
[200]

Submodular Maximization by Simulated Annealing , booktitle = soda, pages =

Shayan Oveis Gharan and Jan Vondr. Submodular Maximization by Simulated Annealing , booktitle = soda, pages =
[201]

Ashish Goel and Michael Kapralov and Sanjeev Khanna , title =
[202]

Anupam Gupta and Ravishankar Krishnaswamy and Amit Kumar and Debmalya Panigrahi , title =
[203]

Anupam Gupta and Amit Kumar , title =
[204]

Michael Kapralov , title =
[205]

Roie Levin and David Wajc , title =
[206]

Gibbons and Charles McGuffey , title =

Nathan Beckmann and Phillip B. Gibbons and Charles McGuffey , title =
[207]

Christian Coester and Roie Levin and Joseph (Seffi) Naor and Ohad Talmon , title =
[208]

Guy Even and Moti Medina and Dror Rawitz , title =
[209]

Zhiyi Huang and Ning Kang and Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang and Xue Zhu , title =
[210]

Zhiyi Huang and Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang , title =
[211]

Zhiyi Huang and Binghui Peng and Zhihao Gavin Tang and Runzhou Tao and Xiaowei Wu and Yuhao Zhang , title =
[212]

Matthew Fahrbach and Zhiyi Huang and Runzhou Tao and Morteza Zadimoghaddam , title =
[213]

Zhiyi Huang and Qiankun Zhang , title =
[214]

Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang , title =
[215]

Zhiyi Huang and Qiankun Zhang and Yuhao Zhang , title =
[216]

Irit Dinur and David Steurer , title =
[217]

The one-way communication complexity of submodular maximization with applications to streaming and robustness , booktitle = stoc, pages =

Moran Feldman and Ashkan Norouzi. The one-way communication complexity of submodular maximization with applications to streaming and robustness , booktitle = stoc, pages =
[218]

Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams , booktitle = icml, series =

Ashkan Norouzi. Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams , booktitle = icml, series =
[219]

Anupam Gupta and Amit Kumar and Debmalya Panigrahi , title =
[220]

Wang and S

Aviad Rubinstein and Jack Z. Wang and S. Matthew Weinberg , title =
[221]

Jakub Lacki and Jakub Ocwieja and Marcin Pilipczuk and Piotr Sankowski and Anna Zych , title =
[222]

Phillips and Jeffery R

Steven J. Phillips and Jeffery R. Westbrook , title =
[223]

Westbrook , title =

Jeffery R. Westbrook , title =
[224]

Goemans and Lisa Zhang , title =

Matthew Andrews and Michel X. Goemans and Lisa Zhang , title =. Algorithmica , volume =
[225]

Peter Sanders and Naveen Sivadasan and Martin Skutella , title =. Math. Oper. Res. , volume =
[226]

A Robust

Martin Skutella and Jos. A Robust. Algorithms -
[227]

Algorithmica , volume =

Leah Epstein and Asaf Levin , title =. Algorithmica , volume =
[228]

Anupam Gupta and Amit Kumar and Cliff Stein , title =
[229]

Ran Raz and Shmuel Safra , title =
[230]

Optimal approximation for the submodular welfare problem in the value oracle model , booktitle = stoc, pages =

Jan Vondr. Optimal approximation for the submodular welfare problem in the value oracle model , booktitle = stoc, pages =
[231]

Games Econ

Benny Lehmann and Daniel Lehmann and Noam Nisan , title =. Games Econ. Behav. , volume =
[232]

Maximizing a Monotone Submodular Function Subject to a Matroid Constraint , journal = siamjc, volume =

Gruia C. Maximizing a Monotone Submodular Function Subject to a Matroid Constraint , journal = siamjc, volume =
[233]

David Wajc , title =
[234]

Grove and Ming

Edward F. Grove and Ming. Online Perfect Matching and Mobile Computing , booktitle =
[235]

Kleinberg and Henry Lin , title =

Kamalika Chaudhuri and Constantinos Daskalakis and Robert D. Kleinberg and Henry Lin , title =
[236]

Bartlomiej Bosek and Dariusz Leniowski and Piotr Sankowski and Anna Zych , title =
[237]

Proceedings of the Second International Conference on Web Search and Web Data Mining,

Rakesh Agrawal and Sreenivas Gollapudi and Alan Halverson and Samuel Ieong , title =. Proceedings of the Second International Conference on Web Search and Web Data Mining,
[238]

Dickerson and Mark D

Faez Ahmed and John P. Dickerson and Mark D. Fuge , title =
[239]

Algorithmica , volume =

Susanne Albers and Maximilian Janke , title =. Algorithmica , volume =
[240]

Susanne Albers and Maximilian Janke , title =
[241]

Daniel Dominic Sleator and Robert Endre Tarjan , title =
[242]

Karp and Michael Luby and Lyle A

Amos Fiat and Richard M. Karp and Michael Luby and Lyle A. McGeoch and Daniel Dominic Sleator and Neal E. Young , title =
[243]

Young , title =

Neal E. Young , title =
[244]

Young , title =

Neal E. Young , title =. Algorithmica , volume =
[245]

McGeoch and Daniel Dominic Sleator , title =

Lyle A. McGeoch and Daniel Dominic Sleator , title =. Algorithmica , volume =
[246]

Nikhil Bansal and Niv Buchbinder and Joseph Naor , title =
[247]

Dimitris Achlioptas and Marek Chrobak and John Noga , title =
[248]

Susanne Albers and Sanjeev Arora and Sanjeev Khanna , title =
[249]

Avrim Blum and Carl Burch and Adam Kalai , title =
[250]

Algorithmica , volume =

Sandy Irani , title =. Algorithmica , volume =
[251]

Wolsey , title =

Laurence A. Wolsey , title =
[252]

Pan Wu and Guihai Chen and Xiaojun Zhu and Xiaobing Wu , title =. Comput. Commun. , volume =
[253]

Preciado , title =

Mohammad Amin Rahimian and Victor M. Preciado , title =
[254]

Zhenzhe Zheng and Yanqing Peng and Fan Wu and Shaojie Tang and Guihai Chen , title =
[255]

Armeline Dembo Mafuta and Tom Walingo , title =
[256]

CoRR , volume =

Sayan Bhattacharya and Peter Kiss and Thatchaphol Saranurak , title =. CoRR , volume =. 2022 , eprinttype =

2022
[257]

Bach , title =

Francis R. Bach , title =. Found. Trends Mach. Learn. , volume =
[258]

Convex Optimization: Algorithms and Complexity , journal =

S. Convex Optimization: Algorithms and Complexity , journal =
[259]

Niv Buchbinder and Joseph Naor , title =. Found. Trends Theor. Comput. Sci. , volume =
[260]

Niv Buchbinder and Shahar Chen and Joseph Naor , title =
[261]

k-server via multiscale entropic regularization , booktitle = stoc, pages =

S. k-server via multiscale entropic regularization , booktitle = stoc, pages =
[262]

Shmoys and Chaitanya Swamy , title =

David B. Shmoys and Chaitanya Swamy , title =
[263]

Ravi and Amitabh Sinha , title =

Anupam Gupta and R. Ravi and Amitabh Sinha , title =. Math. Oper. Res. , volume =
[264]

What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization , booktitle =

Anupam Gupta and Martin P. What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization , booktitle =
[265]

Boosted sampling: approximation algorithms for stochastic optimization , booktitle = stoc, pages =

Anupam Gupta and Martin P. Boosted sampling: approximation algorithms for stochastic optimization , booktitle = stoc, pages =
[266]

Shmoys , title =

Chaitanya Swamy and David B. Shmoys , title =
[267]

Noga Alon and Baruch Awerbuch and Yossi Azar and Niv Buchbinder and Joseph Naor , title =
[268]

Ravi , title =

Marco Molinaro and R. Ravi , title =. Math. Oper. Res. , volume =
[269]

Primal Beats Dual on Online Packing LPs in the Random-Order Model , journal = siamjc, volume =

Thomas Kesselheim and Klaus Radke and Andreas T. Primal Beats Dual on Online Packing LPs in the Random-Order Model , journal = siamjc, volume =
[270]

Anupam Gupta and Marco Molinaro , title =. Math. Oper. Res. , volume =
[271]

Algorithmica , volume =

Susanne Albers and Arindam Khan and Leon Ladewig , title =. Algorithmica , volume =
[272]

Anstee , title =

Richard P. Anstee , title =
[273]

Gabow , title =

Harold N. Gabow , title =
[274]

C. J. Argue and Anupam Gupta and Ziye Tang and Guru Guruganesh , title =
[275]

Mark Sellke , title =
[276]

Anna Adamaszek and Artur Czumaj and Matthias Englert and Harald R. An
[277]

A unified approach to approximating resource allocation and scheduling , journal = jacm, volume =

Amotz Bar. A unified approach to approximating resource allocation and scheduling , journal = jacm, volume =
[278]

Nemhauser and Laurence A

George L. Nemhauser and Laurence A. Wolsey , title =. Math. Oper. Res. , volume =
[279]

Thodoris Lykouris and Sergei Vassilvitskii , title =
[280]

Daniel Golovin and Andreas Krause , title =
[281]

Amol Deshpande and Lisa Hellerstein and Devorah Kletenik , title =
[282]

Lisa Hellerstein and Devorah Kletenik , title =
[283]

Approximation and Online Algorithms - 14th International Workshop,

Nathaniel Grammel and Lisa Hellerstein and Devorah Kletenik and Patrick Lin , title =. Approximation and Online Algorithms - 14th International Workshop,
[284]

Arpit Agarwal and Sepehr Assadi and Sanjeev Khanna , title =
[285]

Mirrokni , title =

Hossein Esfandiari and Amin Karbasi and Vahab S. Mirrokni , title =. Conference on Learning Theory,
[286]

Rohan Ghuge and Anupam Gupta and Viswanath Nagarajan , title =
[287]

Russell Impagliazzo and Ramamohan Paturi , title =
[288]

Approximate and incremental network function placement , journal = jpdc, volume =

Tam. Approximate and incremental network function placement , journal = jpdc, volume =
[289]

Niv Buchbinder and Moran Feldman , title =. Math. Oper. Res. , volume =
[290]

Niv Buchbinder and Joseph Naor , title =. Math. Oper. Res. , volume =
[291]

A Greedy Heuristic for the Set-Covering Problem , journal =

Vasek Chv. A Greedy Heuristic for the Set-Covering Problem , journal =
[292]

Johnson , title =

David S. Johnson , title =
[293]

On the ratio of optimal integral and fractional covers , journal =

L. On the ratio of optimal integral and fractional covers , journal =
[294]

Williamson and David B

David P. Williamson and David B. Shmoys , title =. 2011 , isbn =

2011
[295]

Hammer , title =

Stephan Foldes and Peter L. Hammer , title =. Math. Oper. Res. , volume =
[296]

Submodular Maximization over Multiple Matroids via Generalized Exchange Properties , journal =

Jon Lee and Maxim Sviridenko and Jan Vondr. Submodular Maximization over Multiple Matroids via Generalized Exchange Properties , journal =
[297]

Mirrokni and Viswanath Nagarajan and Maxim Sviridenko , title =

Jon Lee and Vahab S. Mirrokni and Viswanath Nagarajan and Maxim Sviridenko , title =
[298]

Internet and Network Economics - 6th International Workshop,

Anupam Gupta and Aaron Roth and Grant Schoenebeck and Kunal Talwar , title =. Internet and Network Economics - 6th International Workshop,
[299]

Amit Chakrabarti and Sagar Kale , title =. Math. Program. , volume =
[300]

Nemhauser and Laurence A

George L. Nemhauser and Laurence A. Wolsey and Marshall L. Fisher , title =. Math. Program. , volume =

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.

[1] [1]

PhD thesis, Charles University, Prague, Czech Republic , year =

Submodularity in combinatorial optimization , author =. PhD thesis, Charles University, Prague, Czech Republic , year =

[2] [2]

Jakulin, Aleks , journal =

[3] [3]

1985 , publisher =

A simple probabilistic approximation algorithm for vertex cover , author =. 1985 , publisher =

1985

[4] [4]

Master's thesis, Weizmann Institute of Science, Rehovot, Israel , year =

On the use of randomization in the online set cover problem , author =. Master's thesis, Weizmann Institute of Science, Rehovot, Israel , year =

[5] [5]

Polyhedral Combinatorics: Dedicated to the memory of D.R

An analysis of approximations for maximizing submodular set functions---II. Polyhedral Combinatorics: Dedicated to the memory of D.R. Fulkerson. 1978

1978

[6] [6]

1988 , publisher =

Tsallis, Constantino , journal = jsp, volume =. 1988 , publisher =

1988

[7] [7]

Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences , volume =

Cand\`. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences , volume =. 2006 , publisher =

2006

[8] [8]

Sayan Bhattacharya and Janardhan Kulkarni , title =