Approximation algorithms for combinatorial problems
From MaRDI portal
Publication:1213733
DOI10.1016/S0022-0000(74)80044-9zbMath0296.65036OpenAlexW2040924621WikidataQ56338199 ScholiaQ56338199MaRDI QIDQ1213733
Publication date: 1974
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(74)80044-9
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Permutations, words, matrices (05A05) Coloring of graphs and hypergraphs (05C15) Algorithms in computer science (68W99)
Related Items
Siting renewable power generation assets with combinatorial optimisation ⋮ On parallelizing a greedy heuristic for finding small dominant sets ⋮ Solving the maximum clique problem using a tabu search approach ⋮ Scheduling with constrained processor allocation for interval orders ⋮ An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT ⋮ Approximation schemes for parallel machine scheduling problems with controllable processing times ⋮ An approximate max-flow min-cut relation for undirected multicommodity flow, with applications ⋮ Construction of component tapes for radial placement machines ⋮ Approximability of identifying codes and locating-dominating codes ⋮ Scheduling of conditional executed jobs on unrelated processors ⋮ On specifying Boolean functions by labelled examples ⋮ Feedback vertex sets in mesh-based networks ⋮ Separation and approximation of polyhedral objects ⋮ Almost optimal set covers in finite VC-dimension ⋮ Tight approximation bounds for combinatorial frugal coverage algorithms ⋮ Homogeneous grouping of non-prime steel products for online auctions: a case study ⋮ A primal-dual approximation algorithm for \textsc{minsat} ⋮ Simple decentralized graph coloring ⋮ A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph ⋮ Approximating activation edge-cover and facility location problems ⋮ Feeder routing for air-to-air refueling operations ⋮ Diversification strategies in tabu search algorithms for the maximum clique problem ⋮ Formal methods for reasoning and uncertainty reduction in evidential grid maps ⋮ Approximating set multi-covers ⋮ Network design under general wireless interference ⋮ Local ratio method on partial set multi-cover ⋮ Unrelated parallel machine scheduling with new criteria: complexity and models ⋮ A MILP model and two heuristics for the bin packing problem with conflicts and item fragmentation ⋮ Strengthening hash families and compressive sensing ⋮ On the computational complexities of three problems related to a privacy measure for large networks under active attack ⋮ Robust fitting in computer vision: easy or hard? ⋮ An improved approximation algorithm for the minimum 3-path partition problem ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ Approximation of the quadratic set covering problem ⋮ Minimize the maximum duty in multi-interface networks ⋮ A taxonomy of exact methods for partial Max-SAT ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Approximating minimum cost source location problems with local vertex-connectivity demands ⋮ Solving the weighted MAX-SAT problem using the dynamic convexized method ⋮ The decycling number of outerplanar graphs ⋮ Computational complexity of recognition learning procedures in the class of piecewise-linear committee decision rules ⋮ Max NP-completeness made easy ⋮ How to guard a graph against tree moves ⋮ Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP ⋮ On approximation of the submodular set cover problem ⋮ \(\boldsymbol{borealis}\) -- a generalized global update algorithm for Boolean optimization problems ⋮ MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability ⋮ Online budgeted maximum coverage ⋮ Inapproximability results for the lateral gene transfer problem ⋮ Approximating the online set multicover problems via randomized winnowing ⋮ Approximating a vehicle scheduling problem with time windows and handling times ⋮ Restricted parameter range promise set cover problems are easy ⋮ Tight approximability results for test set problems in bioinformatics ⋮ Approximation algorithm for the partial set multi-cover problem ⋮ Reductions, completeness and the hardness of approximability ⋮ Discrete sensor placement problems in distribution networks ⋮ On the probabilistic minimum coloring and minimum \(k\)-coloring ⋮ A hybrid heuristic for the maximum clique problem ⋮ A study of ACO capabilities for solving the maximum clique problem ⋮ A modified greedy algorithm for dispersively weighted 3-set cover ⋮ Hedging uncertainty: approximation algorithms for stochastic optimization problems ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Heuristic search of exact biclusters in binary data ⋮ Approximation algorithm for the multicovering problem ⋮ Bin packing problem with conflicts and item fragmentation ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ On influence, stable behavior, and the most influential individuals in networks: a game-theoretic approach ⋮ Algorithmic aspects of upper edge domination ⋮ A multi-objective integrated facility location-hardening model: analyzing the pre- and post-disruption tradeoff ⋮ Approximation algorithm for stochastic set cover problem ⋮ Empirical study of the greedy heuristic as applied to the link selection problem ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting ⋮ A primal-dual algorithm for the minimum partial set multi-cover problem ⋮ On the induced matching problem in Hamiltonian bipartite graphs ⋮ A new proof of the Larman-Rogers upper bound for the chromatic number of the Euclidean space ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Computing a small agreeable set of indivisible items ⋮ Computing in combinatorial optimization ⋮ Landmarks in graphs ⋮ A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem ⋮ Techniques and results on approximation algorithms for packing circles ⋮ A primal-dual algorithm for the minimum power partial cover problem ⋮ Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty ⋮ Scheduling orders for multiple product types with due date related objectives ⋮ Hierarchical heuristics for Boolean-reasoning-based binary bicluster induction ⋮ A local search 4/3-approximation algorithm for the minimum 3-path partition problem ⋮ Approximation algorithms for covering/packing integer programs ⋮ Approximating minimum cocolorings. ⋮ The inapproximability of non-NP-hard optimization problems. ⋮ A sharp threshold for the renameable-Horn and the \(q\)-Horn properties ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ An improved approximation algorithm for vertex cover with hard capacities ⋮ Capacitated domination: problem complexity and approximation algorithms ⋮ Learning residual alternating automata ⋮ Mining circuit lower bound proofs for meta-algorithms ⋮ A fuzzy genetic algorithm for driver scheduling ⋮ A simple greedy algorithm for finding functional relations: Efficient implementation and average case analysis ⋮ Tight bounds on subexponential time approximation of set cover and related problems ⋮ Constant round distributed domination on graph classes with bounded expansion ⋮ Tight approximation bounds for maximum multi-coverage ⋮ A-priori upper bounds for the set covering problem ⋮ It is hard to know when greedy is good for finding independent sets ⋮ Models of greedy algorithms for graph problems ⋮ Improved performance of the greedy algorithm for partial cover ⋮ Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat} ⋮ Simplified tight analysis of Johnson's algorithm ⋮ Minimizing the stretch when scheduling flows of divisible requests ⋮ Feedback vertex set in hypercubes ⋮ Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs ⋮ A heuristic for the stability number of a graph based on convex quadratic programming and tabu search ⋮ A hybrid Lagrangean heuristic with GRASP and path-relinking for set \(k\)-covering ⋮ A nonmonotone GRASP ⋮ Towards the price of leasing online ⋮ New primal-dual algorithms for Steiner tree problems ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks ⋮ Time slot scheduling of compatible jobs ⋮ Survivable network activation problems ⋮ A variable neighborhood search algorithm for the multimode set covering problem ⋮ Identifying path covers in graphs ⋮ Lower and upper bounds for the bin packing problem with fragile objects ⋮ Scheduling large-scale micro/nano biochemical testing: Exact and heuristic algorithms ⋮ Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs ⋮ On the approximability of covering points by lines and related problems ⋮ Uniform unweighted set cover: the power of non-oblivious local search ⋮ A unified approach to approximating partial covering problems ⋮ Computing optimal islands ⋮ Approximating the traffic grooming problem in tree and star networks ⋮ Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem ⋮ Probabilistic bounds and algorithms for the maximum satisfiability problem ⋮ A survey on the structure of approximation classes ⋮ Circulant graphs and GCD and LCM of subsets ⋮ On finding the longest antisymmetric path in directed acyclic graphs ⋮ Three optimizations for assume-guarantee reasoning with \(L^{*}\) ⋮ The computational complexity and approximability of a series of geometric covering problems ⋮ Dominance guarantees for above-average solutions ⋮ Approximate solution of NP optimization problems ⋮ Rounding to an integral program ⋮ Computing functions with parallel queries to NP ⋮ A parallel algorithm for the minimum weighted vertex cover problem ⋮ Approximating Max NAE-\(k\)-SAT by anonymous local search ⋮ Separating sets of strings by finding matching patterns is almost always hard ⋮ Randomized approximation of bounded multicovering problems ⋮ Learning discrete decomposable graphical models via constraint optimization ⋮ Approximate clustering of incomplete fingerprints ⋮ A note on the descriptive complexity of maximization problems ⋮ Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles ⋮ The minimum substring cover problem ⋮ On the relation between rough set reducts and typical testors ⋮ A biased random-key genetic algorithm for the Steiner triple covering problem ⋮ Capacitated domination problem ⋮ Pseudo-Boolean optimization ⋮ Approximation algorithms for art gallery problems in polygons ⋮ Approximating minimum-power degree and connectivity problems ⋮ Variable neighborhood search for the maximum clique ⋮ A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership ⋮ New lower bounds for bin packing problems with conflicts ⋮ Domination in graphs with bounded propagation: Algorithms, formulations and hardness results ⋮ An efficient algorithm for minimum feedback vertex sets in rotator graphs ⋮ Approximation of min coloring by moderately exponential algorithms ⋮ Min-sum bin packing ⋮ Covering compact metric spaces greedily ⋮ The ordered covering problem ⋮ Indirect unstructured hex-dominant mesh generation using tetrahedra recombination ⋮ Partial covering arrays: algorithms and asymptotics ⋮ Probabilistic graph-coloring in bipartite and split graphs ⋮ Hitting sets online and unique-MAX coloring ⋮ On the distribution of the domination number for random class cover catch digraphs ⋮ A randomised approximation algorithm for the hitting set problem ⋮ Minimum partition of an independence system into independent sets ⋮ Teachability in computational learning ⋮ Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees ⋮ Path hitting in acyclic graphs ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms ⋮ Algorithms for the maximum satisfiability problem ⋮ An application of the greedy heuristic of set cover to traffic checks ⋮ Approximability of minimum AND-circuits ⋮ Connected domination of regular graphs ⋮ Independent sets in bounded-degree hypergraphs ⋮ On approximation problems related to the independent set and vertex cover problems ⋮ Before and after vacuity ⋮ The greedy algorithm for domination in graphs of maximum degree 3 ⋮ On the hardness of approximating label-cover ⋮ Improved approximability and non-approximability results for graph diameter decreasing problems ⋮ On two restricted ancestors tree problems ⋮ Weighted sum coloring in batch scheduling of conflicting jobs ⋮ Parameterized learnability of juntas ⋮ Models and heuristic algorithms for a weighted vertex coloring problem ⋮ Computational study on planar dominating set problem ⋮ Covering the edges of bipartite graphs using \(K_{2,2}\) graphs ⋮ Priority algorithms for graph optimization problems ⋮ Absolute \(o(\log m)\) error in approximating random set covering: an average case analysis ⋮ Vertex covering by paths on trees with its applications in machine translation ⋮ Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses ⋮ Efficient bounds for the stable set, vertex cover and set packing problems ⋮ Probabilistic behaviour of optimal bin-packing solutions ⋮ The conjunctive complexity of quadratic Boolean functions ⋮ Completeness in approximation classes ⋮ Consistency-based search in feature selection ⋮ Randomized approximation for the set multicover problem in hypergraphs ⋮ Tight Approximation Bounds for Maximum Multi-coverage ⋮ A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets ⋮ Safe Approximation and Its Relation to Kernelization ⋮ Near-Linear Query Complexity for Graph Inference ⋮ Local Search to Approximate Max NAE-$$k$$-Sat Tightly ⋮ Recent results in hardness of approximation ⋮ Some recent strong inapproximability results ⋮ Improved Upper Bounds for Partial Vertex Cover ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ An Improved Approximation Bound for Spanning Star Forest and Color Saving ⋮ An Efficient Approximation Algorithm for Finding a Maximum Clique Using Hopfield Network Learning ⋮ APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS ⋮ Partial Resampling to Approximate Covering Integer Programs ⋮ An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem ⋮ Randomized Online Algorithms for Set Cover Leasing Problems ⋮ On the approximability of the maximum common subgraph problem ⋮ Approximation algorithms for a genetic diagnostics problem ⋮ Intractability of assembly sequencing: Unit disks in the plane ⋮ Constructive Relationships Between Algebraic Thickness and Normality ⋮ Approximability results for the $p$-centdian and the converse centdian problems ⋮ Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry ⋮ Unnamed Item ⋮ Structure in approximation classes ⋮ Detecting arrays for effects of single factors ⋮ Technical Note—Online Hypergraph Matching with Delays ⋮ A hybrid heuristic for the rectilinear picture compression problem ⋮ Bayesian nonparametrie inference and monte carlo optimization ⋮ Rseslib 3: Open Source Library of Rough Set and Machine Learning Methods ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ Computing and ranking measures of presortedness ⋮ An Adaptive Neighborhood Search for k-Clustering Minimum Bi-clique Completion Problems ⋮ Worst case analysis of two heuristics for the set partitioning problem ⋮ Sublinear-space approximation algorithms for Max \(r\)-SAT ⋮ Parameterized Learnability of k-Juntas and Related Problems ⋮ Covering a Graph with Clubs ⋮ Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs ⋮ When polynomial approximation meets exact computation ⋮ The Computational Complexity of and Approximation Algorithms for Variants of the Component Selection Problem ⋮ An efficient distributed algorithm for constructing small dominating sets ⋮ Capacitated Domination Problem ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Spanning Trees With Edge Conflicts and Wireless Connectivity ⋮ Monitoring the edges of a graph using distances ⋮ Tight Approximation Bounds for Greedy Frugal Coverage Algorithms ⋮ MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS ⋮ Absolute bounds on optimal cost for a class of set covering problems ⋮ Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands ⋮ VC-Dimension and Shortest Path Algorithms ⋮ Approximating k-set cover and complementary graph coloring ⋮ When polynomial approximation meets exact computation ⋮ Modeling and algorithmic development of a staff scheduling problem ⋮ Minimizing number of wavelengths in multicast routing trees in WDM networks ⋮ Approximation of some NP-hard optimization problems by finite machines, in probability ⋮ Sublinear Graph Approximation Algorithms ⋮ Worst-case analysis of greedy algorithms for the subset-sum problem ⋮ Approximating maximum independent sets by excluding subgraphs ⋮ On Partial Covers, Reducts and Decision Rules ⋮ On a minimum linear classification problem ⋮ The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem ⋮ Unnamed Item ⋮ The Minimum Substring Cover Problem ⋮ Minimum Weighted Sum Bin Packing ⋮ Approximate algorithms for generalized maximum utility problems ⋮ Mixed fault tolerance in server assignment: combining reinforcement and backup ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ On the primer selection problem in polymerase chain reaction experiments ⋮ Computing coverage kernels under restricted settings ⋮ Approximation algorithms for minimum weight partial connected set cover problem ⋮ Constant-time distributed dominating set approximation ⋮ On the independent set problem in random graphs ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Min-Max Coverage in Multi-interface Networks ⋮ Upper and lower bounds on approximating weighted mixed domination ⋮ Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP ⋮ Unnamed Item ⋮ On Geometric Set Cover for Orthants ⋮ On Multiple Coverings of Fixed Size Containers with Non-Euclidean Metric by Circles of Two Types ⋮ Approximation Algorithms for Edge-Covering Problem ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ On the Approximability of Some Haplotyping Problems ⋮ On the complexity of approximating the independent set problem ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ Sparse Stretching for Solving Sparse-Dense Linear Least-Squares Problems ⋮ An ex-post bound on the greedy heuristic for the uncapacitated facility location problem ⋮ Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Spanner Approximation ⋮ Heuristics for the fixed cost median problem ⋮ Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata ⋮ Parameterized Algorithms for Generalized Domination ⋮ On the Greedy Heuristic for Continuous Covering and Packing Problems ⋮ Unnamed Item ⋮ Selecting Complementary Pairs of Literals ⋮ Worst case analysis of a class of set covering heuristics ⋮ Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds ⋮ Decision Trees for Geometric Models ⋮ Upper Bounds on the Size of Covering Arrays ⋮ Minimum Power Dominating Sets of Random Cubic Graphs ⋮ Hybrid branch-and-price-and-cut algorithm for the two-dimensional vector packing problem with time windows ⋮ Real-time passenger bus routing problems with preferences and tradeoffs ⋮ Feasible rounding based diving strategies in branch-and-bound methods for mixed-integer optimization ⋮ Algorithmic results on locating-total domination in graphs ⋮ A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts ⋮ Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs ⋮ Approximating minimum keys and optimal substructure screens ⋮ The complexity of spanning tree problems involving graphical indices ⋮ An asymptotically exact polynomial algorithm for equipartition problems ⋮ Theory refinement combining analytical and empirical methods ⋮ Equivalent approximation algorithms for node cover ⋮ A graph approximation heuristic for the vertex cover problem on planar graphs ⋮ On a combinatorial framework for fault characterization ⋮ Implications of forbidden structures for extremal algorithmic problems ⋮ A modified greedy heuristic for the set covering problem with improved worst case bound ⋮ A short note on the approximability of the maximum leaves spanning tree problem ⋮ Continuous optimization problems and a polynomial hierarchy of real functions ⋮ Uniquely identifying the edges of a graph: the edge metric dimension ⋮ Optimal attribute sets for identifications and diagnoses ⋮ A theory for memory-based learning ⋮ Conditional covering: greedy heuristics and computational results ⋮ Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Dividing strategies for the optimization of a test suite ⋮ Approximability of maximum splitting of k-sets and some other Apx-complete problems ⋮ Dynamic algorithms via the primal-dual method ⋮ On approximation algorithms for the minimum satisfiability problem ⋮ New local search approximation techniques for maximum generalized satisfiability problems ⋮ Optima of dual integer linear programs ⋮ Quantifying inductive bias: AI learning algorithms and Valiant's learning framework ⋮ BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem ⋮ The complexity and approximability of finding maximum feasible subsystems of linear relations ⋮ Pick-and-choose heuristics for partial set covering ⋮ Rounding algorithms for covering problems ⋮ Selection of relevant features and examples in machine learning ⋮ Recognizing polygonal parts width measurements ⋮ Efficient delay routing ⋮ A simple approximation algorithm for minimum weight partial connected set cover ⋮ The probabilistic minimum dominating set problem ⋮ Backtracking with multi-level dynamic search rearrangement ⋮ Structure preserving reductions among convex optimization problems ⋮ Approximating covering integer programs with multiplicity constraints ⋮ Discrete extremal problems ⋮ Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem ⋮ Sparsification and subexponential approximation ⋮ Algorithms for graphs with small octopus ⋮ On the relationship between the biconnectivity augmentation and traveling salesman problems ⋮ Evaluation of reliability bounds by set covering models. ⋮ Approximation algorithms for hitting objects with straight lines ⋮ Lower bounds on the stability number of graphs computed in terms of degrees ⋮ Greedy domination on biclique-free graphs ⋮ \((\delta ,\varepsilon)\)-ball approximation of a shape: definition and complexity ⋮ Analysis of a greedy heuristic for finding small dominating sets in graphs ⋮ Complexity of the repeaters allocating problem ⋮ Computational study on a PTAS for planar dominating set problem ⋮ On the complexity of approximating the independent set problem ⋮ Optimization, approximation, and complexity classes ⋮ Parallel and serial heuristics for the minimum set cover problem ⋮ Learning in parallel ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ FPT algorithms for domination in sparse graphs and beyond ⋮ Asymptotic and constructive methods for covering perfect hash families and covering arrays ⋮ Simple approximation algorithms for balanced MAX~2SAT ⋮ Towards flexible demands in online leasing problems ⋮ Performance of a neural network method with set partitioning ⋮ Processor optimization for flow graphs ⋮ The multicovering problem ⋮ Quantifiers and approximation ⋮ Optimal covering designs: complexity results and new bounds ⋮ Approximating the dense set-cover problem ⋮ On approximating the b-chromatic number ⋮ Heuristics and lower bounds for the bin packing problem with conflicts ⋮ On the differential approximation of MIN SET COVER ⋮ Polynomial approximation algorithms with performance guarantees: an introduction-by-example ⋮ Some simplified NP-complete graph problems ⋮ Chromatic numbers of spheres ⋮ Approximate algorithms for some generalized knapsack problems ⋮ Resource constrained scheduling as generalized bin packing ⋮ Lift-and-project methods for set cover and knapsack ⋮ Stochastic on-line knapsack problems ⋮ Binary interactions and subset choice ⋮ Alphabet indexing for approximating features of symbols ⋮ Differential approximation algorithms for some combinatorial optimization problems ⋮ Integer programming as a framework for optimization and approximability ⋮ A new linear storage, polynomial-time approximation scheme for the subset-sum problem ⋮ Computational experience with approximation algorithms for the set covering problem ⋮ Heuristic methods and applications: A categorized survey ⋮ How good are branching rules in DPLL? ⋮ On the approximability of the Steiner tree problem in phylogeny ⋮ Bounds for optimal coverings ⋮ Lower bounds on the independence number in terms of the degrees ⋮ A neural network for the minimum set covering problem ⋮ Interactive and probabilistic proof-checking ⋮ An analysis of the greedy algorithm for the submodular set covering problem ⋮ Approximating the weight of shallow Steiner trees ⋮ Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT ⋮ Clique is hard to approximate within \(n^{1-\epsilon}\) ⋮ Generalized submodular cover problems and applications ⋮ Tight bound on Johnson's algorithm for maximum satisfiability ⋮ Minimal approximate hitting sets and rule templates ⋮ Pareto optimality and a class of set covering heuristics ⋮ Approximation algorithms for terrain guarding. ⋮ The maximum clique problem ⋮ Approximation schemes for the subset-sum problem: Survey and experimental analysis ⋮ On bounded occurrence constraint satisfaction ⋮ Decomposing a set of points into chains, with applications to permutation and circle graphs ⋮ Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. ⋮ Independence and the Havel-Hakimi residue ⋮ Sparse approximate multiquadric interpolation
Cites Work
