Combinatorial optimization with interaction costs: complexity and solvable cases
From MaRDI portal
Publication:2010918
DOI10.1016/j.disopt.2019.03.004zbMath1474.90381arXiv1707.02428OpenAlexW2923556723WikidataQ128009018 ScholiaQ128009018MaRDI QIDQ2010918
Ante Ćustić, Abraham P. Punnen, Stefan Lendl
Publication date: 28 November 2019
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1707.02428
computational complexityparametric optimizationlinearizationparameterized complexityfixed-rank matrixquadratic combinatorial optimization
Analysis of algorithms and problem complexity (68Q25) Quadratic programming (90C20) Sensitivity, stability, parametric optimization (90C31) Combinatorial optimization (90C27)
Related Items (7)
Two-stage robust optimization problems with two-stage uncertainty ⋮ Matroid bases with cardinality constraints on the intersection ⋮ The quadratic cycle cover problem: special cases and efficient bounds ⋮ On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty ⋮ Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications ⋮ The linearization problem of a binary quadratic problem and its applications ⋮ Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linearizable special cases of the QAP
- The bipartite quadratic assignment problem and extensions
- Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
- An FPTAS for optimizing a class of low-rank functions over a polytope
- An integer linear programming approach for bilinear integer programming
- On the tractability of some natural packing, covering and partitioning problems
- An FPTAS for minimizing the product of two non-negative linear cost functions
- Mixed-integer bilinear programming problems
- Admissible transformations and assignment problems
- Forests, frames, and games: Algorithms for matroid sums and applications
- A characterization of linear admissible transformations for the m- travelling salesmen problem
- The quadratic assignment problem. Theory and algorithms
- The disjoint shortest paths problem
- Cardinality constrained minimum cut problems: complexity and algorithms.
- A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
- The bilinear assignment problem: complexity and polynomially solvable special cases
- A characterization of linearizable instances of the quadratic minimum spanning tree problem
- Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis
- The constant objective value property for multidimensional assignment problems
- Markov chain methods for the bipartite Boolean quadratic programming problem
- Complexity of a 3-dimensional assignment problem
- 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
- An O(n4) Algorithm for the QAP Linearization Problem
- On the impact of combinatorial structure on congestion games
- Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems
- The complexity of the matching-cut problem for planar graphs and other graph classes
- A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
- AN ALGORITHM FOR SOLVING BILINEAR KNAPSACK PROBLEMS
- A Cutting-Plane Algorithm for the Quadratic Set-Covering Problem
- OUTER APPROXIMATION ALGORITHMS FOR LOWER RANK BILINEAR PROGRAMMING PROBLEMS
- Enumerating parametric global minimum cuts by random interleaving
- Improved smoothed analysis of multiobjective optimization
- Finding minimum congestion spanning trees
- Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
- A polynomial case of unconstrained zero-one quadratic optimization
This page was built for publication: Combinatorial optimization with interaction costs: complexity and solvable cases
