On the public citation graph
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?
0 signed · 56 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/11561071_63openalex-snapshot
Using Fractional Primal-Dual to Schedule Split Intervals with Demands
inferredcites →https://doi.org/10.1007/3-540-40996-3_20openalex-snapshot
Simple Algorithms for a Weighted Interval Selection Problem
inferredcites →https://doi.org/10.1007/3-540-44666-4_7openalex-snapshot
On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique
inferredcites →https://doi.org/10.1007/3-540-44683-4_59openalex-snapshot
On the Approximability of the Steiner Tree Problem
inferredcites →https://doi.org/10.1007/3-540-45753-4_5openalex-snapshot
On the Power of Priority Algorithms for Facility Location and Set Cover
inferredcites →https://doi.org/10.1007/3-540-47867-1_28openalex-snapshot
Improved Approximation Algorithms for Resource Allocation
inferredcites →https://doi.org/10.1007/978-1-4613-0259-9_7openalex-snapshot
A Simple Approximation Algorithm for Nonoverlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles)
inferredcites →https://doi.org/10.1007/978-1-4757-3613-7_23openalex-snapshot
Opportunity Cost Algorithms for Combinatorial Auctions
inferredcites →https://doi.org/10.1007/bfb0015417openalex-snapshot
Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
inferredcites →https://doi.org/10.1007/s00037-011-0028-yopenalex-snapshot
Toward a Model for Backtracking and Dynamic Programming
inferredcites →https://doi.org/10.1007/s00453-003-1036-3openalex-snapshot
(Incremental) Priority Algorithms
inferredcites →https://doi.org/10.1007/s00453-004-1113-2openalex-snapshot
The Power of Priority Algorithms for Facility Location and Set Cover
inferredcites →https://doi.org/10.1007/s101070100262openalex-snapshot
The primal-dual method for approximation algorithms
inferredcites →https://doi.org/10.1007/springerreference_57547openalex-snapshot
Approximation Algorithms
inferredcites →https://doi.org/10.1016/0020-0190(88)90066-xopenalex-snapshot
A faster approximation algorithm for the Steiner problem in graphs
inferredcites →https://doi.org/10.1016/0166-218x(87)90037-0openalex-snapshot
Scheduling jobs with fixed start and end times
inferredcites →https://doi.org/10.1016/0196-6774(81)90020-1openalex-snapshot
A linear-time approximation algorithm for the weighted vertex cover problem
inferredcites →https://doi.org/10.1016/b978-1-55860-332-5.50013-4openalex-snapshot
Approximation Algorithms for the Loop Cutset Problem
inferredcites →https://doi.org/10.1016/s0167-6377(98)00021-2openalex-snapshot
A primal–dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
inferredcites →https://doi.org/10.1016/s0196-6774(02)00291-2openalex-snapshot
Interval selection: Applications, algorithms, and lower bounds
inferredcites →https://doi.org/10.1016/s0304-3975(02)00414-0openalex-snapshot
On the approximability of the Steiner tree problem
inferredcites →https://doi.org/10.1057/palgrave.jors.2601377openalex-snapshot
Approximation Algorithms
inferredcites →https://doi.org/10.1109/sfcs.2002.1181954openalex-snapshot
Proving integrality gaps without knowing the linear program
inferredcites →https://doi.org/10.1137/0605024openalex-snapshot
Greedoids and Linear Objective Functions
inferredcites →https://doi.org/10.1137/s009753970240118xopenalex-snapshot
The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
inferredcites →https://doi.org/10.1137/s0097539792236237openalex-snapshot
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
inferredcites →https://doi.org/10.1137/s0097539793242618openalex-snapshot
A General Approximation Technique for Constrained Forest Problems
inferredcites →https://doi.org/10.1137/s0097539795286612openalex-snapshot
On Syntactic versus Computational Views of Approximability
inferredcites →https://doi.org/10.1145/237814.237991openalex-snapshot
A tight analysis of the greedy algorithm for set cover
inferredcites →https://doi.org/10.1145/258533.258641openalex-snapshot
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
inferredcites →https://doi.org/10.1145/261342.571216openalex-snapshot
Approximation Algorithms for NP-Hard Problems
inferredcites →https://doi.org/10.1145/285055.285059openalex-snapshot
A threshold of ln n for approximating set cover
inferredcites →https://doi.org/10.1145/335305.335401openalex-snapshot
Improvements in throughout maximization for real-time scheduling
inferredcites →https://doi.org/10.1145/375827.375845openalex-snapshot
Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
inferredcites →https://doi.org/10.1145/502102.502107openalex-snapshot
A unified approach to approximating resource allocation and scheduling
inferredcites →https://doi.org/10.1287/ijoc.1.3.181openalex-snapshot
On the Greedy Solution of Ordering Problems
inferredcites →https://doi.org/10.1287/opre.46.4.503openalex-snapshot
From Valid Inequalities to Heuristics: A Unified View of Primal-Dual Approximation Algorithms in Covering Problems
inferredcites →https://doi.org/10.5555/338219.338638openalex-snapshot
Improved Steiner tree approximation in graphs
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/11775096_1openalex-snapshot
Further Reflections on a Theory for Basic Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-642-02927-1_53openalex-snapshot
Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
inferred← citeshttps://doi.org/10.1007/978-3-642-03816-7_52openalex-snapshot
On the Structure of Optimal Greedy Computation (for Job Scheduling)
inferred← citeshttps://doi.org/10.1007/978-3-642-14165-2_9openalex-snapshot
On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions
inferred← citeshttps://doi.org/10.1007/s00037-011-0028-yopenalex-snapshot
Toward a Model for Backtracking and Dynamic Programming
inferred← citeshttps://doi.org/10.1007/s00453-007-9124-4openalex-snapshot
Models of Greedy Algorithms for Graph Problems
inferred← citeshttps://doi.org/10.1007/s00453-009-9385-1openalex-snapshot
A Stronger Model of Dynamic Programming Algorithms
inferred← citeshttps://doi.org/10.1007/s10951-009-0148-2openalex-snapshot
Characterizing sets of jobs that admit optimal greedy-like algorithms
inferred← citeshttps://doi.org/10.1016/j.tcs.2010.03.014openalex-snapshot
Randomized priority algorithms
inferred← citeshttps://doi.org/10.3390/wevj5030688openalex-snapshot
Routing EV Users Towards an Optimal Charging Plan
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.