Robust Independence Systems

DOI10.1007/978-3-642-22006-7_31zbMath1333.05304OpenAlexW2276586909MaRDI QIDQ5892606

Naonori Kakimura, Kazuhisa Makino

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_31

zbMATH Keywords

robustnessexchangeabilitymatroidsindependence systems

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Extremal set theory (05D05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Computing knapsack solutions with cardinality robustness ⋮ On the intersection of independence systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs, networks and algorithms.
• How to make a digraph strongly connected
• Geometric algorithms and combinatorial optimization.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and applications.
• Greedy Local Improvement and Weighted Set Packing Approximation
• Robust subgraphs for trees and paths
• Note on Independence Functions
• The greedy travelling salesman's problem
• An Analysis of the Greedy Heuristic for Independence Systems
• The Online Median Problem
• Robust Matchings
• A General Approach for Incremental Approximation and Hierarchical Clustering
• Greedy in Approximation Algorithms
• Matroids and the greedy algorithm
• Robust Independence Systems
• Robust Matchings and Matroid Intersections

This page was built for publication: Robust Independence Systems