approximation
47 entries in Optimization & Operations Research.
- Greedy set coverMaximum-coverage selectioncanonfull lesson ▸approximation
- LP rounding set coverRandomized roundingstandardapproximation
- Primal-dual set coverstandalonestandardapproximation
- Greedy vertex coverMaximal matchingcanonapproximation
- LP rounding vertex coverHalf-integralitystandardapproximation
- Local ratiostandalonespecialistapproximation
- Greedy max coverageSubmodular marginal gaincanonapproximation
- Lazy greedy submodularMarginal-gain cachingstandardapproximation
- Continuous greedyMultilinear extensionspecialistapproximation
- Pipage roundingstandalonespecialistapproximation
- ChristofidesMatching plus Euler tourcanonapproximation
- Double-tree TSPMST shortcuttingstandardapproximation
- Greedy k-centerFarthest-first traversalcanonapproximation
- Local search k-medianSwap improvementsstandardapproximation
- LP rounding facility locationFiltering and clusteringspecialistapproximation
- Primal-dual facility locationJain-Vaziranispecialistapproximation
- PTAS for knapsackProfit scalingstandardapproximation
- PTAS for Euclidean TSPArora dissectionspecialistapproximation
- PTAS for bin packingItem groupingspecialistapproximation
- First fit decreasing boundstandalonestandardapproximation
- Goemans-WilliamsonSDP roundingcanonapproximation
- Greedy max-cutLocal improvementstandardapproximation
- Randomized max-cutUniform partitionstandardapproximation
- SDP rounding coloringVector coloringspecialistapproximation
- Multiplicative weights LPPlotkin-Shmoys-Tardosspecialistapproximation
- Iterative LP roundingBasic feasible extreme pointsspecialistapproximation
- Randomized roundingChernoff concentrationstandardapproximation
- Dependent roundingstandalonespecialistapproximation
- Metric embeddingBourgain into L1specialistapproximation
- Tree metric approximationFRT random treesspecialistapproximation
- Sparsest cut approximationLeighton-Rao LPspecialistapproximation
- Sparsest cut approximationARV semidefinitespecialistapproximation
- Steiner tree approximationTerminal spanning treestandardapproximation
- Steiner tree approximationRobins-Zelikovskyspecialistapproximation
- Prize-collecting SteinerPrimal-dual growthspecialistapproximation
- Survivable network designJain iterative roundingspecialistapproximation
- Job scheduling approximationLongest processing timecanonapproximation
- Scheduling PTASstandalonespecialistapproximation
- Unrelated machines roundingLenstra-Shmoys-Tardosspecialistapproximation
- Bin covering approximationstandalonespecialistapproximation
- Knapsack greedyDensity ratio with best single itemstandardapproximation
- Max-SAT approximationRandomized assignmentstandardapproximation
- Johnson's max-SATstandalonespecialistapproximation
- Local search max-SATGSAT flipsspecialistapproximation
- Approximate diameterDouble BFSstandardapproximation
- Coreset constructionSensitivity samplingspecialistapproximation
- Streaming submodularThreshold greedyspecialistapproximation