Structure preserving reductions among convex optimization problems

From MaRDI portal
Revision as of 04:08, 31 January 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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




Related Items (74)

Differential approximation algorithm of FSMVRPMinimizing the stretch when scheduling flows of divisible requestsDifferential approximation results for the traveling salesman and related problemsOptimal cost sharing for capacitated facility location gamesFeedback arc set in bipartite tournaments is NP-completeOn an approximation measure founded on the links between optimization and polynomial approximation theoryLeast and most colored basesAn Improved Approximation Bound for Spanning Star Forest and Color SavingAnalyzing the complexity of finding good neighborhood functions for local search algorithmsThe complexity of approximating a nonlinear programApproximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationaThe complexity of egalitarian mechanisms for linear programming gamesAn efficient fixed-parameter algorithm for 3-hitting setThe minimum maximal k-partial-matching problemTight Localizations of Feedback SetsThe node-deletion problem for hereditary properties is NP-completeAn improved algorithm for the red-blue hitting set problem with the consecutive ones propertyOn the parameterized complexity of compact set packingOn parallel versus sequential approximationStructure preserving reductions among convex optimization problemsCombinatorial problems over power setsExploiting hidden structure in selecting dimensions that distinguish vectorsOn the approximability and hardness of minimum topic connected overlay and its special instancesOn the Minimum Hitting Set of Bundles ProblemOnline and Approximate Network Construction from Bounded Connectivity ConstraintsOn the difficulty of designing good classifiersConstrained hitting set problem with intervals: hardness, FPT and approximation algorithmsOnline and approximate network construction from bounded connectivity constraintsConstrained hitting set problem with intervalsA logarithmic approximation for polymatroid congestion gamesMax NP-completeness made easyA survey on the structure of approximation classesBridging gap between standard and differential polynomial approximation: The case of bin-packingA better differential approximation ratio for symmetric TSPOn the complexity of optimization over the standard simplexApproximation results for the weighted \(P_4\) partition problemOn the complexity of approximating the independent set problemThe complexity of optimizing over a simplex, hypercube or sphere: a short surveyInapproximability results for graph convexity parametersOptimization, approximation, and complexity classesApproximate solution of NP optimization problemsLocal search, reducibility and approximability of NP-optimization problemsCOMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSESA bounded approximation for the minimum cost 2-sat problemOn the convergence rate of grid search for polynomial optimization over the simplexFaster fixed-parameter tractable algorithms for matching and packing problemsThe generalized vertex cover problem and some variationsApproximability of clausal constraintsApproximation algorithms for some vehicle routing problemsReductions, completeness and the hardness of approximabilityOn the differential approximation of MIN SET COVERApproximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)New differential approximation algorithm for \(k\)-customer vehicle routing problemOn the computational hardness based on linear fpt-reductionsCost minimization in wireless networks with a bounded and unbounded number of interfacesA PTAS for the minimization of polynomials of fixed degree over the simplexOn influence, stable behavior, and the most influential individuals in networks: a game-theoretic approachRed-blue covering problems and the consecutive ones propertyDifferential approximation of NP-hard problems with equal size feasible solutionsAutour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instancesOn the complexity of approximating the independent set problemDifferential approximation algorithms for some combinatorial optimization problemsDetection and localization of hidden radioactive sources with spatial statistical methodEnergy Consumption Minimization in Ad Hoc Wireless and Multi-interface NetworksOn the minimum hitting set of bundles problemA Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest PathsScheduling time-constrained multicast messages in circuit-switched tree networks.Minimal approximate hitting sets and rule templatesFinding disjoint paths in networks with star shared risk link groupsThe maximum \(f\)-depth spanning tree problemThe maximum clique problemCompleteness in approximation classesDifferential approximation results for the traveling salesman problem with distances 1 and 2Differential approximation for optimal satisfiability and related problems




Cites Work




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