Approximation algorithms for multi-parameter graph optimization problems
type: Item
instance of: scholarly article
title: Approximation algorithms for multi-parameter graph optimization problems
zbMATH Open document ID: 1041.90059
DOI: 10.1016/S0166-218X(01)00269-4
published in: Discrete Applied Mathematics
publication date: 2002-06-24T00:00:00Z
review text: A multi-parameter graph optimization problem (MPGO) is defined by a graph \(G=(V,E)\), a \(k\)-dimensional non-negative weight \(w(e)\) for each edge \(e\) in \(E\), and a cost function assigning to each subset \(S \subseteq E\) of the edge set a cost \(c(S):=c(w(S)):=c(\sum w(e))\). The goal of MPGO is to find a minimum cost subset of \(E\) satisfying a given property \(P\). In the case, where \(c(S)=\max_{1\leq i\leq k}w_i(S)\), MPGO is very similar to constrained graph optimization problems which have attracted a lot of attention due to their large potential in applications. The authors prove that MPGO is weakly NP-hard for a large class of properties \(P\) and cost functions \(c\), including paths, spanning trees, cuts, joins, etc. The authors develop a simple approximation algorithm for the general problem and prove performance guarantee results.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 90C08
zbMATH DE Number: 1758391
zbMATH Keywords: weakly NP-hard
zbMATH Keywords: approximation algorithm
author: Ivan V. Basov
author: Alek Vainshtein
reviewed by: Horst W. Hamacher
MaRDI profile type: MaRDI publication profile
cites work: Q5284651
cites work: Q4371290
cites work: Q4198056
cites work: Approximation Schemes for the Restricted Shortest Path Problem
cites work: Maximizing Classes of Two-Parameter Objectives Over Matroids
cites work: Algorithms for finding paths with multiple constraints
cites work: The shortest route problem with constraints
cites work: Q4401014
cites work: The network inhibition problem
cites work: The constrained minimum spanning tree problem
cites work: Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
Wikidata QID: Q126717791
Wikidata QID: Q126717792
Wikidata QID: Q126717793
Wikidata QID: Q126717794
Recommended article: An approximation algorithm for a general class of multi-parametric optimization problems
Recommended article: Generalized \(k\)-multiway cut problems
Recommended article: An improved approximation algorithm of MULTIWAY CUT.
Recommended article: Simple greedy algorithms for fundamental multidimensional graph problems
Recommended article: Q3150852
description: scientific article; zbMATH DE number 1758391