Report icon

Report

A Randomized Algorithm for the MaxFS Problem

Abstract:

We consider the NP-hard combinatorial optimization problem of finding a feasible subsystem of maximum cardinality among a given set of linear inequalities. In some new and challenging applications in digital broadcasting and in the modelling of protein folding potentials one faces very large MaxFS instances with up to millions of inequalities in thousands of variables. We introduce and analyze a randomized algorithm that is surprisingly successful at solving MaxFS instances that arise in thes...

Expand abstract

Actions


Access Document


Files:

Authors


Edoardo Amaldi More by this author
Pietro Belotti More by this author
Raphael Hauser More by this author
Publication date:
2005-01-05
URN:
uuid:42e809d4-1ab5-4122-82eb-960735c2e238
Local pid:
oai:eprints.maths.ox.ac.uk:1150

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP