On the public citation graph
The primal-dual method for approximation algorithms
0 signed · 106 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.1002/nav.3800020109openalex-snapshot
The Hungarian method for the assignment problem
inferredcites →https://doi.org/10.1002/net.3230190602openalex-snapshot
The prize collecting traveling salesman problem
inferredcites →https://doi.org/10.1006/jagm.1998.0995openalex-snapshot
Approximating Node-Deletion Problems for Matroidal Properties
inferredcites →https://doi.org/10.1006/jcss.1998.1587openalex-snapshot
Zero Knowledge and the Chromatic Number
inferredcites →https://doi.org/10.1007/3-540-61310-2_12openalex-snapshot
Primal-dual approximation algorithms for feedback problems in planar graphs
inferredcites →https://doi.org/10.1007/978-0-8176-4842-8_15openalex-snapshot
Maximal Flow Through a Network
inferredcites →https://doi.org/10.1007/978-0-8176-4842-8_26openalex-snapshot
Paths, Trees, and Flowers
inferredcites →https://doi.org/10.1007/bf01386390openalex-snapshot
A note on two problems in connexion with graphs
inferredcites →https://doi.org/10.1007/bf01580113openalex-snapshot
Matching, Euler tours and the Chinese postman
inferredcites →https://doi.org/10.1007/bf01585864openalex-snapshot
An efficient approximation algorithm for the survivable network design problem
inferredcites →https://doi.org/10.1007/bf02392825openalex-snapshot
Clique is hard to approximate within n1−ε
inferredcites →https://doi.org/10.1007/bf02523685openalex-snapshot
Primal-dual approximation algorithms for integral flow and multicut in trees
inferredcites →https://doi.org/10.1007/bf02612335openalex-snapshot
A dual ascent approach for steiner tree problems on a directed graph
inferredcites →https://doi.org/10.1007/s004530010009openalex-snapshot
One for the Price of Two: a Unified Approach for Approximating Covering Problems
inferredcites →https://doi.org/10.1007/s004930170004openalex-snapshot
A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem
inferredcites →https://doi.org/10.1007/s10107-003-0479-2openalex-snapshot
Approximate k -MSTs and k -Steiner trees via the primal-dual method and Lagrangean relaxation
inferredcites →https://doi.org/10.1007/springerreference_57547openalex-snapshot
Approximation Algorithms
inferredcites →https://doi.org/10.1016/0004-3702(95)00004-6openalex-snapshot
Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
inferredcites →https://doi.org/10.1016/0020-0190(94)00156-1openalex-snapshot
A data structure for bicategories, with application to speeding up an approximation algorithm
inferredcites →https://doi.org/10.1016/0167-6377(94)90067-1openalex-snapshot
Approximating minimum-cost graph problems with spanning tree edges
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/s0022-0000(74)80044-9openalex-snapshot
Approximation algorithms for combinatorial problems
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/s0304-0208(08)73101-3openalex-snapshot
A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem
inferredcites →https://doi.org/10.1090/dimacs/020/07openalex-snapshot
Computing near-optimal solutions to combinatorial optimization problems
inferredcites →https://doi.org/10.1090/s0002-9939-1956-0078686-7openalex-snapshot
On the shortest spanning subtree of a graph and the traveling salesman problem
inferredcites →https://doi.org/10.1109/sfcs.1992.267823openalex-snapshot
Proof verification and hardness of approximation problems
inferredcites →https://doi.org/10.1109/sfcs.1996.548489openalex-snapshot
A 3-approximation for the minimum tree spanning k vertices
inferredcites →https://doi.org/10.1109/sfcs.1996.548522openalex-snapshot
Clique is hard to approximate within n/sup 1-ε/
inferredcites →https://doi.org/10.1109/sffcs.1999.814571openalex-snapshot
Primal-dual approximation algorithms for metric facility location and k-median problems
inferredcites →https://doi.org/10.1109/sffcs.1999.814609openalex-snapshot
Improved combinatorial algorithms for the facility location and k-median problems
inferredcites →https://doi.org/10.1137/0211045openalex-snapshot
Approximation Algorithms for the Set Covering and Vertex Cover Problems
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/s0097539796302531openalex-snapshot
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
inferredcites →https://doi.org/10.1137/s0097539796305109openalex-snapshot
Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
inferredcites →https://doi.org/10.1137/s0895480195291874openalex-snapshot
Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
inferredcites →https://doi.org/10.1137/s0895480196305124openalex-snapshot
A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
inferredcites →https://doi.org/10.1145/167088.167174openalex-snapshot
Efficient probabilistically checkable proofs and applications to approximations
inferredcites →https://doi.org/10.1145/167088.167268openalex-snapshot
A primal-dual approximation algorithm for generalized Steiner network problems
inferredcites →https://doi.org/10.1145/185675.306789openalex-snapshot
On the hardness of approximating minimization problems
inferredcites →https://doi.org/10.1145/226643.226652openalex-snapshot
Interactive proofs and the hardness of approximating cliques
inferredcites →https://doi.org/10.1145/258533.258536openalex-snapshot
Some optimal inapproximability results
inferredcites →https://doi.org/10.1145/261342.571216openalex-snapshot
Approximation Algorithms for NP-Hard Problems
inferredcites →https://doi.org/10.1145/273865.273901openalex-snapshot
Probabilistic checking of proofs
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.335320openalex-snapshot
On the approximability of the traveling salesman problem (extended abstract)
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.8.1.29openalex-snapshot
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances
inferredcites →https://doi.org/10.1287/mnsc.12.3.253openalex-snapshot
Integer Programming: Methods, Uses, Computations
inferredcites →https://doi.org/10.1287/opre.26.6.992openalex-snapshot
A Dual-Based Procedure for Uncapacitated Facility Location
inferredcites →https://doi.org/10.1287/opre.37.5.716openalex-snapshot
A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design
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.1515/9781400881987-008openalex-snapshot
7* A Primal-Dual Algorithm for Linear Programs
inferredcites →https://doi.org/10.2307/2322374openalex-snapshot
Combinatorial Optimization: Algorithms and Complexity.
inferredcites →https://doi.org/10.5555/313852.314074openalex-snapshot
A commercial application of survivable network design: ITP/INPLANS CCS network topology analyzer
inferredcites →https://doi.org/10.5555/314464.314497openalex-snapshot
Improved approximation algorithms for network design problems
inferredcites →https://doi.org/10.5555/338219.338637openalex-snapshot
The prize collecting Steiner tree problem: theory and practice
inferredcites →https://doi.org/10.5555/34233.34235openalex-snapshot
Steiner problem in networks: a survey
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/11523468_76openalex-snapshot
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?
inferred← citeshttps://doi.org/10.1007/11561071_63openalex-snapshot
Using Fractional Primal-Dual to Schedule Split Intervals with Demands
inferred← citeshttps://doi.org/10.1007/3-540-44666-4_7openalex-snapshot
On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique
inferred← citeshttps://doi.org/10.1007/3-540-45753-4_22openalex-snapshot
Primal-Dual Algorithms for Connected Facility Location Problems
inferred← citeshttps://doi.org/10.1007/978-1-4614-1701-9openalex-snapshot
Design and Analysis of Approximation Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-030-38819-5_8openalex-snapshot
Batch Auction Design for Cloud Container Services
inferred← citeshttps://doi.org/10.1007/978-3-642-12139-5_22openalex-snapshot
A New Primal-Dual Genetic Algorithm: Case Study for the Winner Determination Problem
inferred← citeshttps://doi.org/10.1007/s00453-004-1112-3openalex-snapshot
Primal–Dual Algorithms for Connected Facility Location Problems
inferred← citeshttps://doi.org/10.1007/s00453-020-00718-2openalex-snapshot
Improved Solution to Data Gathering with Mobile Mule
inferred← citeshttps://doi.org/10.1007/s10878-014-9753-xopenalex-snapshot
The $$k$$ k -separator problem: polyhedra, complexity and approximation results
inferred← citeshttps://doi.org/10.1007/s10878-020-00653-6openalex-snapshot
An approximation algorithm for submodular hitting set problem with linear penalties
inferred← citeshttps://doi.org/10.1007/s11036-020-01626-zopenalex-snapshot
Batch Auction Design for Cloud Container Services
inferred← citeshttps://doi.org/10.1016/j.dam.2005.05.027openalex-snapshot
Worst-case performance of Wong's Steiner tree heuristic
inferred← citeshttps://doi.org/10.1016/j.disopt.2006.05.010openalex-snapshot
Using fractional primal–dual to schedule split intervals with demands
inferred← citeshttps://doi.org/10.1016/j.sorms.2010.06.001openalex-snapshot
Approximation algorithms for network design: A survey
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.06.003openalex-snapshot
Combination of parallel machine scheduling and vertex cover
inferred← citeshttps://doi.org/10.1016/s0166-218x(02)00201-9openalex-snapshot
A primal–dual approximation algorithm for the survivable network design problem in hypergraphs
inferred← citeshttps://doi.org/10.1017/cbo9780511921735openalex-snapshot
The Design of Approximation Algorithms
inferred← citeshttps://doi.org/10.1023/b:aurc.0000014716.77510.61openalex-snapshot
Committees of Systems of Linear Inequalities
inferred← citeshttps://doi.org/10.1109/bibm.2014.6999213openalex-snapshot
A matching framework for modeling symptom and medication relationships from clinical notes
inferred← citeshttps://doi.org/10.1109/comst.2017.2647981openalex-snapshot
Resource Management in Cloud Networking Using Economic Analysis and Pricing Models: A Survey
inferred← citeshttps://doi.org/10.1109/icnc.2012.11openalex-snapshot
Approximate Algorithms for Survivable Network Design
inferred← citeshttps://doi.org/10.1109/infcom.2009.5061986openalex-snapshot
Hardness and Approximation of the Survivable Multi-Level Fat Tree Problem
inferred← citeshttps://doi.org/10.1109/pccc.2010.5682314openalex-snapshot
A primal-dual approximation algorithm for the Minimum Cost Stashing problem in wireless sensor networks
inferred← citeshttps://doi.org/10.1109/pccc.2017.8280458openalex-snapshot
A truthful auction mechanism for resource provisioning in mobile crowdsensing
inferred← citeshttps://doi.org/10.1109/pdcat.2011.41openalex-snapshot
Fast Fault-Tolerant Resource Allocation
inferred← citeshttps://doi.org/10.1109/sfcs.2002.1181956openalex-snapshot
A constant-factor approximation algorithm for the multicommodity rent-or-buy problem
inferred← citeshttps://doi.org/10.1109/tac.2014.2365686openalex-snapshot
Distributed Optimization With Local Domains: Applications in MPC and Network Flows
inferred← citeshttps://doi.org/10.1109/tc.2011.123openalex-snapshot
Efficient 2-Approximation Algorithms for Computing 2-Connected Steiner Minimal Networks
inferred← citeshttps://doi.org/10.1109/tsg.2013.2245155openalex-snapshot
Smart Grid Data Integrity Attacks
inferred← citeshttps://doi.org/10.1137/050625382openalex-snapshot
On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
inferred← citeshttps://doi.org/10.1142/s0129054117500344openalex-snapshot
Improved Approximation Algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover
inferred← citeshttps://doi.org/10.1145/1978782.1978784openalex-snapshot
How well can primal-dual and local-ratio algorithms perform?
inferred← citeshttps://doi.org/10.32657/10356/59538openalex-snapshot
Online test paper generation for a web-based mathematics testing environment
inferred← citeshttps://doi.org/10.3934/jimo.2015.11.575openalex-snapshot
The set covering problem revisited: An empirical study of the value of dual information
inferred← citeshttps://doi.org/10.47749/t/unicamp.2006.400629openalex-snapshot
Aproximação e compartilhamento de custos em projeto de redes
inferred← citeshttps://doi.org/10.48550/arxiv.1305.3584openalex-snapshot
New Greedy Heuristics For Set Cover and Set Packing
inferred← citeshttps://doi.org/10.5204/thesis.eprints.238538openalex-snapshot
Creating a novel region finding approach to provide good solutions to mixed-integer problems
inferred← citeshttps://doi.org/10.5281/zenodo.21733266openalex-snapshot
Medical Papers Cluster Supported Medication-Symptom Names Using Multi Read Nonnegative Matrix Factorization
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.