Hyperbolic set covering problems with competing ground-set elements

DOI10.1007/s10107-010-0431-1zbMath1254.90119OpenAlexW2028120800MaRDI QIDQ715069

Edoardo Amaldi, Federico Malucelli, Sandro Bosio

Publication date: 15 October 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-010-0431-1

zbMATH Keywords

complexityLagrangean relaxationset coveringwireless networksoverlapsapproximabilityhyperbolic objective function

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Integer programming (90C10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Fractional 0-1 programming: applications and algorithms ⋮ A simple technique to improve linearized reformulations of fractional (hyperbolic) 0-1 programming problems ⋮ Compact representations of all members of an independence system ⋮ Fractional 0-1 programs: links between mixed-integer linear and conic quadratic formulations

Uses Software

• OR-Library
• Object Bundle Package

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a new class of nonlinear set covering problems arising in wireless network design
• A fast approximation algorithm for the multicovering problem
• Optimal packing and covering in the plane are NP-complete
• Hyperbolic 0-1 programming and query optimization in information retrieval
• Boolean query optimization and the 0-1 hyperbolic sum problem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• On complexity of unconstrained hyperbolic 0--1 programming problems
• Global optimization of 0-1 hyperbolic programs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A threshold of ln n for approximating set cover
• Approximation schemes for covering and packing problems in image processing and VLSI
• A Greedy Heuristic for the Set-Covering Problem
• A Cutting-Plane Algorithm for the Quadratic Set-Covering Problem
• Set Partitioning: A survey
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Hyperbolic set covering problems with competing ground-set elements