Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming

DOI10.1007/S10107-018-1242-ZMaRDI QIDQ1749453zbMATH OpenOpenAlexFDO

Authors Yishui Wang, Zaixin Lu, Zhao Zhang, Du Ding-Zhu, Chenchen Wu, Panos M. Pardalos, Dachuan Xu

Publication date 16 May 2018

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-018-1242-z

zbMATH Keywords

convex functionconnectivityDC programmingfault-tolerant

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1859295
• Degree-constrained \(k\)-minimum spanning tree problem
• The degree-constrained and diameter-constrained minimum spanning tree problem and its algorithm
• Approximation of the degree-constrained minimum spanning hierarchies
• A branch and cut method for the degree-constrained minimum spanning tree problem

Cites work

• scientific article; zbMATH DE number 5485528 (Why is no real title available?)
• scientific article; zbMATH DE number 4041643 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 710624 (Why is no real title available?)
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A framework of discrete DC programming by discrete convex analysis
• An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints
• An efficient combined DCA and B\&B using DC/SDP relaxation for globally solving binary quadratic programs
• Approximation algorithms for scheduling unrelated parallel machines
• Continuous relaxation for discrete DC programming
• Convex analysis approach to d. c. programming: Theory, algorithms and applications
• Depth-First Search and Linear Graph Algorithms
• Discrete Convex Analysis
• Exact penalty and error bounds in DC programming
• Generating Minimal k-Vertex Connected Spanning Subgraphs
• Graph theory
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Increasing the rooted connectivity of a digraph by one
• On local search in d.c. optimization problems
• Properties of two DC algorithms in quadratic programming
• Solving a class of linearly constrained indefinite quadratic problems by DC algorithms
• Steiner tree approximation via iterative randomized rounding
• The DC (Difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems
• The design of approximation algorithms

Cited in

(4)

• Parametric monotone function maximization with matroid constraints
• Set function optimization
• Fast algorithms for maximizing monotone nonsubmodular functions
• Fast algorithms for maximizing monotone nonsubmodular functions

This page was built for publication: Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1749453)