Approximability of sparse integer programs (Q634673)

From MaRDI portal

Revision as of 23:10, 9 December 2024 by Import241208061232 (talk | contribs) (Normalize DOI.)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Approximability of sparse integer programs	scientific article

Statements

scholarly article

0 references

Approximability of sparse integer programs (English)

0 references

Juan-Miguel Gracia

0 references

0 references

publication date

16 August 2011

0 references

full work available at URL

https://arxiv.org/abs/0904.0859

0 references

zbMATH Keywords

integer programming

0 references

approximation algorithms

0 references

LP rounding

0 references

MaRDI profile type

MaRDI publication profile

0 references

On k-Column Sparse Packing Programs

0 references

A linear-time approximation algorithm for the weighted vertex cover problem

0 references

Efficient algorithms for integer programs with two variables per constraint.

0 references

0 references

0 references

On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP

0 references

Multicommodity demand flow in a tree and packing integer programs

0 references

Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs

0 references

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

0 references

Approximation and Online Algorithms

0 references

Primal-dual approximation algorithms for integral flow and multicut in trees

0 references

Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions

0 references

Geometric algorithms and combinatorial optimization

0 references

A fast approximation algorithm for the multicovering problem

0 references

Some optimal inapproximability results

0 references

On the complexity of approximating \(k\)-set packing

0 references

Approximation Algorithms for the Set Covering and Vertex Cover Problems

0 references

Monotonizing linear programs with up to two nonzeroes per column

0 references

Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

0 references

On the Size of Systems of Sets Every <i>t</i> of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems

0 references

Submodular Function Minimization under Covering Constraints

0 references

0 references

Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion

0 references

Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

0 references

Approximation algorithms for covering/packing integer programs

0 references

Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees

0 references

Distributed and parallel algorithms for weighted vertex cover and other covering problems

0 references

Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality

0 references

Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost

0 references

Integer Programming with a Fixed Number of Variables

0 references

0 references

Approximability of Sparse Integer Programs

0 references

The Demand-Matching Problem

0 references

Improved Approximation Guarantees for Packing and Covering Integer Programs

0 references

An Extension of the Lovász Local Lemma, and its Applications to Integer Programming

0 references

Non-approximability results for optimization problems on bounded degree instances

0 references

An analysis of the greedy algorithm for the submodular set covering problem

0 references

Identifiers

zbMATH Open document ID

0 references

Mathematics Subject Classification ID

0 references

0 references

zbMATH DE Number

0 references

0 references

0 references

10.1007/S00453-010-9431-Z

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:634673

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q634673&oldid=38424492"