Using the pseudo-dimension to analyze approximation algorithms for integer programming

DOI10.1007/3-540-44634-6_4MaRDI QIDQ4778540zbMATH OpenFDO

Authors Philip M. Long

Publication date 18 November 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2125/21250026

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• scientific article; zbMATH DE number 1263202
• Solving packing integer programs via randomized rounding with alterations
• Approximation algorithms for covering/packing integer programs

Cited in

(9)

• Near-linear algorithms for geometric hitting sets and set covers
• An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
• scientific article; zbMATH DE number 1305498 (Why is no real title available?)
• Approximation algorithms for maximum independent set of pseudo-disks
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Sparse Approximation via Generating Point Sets
• Superlinear Integrality Gaps for the Minimum Majority Problem
• scientific article; zbMATH DE number 6460215 (Why is no real title available?)
• A PAC Approach to Application-Specific Algorithm Selection

This page was built for publication: Using the pseudo-dimension to analyze approximation algorithms for integer programming

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