Structure preserving reductions among convex optimization problems

Cites work

Algorithms for Scheduling Independent Tasks
An analysis of approximations for maximizing submodular set functions—I
Approximation algorithms for combinatorial problems
Heuristic evaluation techniques for bin packing approximation algorithms
scientific article; zbMATH DE number 3551892 (Why is no real title available?)
scientific article; zbMATH DE number 3560738 (Why is no real title available?)
scientific article; zbMATH DE number 3566162 (Why is no real title available?)
scientific article; zbMATH DE number 3566230 (Why is no real title available?)
scientific article; zbMATH DE number 3569828 (Why is no real title available?)
scientific article; zbMATH DE number 3571502 (Why is no real title available?)
P-Complete Approximation Problems
Structure preserving reductions among convex optimization problems
The Complexity of Near-Optimal Graph Coloring

Cited in

(77)

Red-blue covering problems and the consecutive ones property
On the minimum hitting set of bundles problem
The node-deletion problem for hereditary properties is NP-complete
Structure preserving reductions among convex optimization problems
Combinatorial problems over power sets
On the complexity of approximating the independent set problem
Optimization, approximation, and complexity classes
A bounded approximation for the minimum cost 2-sat problem
Differential approximation algorithms for some combinatorial optimization problems
The maximum clique problem
On an approximation measure founded on the links between optimization and polynomial approximation theory
Minimal approximate hitting sets and rule templates
The maximum \(f\)-depth spanning tree problem
The complexity of egalitarian mechanisms for linear programming games
A logarithmic approximation for polymatroid congestion games
The generalized vertex cover problem and some variations
Approximation algorithms for some vehicle routing problems
On the differential approximation of MIN SET COVER
Scheduling time-constrained multicast messages in circuit-switched tree networks.
Differential approximation results for the traveling salesman problem with distances 1 and 2
Differential approximation for optimal satisfiability and related problems
The complexity of approximating a nonlinear program
Max NP-completeness made easy
Bridging gap between standard and differential polynomial approximation: The case of bin-packing
Finding disjoint paths in networks with star shared risk link groups
Least and most colored bases
Reductions, completeness and the hardness of approximability
On the computational hardness based on linear fpt-reductions
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
Online and approximate network construction from bounded connectivity constraints
Constrained hitting set problem with intervals
Differential approximation algorithm of FSMVRP
Differential approximation results for the traveling salesman and related problems
Optimal cost sharing for capacitated facility location games
An Improved Approximation Bound for Spanning Star Forest and Color Saving
Energy consumption minimization in ad hoc wireless and multi-interface networks
On the Minimum Hitting Set of Bundles Problem
The minimum maximal k-partial-matching problem
An improved algorithm for the red-blue hitting set problem with the consecutive ones property
On the approximability and hardness of minimum topic connected overlay and its special instances
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
A survey on the structure of approximation classes
Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
Inapproximability results for graph convexity parameters
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
On the complexity of approximating the independent set problem (extended abstract)
Tight localizations of feedback sets
Cost minimization in wireless networks with a bounded and unbounded number of interfaces
On the convergence rate of grid search for polynomial optimization over the simplex
COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
On the parameterized complexity of compact set packing
On parallel versus sequential approximation
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
On the parameterized complexity of compact set packing
Approximate solution of NP optimization problems
Local search, reducibility and approximability of NP-optimization problems
Finding diverse strings and longest common subsequences in a graph
The complexity of Boolean failure identification
Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
Detection and localization of hidden radioactive sources with spatial statistical method
Completeness in approximation classes
Minimizing the stretch when scheduling flows of divisible requests
Feedback arc set in bipartite tournaments is NP-complete
Analyzing the complexity of finding good neighborhood functions for local search algorithms
An efficient fixed-parameter algorithm for 3-hitting set
Exploiting hidden structure in selecting dimensions that distinguish vectors
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
The complexity of optimizing over a simplex, hypercube or sphere: a short survey
Faster fixed-parameter tractable algorithms for matching and packing problems
Approximability of clausal constraints
New differential approximation algorithm for \(k\)-customer vehicle routing problem

This page was built for publication: Structure preserving reductions among convex optimization problems

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