๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On approximate algorithms for combinatorial linear maximization problems

โœ Scribed by C. Croitoru

Publisher
Springer
Year
1980
Tongue
English
Weight
232 KB
Volume
24
Category
Article
ISSN
0340-9422

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Combinatorial Approximation Algorithms f
Combinatorial Approximation Algorithms for Generalized Flow Problems
โœ Jeffrey D Oldham ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 226 KB

Generalized network flow problems generalize normal network flow problems by specifying a flow multiplier ยต v w for each arc v w . For every unit of flow entering the arc, ยต v w units of flow exit. We present a strongly polynomial algorithm for a single-source generalized shortest paths problem, usi

Approximation Algorithms for Maximizatio
Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
โœ Uriel Feige; Michael Langberg ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 261 KB

Given a graph G = V E , a weight function w E โ†’ R + , and a parameter k, we consider the problem of finding a subset U โŠ† V of size k that maximizes: Max-Vertex Cover k the weight of edges incident with vertices in U, Max-Dense Subgraph k the weight of edges in the subgraph induced by U, Max-Cut k th

Parallel Output-Sensitive Algorithms for
Parallel Output-Sensitive Algorithms for Combinatorial and Linear Algebra Problems
โœ John H. Reif ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 160 KB

This paper gives output-sensitive parallel algorithms whose performance depends on the output size and are significantly more efficient tan previous algorithms for problems with sufficiently small output size. Inputs are n\_n matrices over a fixed ground field. Let P(n) and M(n) be the PRAM processo