Color constrained combinatorial optimization problems
Let \(E\) be a finite set and let \(c: E\to Z_ +\) be a non-negative integer cost function. Given subsets \(E_ 1,\dots,E_ K\subseteq E\) (colors) and \(\ell_ 1,\dots,\ell_ K\in Z\), find \(\min\sum_{e\in S}c(e)\) satisfying \(S\in{\mathcal S}\), \(| S\cap E_ k|=\ell_ k\), \(| S\cap\overline{E}_ k|=R-\ell_ k\), \(k=1,\dots,K\), where \(S\subseteq E\), \(\mathcal S\) is the set of feasible solutions, \(\overline {E}_ k=E\backslash E_ k\) and \(R=\max\{| S|:\;S\subseteq E,\;S\in{\mathcal S}\}\). The authors show how to reduce this problem to a parametric problem with paiwise disjoint colors and derive as special cases polynomial algorithms for one instance of a 3-matroid intersection problem and colored bipartite matching problems.
- A multiply constrained matroid optimization problem
- Matroid optimization with generalized constraints
- Efficient algorithms for a family of matroid intersection problems
- Optimization problems with color-induced budget constraints
- Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems
- A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
- A multiply constrained matroid optimization problem
- A strongly polynomial minimum cost circulation algorithm
- Efficient algorithms for a family of matroid intersection problems
- scientific article; zbMATH DE number 3580570 (Why is no real title available?)
- k-Best constrained bases of a matroid
- Matroid optimization with the interleaving of two ordered sets
- Network flows. Theory, algorithms, and applications.
- Two algorithms for weighted matroid intersection
- Budgeted colored matching problems
- A column-generation approach to the multiple knapsack problem with color constraints
- The color-balanced spanning tree problem.
- Algorithms and Computation
- Biobjective optimization problems on matroids with binary costs
- On generalized balanced optimization problems
- Almost optimal solutions for bin coloring problems
This page was built for publication: Color constrained combinatorial optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1178732)
