[go: up one dir, main page]

Grossman et al., 1997 - Google Patents

Computational experience with approximation algorithms for the set covering problem

Grossman et al., 1997

View PDF
Document ID
15718109207689680555
Author
Grossman T
Wool A
Publication year
Publication venue
European journal of operational research

External Links

Snippet

The Set Covering problem (SCP) is a well known combinatorial optimization problem, which is NP-hard. We conducted a comparative study of nine different approximation algorithms for the SCP, including several greedy variants, fractional relaxations, randomized algorithms …
Continue reading at www.academia.edu (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/50—Computer-aided design
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a programme unit and a register, e.g. for a simultaneous processing of several programmes
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06N—COMPUTER SYSTEMS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computer systems based on biological models
    • G06N3/12—Computer systems based on biological models using genetic models
    • G06N3/126—Genetic algorithms, i.e. information processing using digital simulations of the genetic system
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06N—COMPUTER SYSTEMS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computer systems based on biological models
    • G06N3/02—Computer systems based on biological models using neural network models
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06Q—DATA PROCESSING SYSTEMS OR METHODS, SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management

Similar Documents

Publication Publication Date Title
Grossman et al. Computational experience with approximation algorithms for the set covering problem
US6031984A (en) Method and apparatus for optimizing constraint models
Radner The organization of decentralized information processing
Kruskal et al. A complexity theory of efficient parallel algorithms
Compton et al. A uniform method for proving lower bounds on the computational complexity of logical theories
Akutsu et al. Algorithms for identifying Boolean networks and related biological networks based on matrix multiplication and fingerprint function
Alon et al. Efficient testing of bipartite graphs for forbidden induced subgraphs
Bacci et al. Tensor of quantitative equational theories
Kuno et al. A Lagrangian based branch-and-bound algorithm for production-transportation problems
Aytug et al. A Markov chain analysis of genetic algorithms with power of 2 cardinality alphabets
Gairing et al. Structure and complexity of extreme Nash equilibria
Alon et al. On-line and off-line approximation algorithms for vector covering problems
Resende et al. Interior point algorithms for network flow problems
Pardalos et al. On the expected optimal value of random assignment problems: Experimental results and open questions
Allen et al. Counting, Ranking, and Randomly Generating CP-Nets.
Rajasekaran et al. Randomized parallel computation
Lam et al. Three new combination algorithms with the minimal change property
Shiny et al. Computation of prime implicants using matrix and paths
Condon A Theory of Strict P-completeness
Saxena et al. On parallel prefix computation
Brodal et al. Deterministic Cache-Oblivious Funnelselect
Gawrychowski et al. Minimax trees in linear time with applications
Valero-Garcia et al. Systematic hardware adaptation of systolic algorithms
Hu et al. Optimal alphabetic trees for binary search
Junges et al. On Gröbner bases in SMT-compliant decision procedures