Pith. sign in

REVIEW 1 cited by

Optimizing Polymatroid Functions

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2211.08381 v1 pith:5MQ4YUWV submitted 2022-11-15 cs.DS

Sungjin Im , Benjamin Moseley , Hung Q. Ngo , Kirk Pruhs , Alireza Samadian This is my paper · ORCID
classification cs.DS
keywords resultscertainclassconstraintsdifferenceparticulartechniqueused
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We consider a class of optimization problems that involve determining the maximum value that a function in a particular class can attain subject to a collection of difference constraints. We show that a particular linear programming technique, based on duality and projections, can be used to rederive some structural results that were previously established using more ad hoc methods. We then show that this technique can be used to obtain a polynomial-time algorithm for a certain type of simple difference constraints. Finally we give lower bound results that show that certain possible extensions of these results are probably not feasible.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. LpBound: Pessimistic Cardinality Estimation using $\ell_p$-Norms of Degree Sequences

    cs.DB 2025-02 conditional novelty 6.0 of 10

    LpBound computes a guaranteed, tight upper bound on multijoin output cardinality by solving a linear program over lp-norm degree statistics and Shannon inequalities.

Pith tools