Paroids: A canonical format for combinatorial optimization
type: Item
instance of: scholarly article
title: Paroids: A canonical format for combinatorial optimization
zbMATH Open document ID: 0771.05027
DOI: 10.1016/0166-218X(92)90113-O
author: Ronald L. Rardin
author: Moises Sudit
published in: Discrete Applied Mathematics
publication date: 1993-01-16T00:00:00Z
review text: A paroid is a matroid with ground set \(E\) and family of independent sets \(I\), and a partition \(E_ 1,E_ 2,\dots,E_ p\) of \(E\). A paroid independent set is the union of some subsets \(E_ i\) if it belongs to \(I\). The authors consider the problem of finding maximum weight paroid independent sets or bases. If \(| E_ i|=k\) for every \(i\), this reduces to the \(k\)-polymatroid matching problem which includes \(k\)- matroid intersection and matching. However, it also includes travelling salesman, vertex packing, satisfiability, graph partitioning and knapsack. The authors develop a structural hierarchy of paroids as well as duals and minors, and then briefly review their other paper about a generic paroid search algorithm.
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 94338
zbMATH Keywords: paroid
zbMATH Keywords: matroid
zbMATH Keywords: independent sets
zbMATH Keywords: bases
zbMATH Keywords: matching
zbMATH Keywords: travelling salesman
zbMATH Keywords: packing
zbMATH Keywords: knapsack
zbMATH Keywords: minors
zbMATH Keywords: search algorithm
reviewed by: András Recski
MaRDI profile type: Publication
cites work: The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n‐Bonds
cites work: Two algorithms for weighted matroid intersection
cites work: Heuristically guided algorithm for k-parity matroid problems
cites work: Q4198056
cites work: Worst case analysis of greedy type algorithms for independence systems
cites work: The Traveling-Salesman Problem and Minimum Spanning Trees
cites work: How easy is local search?
cites work: An Efficient Heuristic Procedure for Partitioning Graphs
cites work: Q4136942
cites work: Matroid intersection algorithms
cites work: Q4130999
cites work: An Effective Heuristic Algorithm for the Traveling-Salesman Problem
cites work: Q4040299
cites work: Paroid search: Generic local combinatorial optimization
cites work: Q4111952
Wikidata QID: Q127517389
description: scientific article; zbMATH DE number 94338