Paper Citation Record · LEDGER

Tight Algorithm and Hardness for Submodular Linear Ordering

As of 9 August 2026, this Paper Citation Record lists 41 of 41 outbound references and 0 inbound Pith citation observations for arXiv:2606.20202.

A citation records a reference. It does not transfer a finding from one paper to another.

pith.paper-citation-record.v1
2606.20202 v1

Coverage vector

measured 41 of 41 reference resolution

Typed states for the displayed outbound observations.

Source: paper_references, paper_reference_links, observed 2026-06-26T15:23:45.836127Z

measured 41 of 41 standing notices

One-hop event checks from named stored sources.

Source: scholarly_work_events, retraction_status_cache, observed 2026-08-09T06:31:02.800959+00:00

measured 0 of 0 inbound itemization

Pith citing papers itemized under the disclosed page cap.

Source: paper_references, paper_reference_links

measured 0 of 1 external citation measurements

A source-named dated measurement, never combined with another source.

Source: cited_works

Reference resolution

41 of 41 outbound references displayed

verified exact0
verified fuzzy0
unresolved40
parse uncertain0
malformed identifier0
metadata mismatch1

External citation measurements

No source-named external measurement is stored.

Outbound references

Observation e3785afa-c43f-4de0-8139-689bd5f9d480 · outbound

This paper cites Expander flows, geometric embeddings and graph partitioning.Journal of the ACM (JACM), 56(2):1–37, 2009.

Tight Algorithm and Hardness for Submodular Linear Ordering Expander flows, geometric embeddings and graph partitioning.Journal of the ACM (JACM), 56(2):1–37, 2009

Reference 1

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 46d6f1b8-3615-40d1-84ce-a99fb5aed94f · outbound

This paper cites Submodular max-sat.

Tight Algorithm and Hardness for Submodular Linear Ordering Submodular max-sat

Reference 2

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation ad43848d-9ca5-4e8c-8d92-35a86dbf7bb2 · outbound

This paper cites Improved approximations for min sum vertex cover and generalized min sum set cover.

Tight Algorithm and Hardness for Submodular Linear Ordering Improved approximations for min sum vertex cover and generalized min sum set cover

Reference 3

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 89ae7aca-9cf8-480c-bf86-d16e29d83769 · outbound

This paper cites Concentration inequalities for sampling without replacement.

Tight Algorithm and Hardness for Submodular Linear Ordering Concentration inequalities for sampling without replacement

Reference 4

Resolution: metadata mismatch; local_arxiv, observed 2026-07-04T05:49:37.778240Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

Observation e4a7ee20-fd4e-4ede-bc39-798dd60ef680 · outbound

This paper cites Improved approximation for min-sum vertex cover.

Tight Algorithm and Hardness for Submodular Linear Ordering Improved approximation for min-sum vertex cover

Reference 5

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation d98a1d87-b547-40dc-bce7-4c3c545bb6b3 · outbound

This paper cites Bhatt and Frank Thomson Leighton.

Tight Algorithm and Hardness for Submodular Linear Ordering Bhatt and Frank Thomson Leighton

Reference 6

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 656ccbd4-bf53-4b96-9703-690b614e5d6b · outbound

This paper cites an unresolved cited work.

Tight Algorithm and Hardness for Submodular Linear Ordering Unresolved cited work

Reference 7

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 77bc1137-b1f1-46d8-967a-ae7e1695bb5a · outbound

This paper cites The minsumcut problem.

Tight Algorithm and Hardness for Submodular Linear Ordering The minsumcut problem

Reference 8

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 42e3a96d-d6fa-436c-a9f4-fffbca2a46c3 · outbound

This paper cites From query complexity to computational complexity.

Tight Algorithm and Hardness for Submodular Linear Ordering From query complexity to computational complexity

Reference 9

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation e2cf12f3-1168-4ca3-a487-4e0c41e7f724 · outbound

This paper cites Local distribution and the symmetry gap: Approx- imability of multiway partitioning problems.

Tight Algorithm and Hardness for Submodular Linear Ordering Local distribution and the symmetry gap: Approx- imability of multiway partitioning problems

Reference 10

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 57e2e8fc-1939-435e-8fe9-eddaec081ed2 · outbound

This paper cites Divide-and-conquer approxi- mation algorithms via spreading metrics.Journal of the ACM (JACM), 47(4):585–616, 2000.

Tight Algorithm and Hardness for Submodular Linear Ordering Divide-and-conquer approxi- mation algorithms via spreading metrics.Journal of the ACM (JACM), 47(4):585–616, 2000

Reference 11

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation e7ffa7b6-9085-452d-9fc9-a25b2c41f590 · outbound

This paper cites Hardness and approximation of submodular minimum linear ordering problems.Mathematical Program- ming, 208(1):277–318, 2024.

Tight Algorithm and Hardness for Submodular Linear Ordering Hardness and approximation of submodular minimum linear ordering problems.Mathematical Program- ming, 208(1):277–318, 2024

Reference 12

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 56a51a9e-eadc-44dd-9e02-6f6ffa057874 · outbound

This paper cites an unresolved cited work.

Tight Algorithm and Hardness for Submodular Linear Ordering Unresolved cited work

Reference 13

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation d35bc487-7602-4528-9313-1dbe80f8ae72 · outbound

This paper cites An improved approximation ratio for the minimum linear arrangement problem.Information Processing Letters, 101(1):26–29, 2007.

Tight Algorithm and Hardness for Submodular Linear Ordering An improved approximation ratio for the minimum linear arrangement problem.Information Processing Letters, 101(1):26–29, 2007

Reference 14

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 46a0659e-0bd1-4d39-a513-84d10c251a7d · outbound

This paper cites Approximating min sum set cover.Algorithmica, 40(4):219–234, 2004.

Tight Algorithm and Hardness for Submodular Linear Ordering Approximating min sum set cover.Algorithmica, 40(4):219–234, 2004

Reference 15

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 200587c5-b1f8-426c-89cf-ca4485630412 · outbound

This paper cites Maximizing non-monotone submodular functions.SIAM Journal on Computing, 40(4):1133–1153, 2011.

Tight Algorithm and Hardness for Submodular Linear Ordering Maximizing non-monotone submodular functions.SIAM Journal on Computing, 40(4):1133–1153, 2011

Reference 16

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 2e06eb97-eb9b-46a5-8d8b-9d59c655a8cf · outbound

This paper cites Separating coverage and submodular: Maximization subject to a cardinality constraint.

Tight Algorithm and Hardness for Submodular Linear Ordering Separating coverage and submodular: Maximization subject to a cardinality constraint

Reference 17

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation e34a3f0f-e61a-464a-9af1-8ae4c6d094bf · outbound

This paper cites Submodular maximization by simulated annealing.

Tight Algorithm and Hardness for Submodular Linear Ordering Submodular maximization by simulated annealing

Reference 18

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 937c23b8-ef0e-42e2-8611-cee8cabb1dca · outbound

This paper cites Approximability of com- binatorial problems with multi-agent submodular cost functions.

Tight Algorithm and Hardness for Submodular Linear Ordering Approximability of com- binatorial problems with multi-agent submodular cost functions

Reference 19

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation ea09460a-0423-498c-a5d4-0cbfa9896934 · outbound

This paper cites Approximat- ing submodular functions everywhere.

Tight Algorithm and Hardness for Submodular Linear Ordering Approximat- ing submodular functions everywhere

Reference 20

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 80b36ca9-93c9-4cb2-91f4-7bada58e014e · outbound

This paper cites The ellipsoid method and its consequences in combinatorial optimization.Combinatorica, 1:169–197, 1981.

Tight Algorithm and Hardness for Submodular Linear Ordering The ellipsoid method and its consequences in combinatorial optimization.Combinatorica, 1:169–197, 1981

Reference 21

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 8142e554-9bed-49f6-b767-3686aaf4820a · outbound

This paper cites An approximation algorithm for the minimum latency set cover problem.

Tight Algorithm and Hardness for Submodular Linear Ordering An approximation algorithm for the minimum latency set cover problem

Reference 22

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 74fda985-2232-4075-b610-d46694fa1fc8 · outbound

This paper cites Probability inequalities for sums of bounded random variables.Journal of the American statistical association, 58(301):13–30, 1963.

Tight Algorithm and Hardness for Submodular Linear Ordering Probability inequalities for sums of bounded random variables.Journal of the American statistical association, 58(301):13–30, 1963

Reference 23

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 1f092beb-febd-4245-a391-acb89b1c03af · outbound

This paper cites A combinatorial strongly polynomial algo- rithm for minimizing submodular functions.J.

Tight Algorithm and Hardness for Submodular Linear Ordering A combinatorial strongly polynomial algo- rithm for minimizing submodular functions.J

Reference 24

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 9d74ff3e-a05e-4016-a74e-1f429cfda307 · outbound

This paper cites Submodular function minimization under covering con- straints.

Tight Algorithm and Hardness for Submodular Linear Ordering Submodular function minimization under covering con- straints

Reference 25

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 22094a41-63c6-45e0-8a47-892ed357ef37 · outbound

This paper cites Approximating minimum linear order- ing problems.

Tight Algorithm and Hardness for Submodular Linear Ordering Approximating minimum linear order- ing problems

Reference 26

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation c560af0a-5cdd-40e2-9c25-cfc741a737b5 · outbound

This paper cites A simple algorithm for submodular minimum linear order- ing.

Tight Algorithm and Hardness for Submodular Linear Ordering A simple algorithm for submodular minimum linear order- ing

Reference 27

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 3cdc0745-4c4b-4cd7-89d3-f36ec983a6e1 · outbound

This paper cites Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.Journal of the ACM (JACM), 46(6):787–832, 1999.

Tight Algorithm and Hardness for Submodular Linear Ordering Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.Journal of the ACM (JACM), 46(6):787–832, 1999

Reference 28

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation b70cda4b-e262-4f3f-a29a-bde909f73e84 · outbound

This paper cites Profile minimization problem for matrices and graphs.Acta Mathematicae Applicatae Sinica, 10:107–112, 1994.

Tight Algorithm and Hardness for Submodular Linear Ordering Profile minimization problem for matrices and graphs.Acta Mathematicae Applicatae Sinica, 10:107–112, 1994

Reference 29

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation b1e32629-9325-4ec8-afd0-e0299d3c42cb · outbound

This paper cites Submodular functions and convexity.

Tight Algorithm and Hardness for Submodular Linear Ordering Submodular functions and convexity

Reference 30

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 7d117287-ceb0-4873-8381-f1c194061cb0 · outbound

This paper cites Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions.

Tight Algorithm and Hardness for Submodular Linear Ordering Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions

Reference 31

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation fec45144-a10a-4b87-b2ab-0dc28a9b468f · outbound

This paper cites an unresolved cited work.

Tight Algorithm and Hardness for Submodular Linear Ordering Unresolved cited work

Reference 32

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation ce2c52a1-dca3-429d-bfe8-359fe5be8cbe · outbound

This paper cites Ramalingam and C.Pandu Rangan.

Tight Algorithm and Hardness for Submodular Linear Ordering Ramalingam and C.Pandu Rangan

Reference 33

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 6ab5b3ba-93d7-44ef-8cf3-ca239b6df4e7 · outbound

This paper cites New approximation techniques for some linear ordering problems.SIAM Journal on Computing, 34(2):388–404, 2005.

Tight Algorithm and Hardness for Submodular Linear Ordering New approximation techniques for some linear ordering problems.SIAM Journal on Computing, 34(2):388–404, 2005

Reference 34

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 8730ed35-ce58-4292-aa36-371f1ef21f57 · outbound

This paper cites Ordering problems approximated: single- processor scheduling and interval graph completion.

Tight Algorithm and Hardness for Submodular Linear Ordering Ordering problems approximated: single- processor scheduling and interval graph completion

Reference 35

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation eb5176e0-290e-49c3-9aa7-46676384b5a6 · outbound

This paper cites Multivariate submodular optimization.

Tight Algorithm and Hardness for Submodular Linear Ordering Multivariate submodular optimization

Reference 36

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation abcfd163-82d6-4a17-8aeb-2b85ffbf527b · outbound

This paper cites A combinatorial algorithm minimizing submodular functions in strongly polynomial time.Journal of Combinatorial Theory, Series B, 80(2):346–355, 2000.

Tight Algorithm and Hardness for Submodular Linear Ordering A combinatorial algorithm minimizing submodular functions in strongly polynomial time.Journal of Combinatorial Theory, Series B, 80(2):346–355, 2000

Reference 37

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 22b3e28f-de45-4ee3-b62f-18742ebba76a · outbound

This paper cites an unresolved cited work.

Tight Algorithm and Hardness for Submodular Linear Ordering Unresolved cited work

Reference 38

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 303bbae1-c030-4c37-9093-76a2a298b88c · outbound

This paper cites Some Results on Approximability of Minimum Sum Vertex Cover.

Tight Algorithm and Hardness for Submodular Linear Ordering Some Results on Approximability of Minimum Sum Vertex Cover

Reference 39

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation a7bc8b32-494f-4732-ab67-0d76a4758862 · outbound

This paper cites Submodular approximation: Sampling-based algorithms and lower bounds.SIAM Journal on Computing, 40(6):1715–1737, 2011.

Tight Algorithm and Hardness for Submodular Linear Ordering Submodular approximation: Sampling-based algorithms and lower bounds.SIAM Journal on Computing, 40(6):1715–1737, 2011

Reference 40

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation f944f706-76d2-4bb1-a80f-15afd5d275b3 · outbound

This paper cites Symmetry and approximability of submodular maximization problems.SIAM Journal on Computing, 42(1):265–304, 2013.

Tight Algorithm and Hardness for Submodular Linear Ordering Symmetry and approximability of submodular maximization problems.SIAM Journal on Computing, 42(1):265–304, 2013

Reference 41

Resolution: unresolved; no resolver link, observed 2026-06-26T15:23:45.836127Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Pith citing papers

No inbound Pith citation observations are available.