Structure preserving reductions among convex optimization problems
From MaRDI portal
Publication:1143173
DOI10.1016/0022-0000(80)90046-XzbMath0441.68049OpenAlexW1975218943WikidataQ59650039 ScholiaQ59650039MaRDI QIDQ1143173
Alessandro D'Atri, Marco Protasi, Giorgio Ausiello
Publication date: 1980
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(80)90046-x
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Related Items (74)
Differential approximation algorithm of FSMVRP ⋮ Minimizing the stretch when scheduling flows of divisible requests ⋮ Differential approximation results for the traveling salesman and related problems ⋮ Optimal cost sharing for capacitated facility location games ⋮ Feedback arc set in bipartite tournaments is NP-complete ⋮ On an approximation measure founded on the links between optimization and polynomial approximation theory ⋮ Least and most colored bases ⋮ An Improved Approximation Bound for Spanning Star Forest and Color Saving ⋮ Analyzing the complexity of finding good neighborhood functions for local search algorithms ⋮ The complexity of approximating a nonlinear program ⋮ Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa ⋮ The complexity of egalitarian mechanisms for linear programming games ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ The minimum maximal k-partial-matching problem ⋮ Tight Localizations of Feedback Sets ⋮ The node-deletion problem for hereditary properties is NP-complete ⋮ An improved algorithm for the red-blue hitting set problem with the consecutive ones property ⋮ On the parameterized complexity of compact set packing ⋮ On parallel versus sequential approximation ⋮ Structure preserving reductions among convex optimization problems ⋮ Combinatorial problems over power sets ⋮ Exploiting hidden structure in selecting dimensions that distinguish vectors ⋮ On the approximability and hardness of minimum topic connected overlay and its special instances ⋮ On the Minimum Hitting Set of Bundles Problem ⋮ Online and Approximate Network Construction from Bounded Connectivity Constraints ⋮ On the difficulty of designing good classifiers ⋮ Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms ⋮ Online and approximate network construction from bounded connectivity constraints ⋮ Constrained hitting set problem with intervals ⋮ A logarithmic approximation for polymatroid congestion games ⋮ Max NP-completeness made easy ⋮ A survey on the structure of approximation classes ⋮ Bridging gap between standard and differential polynomial approximation: The case of bin-packing ⋮ A better differential approximation ratio for symmetric TSP ⋮ On the complexity of optimization over the standard simplex ⋮ Approximation results for the weighted \(P_4\) partition problem ⋮ On the complexity of approximating the independent set problem ⋮ The complexity of optimizing over a simplex, hypercube or sphere: a short survey ⋮ Inapproximability results for graph convexity parameters ⋮ Optimization, approximation, and complexity classes ⋮ Approximate solution of NP optimization problems ⋮ Local search, reducibility and approximability of NP-optimization problems ⋮ COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES ⋮ A bounded approximation for the minimum cost 2-sat problem ⋮ On the convergence rate of grid search for polynomial optimization over the simplex ⋮ Faster fixed-parameter tractable algorithms for matching and packing problems ⋮ The generalized vertex cover problem and some variations ⋮ Approximability of clausal constraints ⋮ Approximation algorithms for some vehicle routing problems ⋮ Reductions, completeness and the hardness of approximability ⋮ On the differential approximation of MIN SET COVER ⋮ Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s) ⋮ New differential approximation algorithm for \(k\)-customer vehicle routing problem ⋮ On the computational hardness based on linear fpt-reductions ⋮ Cost minimization in wireless networks with a bounded and unbounded number of interfaces ⋮ A PTAS for the minimization of polynomials of fixed degree over the simplex ⋮ On influence, stable behavior, and the most influential individuals in networks: a game-theoretic approach ⋮ Red-blue covering problems and the consecutive ones property ⋮ Differential approximation of NP-hard problems with equal size feasible solutions ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ On the complexity of approximating the independent set problem ⋮ Differential approximation algorithms for some combinatorial optimization problems ⋮ Detection and localization of hidden radioactive sources with spatial statistical method ⋮ Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks ⋮ On the minimum hitting set of bundles problem ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Scheduling time-constrained multicast messages in circuit-switched tree networks. ⋮ Minimal approximate hitting sets and rule templates ⋮ Finding disjoint paths in networks with star shared risk link groups ⋮ The maximum \(f\)-depth spanning tree problem ⋮ The maximum clique problem ⋮ Completeness in approximation classes ⋮ Differential approximation results for the traveling salesman problem with distances 1 and 2 ⋮ Differential approximation for optimal satisfiability and related problems
Cites Work
- Heuristic evaluation techniques for bin packing approximation algorithms
- Structure preserving reductions among convex optimization problems
- Approximation algorithms for combinatorial problems
- The Complexity of Near-Optimal Graph Coloring
- Algorithms for Scheduling Independent Tasks
- P-Complete Approximation Problems
- An analysis of approximations for maximizing submodular set functions—I
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Structure preserving reductions among convex optimization problems
