Combinatorial optimization with interaction costs: complexity and solvable cases
From MaRDI portal
Publication:2010918
Abstract: We introduce and study the combinatorial optimization problem with interaction costs (COPIC). COPIC is the problem of finding two combinatorial structures, one from each of two given families, such that the sum of their independent linear costs and the interaction costs between elements of the two selected structures is minimized. COPIC generalizes the quadratic assignment problem and many other well studied combinatorial optimization problems, and hence covers many real world applications. We show how various topics from different areas in the literature can be formulated as special cases of COPIC. The main contributions of this paper are results on the computational complexity and approximability of COPIC for different families of combinatorial structures (e.g. spanning trees, paths, matroids), and special structures of the interaction costs. More specifically, we analyze the complexity if the interaction cost matrix is parameterized by its rank and if it is a diagonal matrix. Also, we determine the structure of the intersection cost matrix, such that COPIC is equivalent to independently solving linear optimization problems for the two given families of combinatorial structures.
Recommendations
- scientific article; zbMATH DE number 6832021
- Efficiently solvable special cases of hard combinatorial optimization problems
- Publication:3484639
- Computational combinatorial optimization. Optimal of probably near-optimal solutions
- Towards Copeland optimization in combinatorial problems
- scientific article; zbMATH DE number 780787
- On Approximate Solutions for Combinatorial Optimization Problems
- scientific article; zbMATH DE number 1102774
- scientific article; zbMATH DE number 863497
- Cost distributions in large combinatorial optimisation problems
Cites work
- scientific article; zbMATH DE number 35513 (Why is no real title available?)
- scientific article; zbMATH DE number 1894374 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 5047784 (Why is no real title available?)
- A Cutting-Plane Algorithm for the Quadratic Set-Covering Problem
- A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
- A characterization of linear admissible transformations for the m- travelling salesmen problem
- A characterization of linearizable instances of the quadratic minimum spanning tree problem
- A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
- A polynomial case of unconstrained zero-one quadratic optimization
- AN ALGORITHM FOR SOLVING BILINEAR KNAPSACK PROBLEMS
- Admissible transformations and assignment problems
- Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
- An FPTAS for minimizing the product of two non-negative linear cost functions
- An FPTAS for optimizing a class of low-rank functions over a polytope
- An \(O(n^{4})\) algorithm for the QAP linearization problem
- An integer linear programming approach for bilinear integer programming
- Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis
- Cardinality constrained minimum cut problems: complexity and algorithms.
- Complexity of a 3-dimensional assignment problem
- Connections in combinatorial optimization
- Enumerating parametric global minimum cuts by random interleaving
- Finding minimum congestion spanning trees
- Forests, frames, and games: Algorithms for matroid sums and applications
- Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs
- Linearizable special cases of the QAP
- Markov chain methods for the bipartite Boolean quadratic programming problem
- Mixed-integer bilinear programming problems
- OUTER APPROXIMATION ALGORITHMS FOR LOWER RANK BILINEAR PROGRAMMING PROBLEMS
- On the impact of combinatorial structure on congestion games
- On the tractability of some natural packing, covering and partitioning problems
- Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
- Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems
- The bilinear assignment problem: complexity and polynomially solvable special cases
- The bipartite quadratic assignment problem and extensions
- The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
- The complexity of the matching-cut problem for planar graphs and other graph classes
- The constant objective value property for multidimensional assignment problems
- The disjoint shortest paths problem
- The quadratic assignment problem. Theory and algorithms
Cited in
(9)- The linearization problem of a binary quadratic problem and its applications
- Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications
- Matroid bases with cardinality constraints on the intersection
- Treatment of combinatorial optimization problems using selection equations with cost terms. II: NP-hard three-dimensional assignment problems
- Treatment of combinatorial optimization problems using selection equations with cost terms. I: Two-dimensional assignment problems
- On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty
- The quadratic cycle cover problem: special cases and efficient bounds
- Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems
- Two-stage robust optimization problems with two-stage uncertainty
This page was built for publication: Combinatorial optimization with interaction costs: complexity and solvable cases
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010918)
