Combinatorial optimization with interaction costs: complexity and solvable cases

DOI10.1016/J.DISOPT.2019.03.004zbMATH Open1474.90381arXiv1707.02428OpenAlexW2923556723WikidataQ128009018 ScholiaQ128009018MaRDI QIDQ2010918FDOQ2010918

Ante Ćustić, Abraham P. Punnen, Stefan Lendl

Publication date: 28 November 2019

Published in: Discrete Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1707.02428

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

zbMATH Keywords

computational complexitylinearizationparameterized complexityparametric optimizationfixed-rank matrixquadratic combinatorial optimization

Mathematics Subject Classification ID

Quadratic programming (90C20) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Sensitivity, stability, parametric optimization (90C31)

Cites Work

• Title not available (Why is that?)
• A characterization of linear admissible transformations for the m- travelling salesmen problem
• The quadratic assignment problem. Theory and algorithms
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• Linearizable special cases of the QAP
• An \(O(n^{4})\) algorithm for the QAP linearization problem
• Title not available (Why is that?)
• A Cutting-Plane Algorithm for the Quadratic Set-Covering Problem
• Mixed-integer bilinear programming problems
• Forests, frames, and games: Algorithms for matroid sums and applications
• On the impact of combinatorial structure on congestion games
• Complexity of a 3-dimensional assignment problem
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
• Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs
• The bipartite quadratic assignment problem and extensions
• Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
• Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
• Title not available (Why is that?)
• On the tractability of some natural packing, covering and partitioning problems
• A polynomial case of unconstrained zero-one quadratic optimization
• An FPTAS for optimizing a class of low-rank functions over a polytope
• An FPTAS for minimizing the product of two non-negative linear cost functions
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• The complexity of the matching-cut problem for planar graphs and other graph classes
• An integer linear programming approach for bilinear integer programming
• The disjoint shortest paths problem
• Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems
• Cardinality constrained minimum cut problems: complexity and algorithms.
• Admissible transformations and assignment problems
• Finding minimum congestion spanning trees
• AN ALGORITHM FOR SOLVING BILINEAR KNAPSACK PROBLEMS
• OUTER APPROXIMATION ALGORITHMS FOR LOWER RANK BILINEAR PROGRAMMING PROBLEMS
• Markov chain methods for the bipartite Boolean quadratic programming problem
• The bilinear assignment problem: complexity and polynomially solvable special cases
• Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis
• The constant objective value property for multidimensional assignment problems
• Enumerating parametric global minimum cuts by random interleaving
• Improved smoothed analysis of multiobjective optimization

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)