{"id":{"repo_id":"mcmaster","oai_identifier":"oai:macsphere.mcmaster.ca:11375/12544"},"canonical_url":"https://search.ndltd.org/etd/mcmaster/oai:macsphere.mcmaster.ca:11375/12544","repository":{"repo_id":"mcmaster","name":"McMaster University","base_url":"https://macsphere.mcmaster.ca/server/oai/request"},"display":{"title":"ON ALGORITHMS FOR THE COLOURFUL LINEAR PROGRAMMING FEASIBILITY PROBLEM","abstract":"<p>Given colourful sets S_1,..., S_{d+1} of points in R^d and a point p in R^d, the colourful linear programming problem is to express p as a convex combination of points x_1,...,x_{d+1} with x_i in S_i for each i. This problem was presented by Bárány and Onn in 1997, it is still not known if a polynomial-time algorithm for the problem exists. The monochrome version of this problem, expressing p as a convex combination of points in a set S, is a traditional linear programming feasibility problem. The colourful Carathéodory Theorem, due to Bárány in 1982, provides a sufficient condition for the existence of a colourful set of points containing p in its convex hull. Bárány's result was generalized by Holmsen et al. in 2008 and by Arocha et al. in 2009 before being recently further generalized by Meunier and Deza. We study algorithms for colourful linear programming under the conditions of Bárány and their generalizations. In particular, we implement the Meunier-Deza algorithm and enhance previously used random case generators. Computational benchmarking and a performance analysis including a comparison between the two algorithms of Bárány and Onn and the one of Meunier and Deza, and random picking are presented.</p>","abstract_html":"&lt;p&gt;Given colourful sets S_1,..., S_{d+1} of points in R^d and a point p in R^d, the colourful linear programming problem is to express p as a convex combination of points x_1,...,x_{d+1} with x_i in S_i for each i. This problem was presented by Bárány and Onn in 1997, it is still not known if a polynomial-time algorithm for the problem exists. The monochrome version of this problem, expressing p as a convex combination of points in a set S, is a traditional linear programming feasibility problem. The colourful Carathéodory Theorem, due to Bárány in 1982, provides a sufficient condition for the existence of a colourful set of points containing p in its convex hull. Bárány&#x27;s result was generalized by Holmsen et al. in 2008 and by Arocha et al. in 2009 before being recently further generalized by Meunier and Deza. We study algorithms for colourful linear programming under the conditions of Bárány and their generalizations. In particular, we implement the Meunier-Deza algorithm and enhance previously used random case generators. Computational benchmarking and a performance analysis including a comparison between the two algorithms of Bárány and Onn and the one of Meunier and Deza, and random picking are presented.&lt;/p&gt;","abstract_has_math":false,"creators":["Rong, Guohong"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Computing and Software","school":null,"contributors":[],"advisors":["Deza, Antoine","Franek, Franya"],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-10","date_published":"2012-10","updated_at":"2026-11-18T19:37:40Z","subjects":["Colourful","Caratheodory","Banany-Onn","Meunier-Deza","Convex Hull","Simplex","Computer Sciences","Theory and Algorithms"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.71548/19208"],"render_values":[{"text":"https://doi.org/10.71548/19208","href":"https://doi.org/10.71548/19208","code":true}]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["opendissertations/7421","8478","3343129"],"render_values":[{"text":"opendissertations/7421","href":null,"code":true},{"text":"8478","href":null,"code":true},{"text":"3343129","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11375/12544","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"http://hdl.handle.net/11375/12544","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://macsphere.mcmaster.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amacsphere.mcmaster.ca%3A11375%2F12544","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Deza, Antoine","Franek, Franya"]},{"key":"dc:contributor.department","label":"Department","values":["Computing and Software"]},{"key":"dc:creator","label":"Author","values":["Rong, Guohong"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-06-18T16:59:59Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-06-18T16:59:59Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2012-09-22"]},{"key":"dc:date.issued","label":"Date","values":["2012-10"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Colourful","Caratheodory","Banany-Onn","Meunier-Deza","Convex Hull","Simplex","Computer Sciences","Theory and Algorithms"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["opendissertations/7421","8478","3343129"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11375/12544","https://doi.org/10.71548/19208"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["<p>Given colourful sets S_1,..., S_{d+1} of points in R^d and a point p in R^d, the colourful linear programming problem is to express p as a convex combination of points x_1,...,x_{d+1} with x_i in S_i for each i. This problem was presented by Bárány and Onn in 1997, it is still not known if a polynomial-time algorithm for the problem exists. The monochrome version of this problem, expressing p as a convex combination of points in a set S, is a traditional linear programming feasibility problem. The colourful Carathéodory Theorem, due to Bárány in 1982, provides a sufficient condition for the existence of a colourful set of points containing p in its convex hull. Bárány's result was generalized by Holmsen et al. in 2008 and by Arocha et al. in 2009 before being recently further generalized by Meunier and Deza. We study algorithms for colourful linear programming under the conditions of Bárány and their generalizations. In particular, we implement the Meunier-Deza algorithm and enhance previously used random case generators. Computational benchmarking and a performance analysis including a comparison between the two algorithms of Bárány and Onn and the one of Meunier and Deza, and random picking are presented.</p>"]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science (MSc)"]},{"key":"dc:title","label":"Title","values":["ON ALGORITHMS FOR THE COLOURFUL LINEAR PROGRAMMING FEASIBILITY PROBLEM"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"dc:contributor.advisor":["Deza, Antoine","Franek, Franya"],"dc:contributor.department":["Computing and Software"],"dc:creator":["Rong, Guohong"],"dc:date.accessioned":["2014-06-18T16:59:59Z"],"dc:date.available":["2014-06-18T16:59:59Z"],"dc:date.created":["2012-09-22"],"dc:date.issued":["2012-10"],"dc:description.abstract":["<p>Given colourful sets S_1,..., S_{d+1} of points in R^d and a point p in R^d, the colourful linear programming problem is to express p as a convex combination of points x_1,...,x_{d+1} with x_i in S_i for each i. This problem was presented by Bárány and Onn in 1997, it is still not known if a polynomial-time algorithm for the problem exists. The monochrome version of this problem, expressing p as a convex combination of points in a set S, is a traditional linear programming feasibility problem. The colourful Carathéodory Theorem, due to Bárány in 1982, provides a sufficient condition for the existence of a colourful set of points containing p in its convex hull. Bárány's result was generalized by Holmsen et al. in 2008 and by Arocha et al. in 2009 before being recently further generalized by Meunier and Deza. We study algorithms for colourful linear programming under the conditions of Bárány and their generalizations. In particular, we implement the Meunier-Deza algorithm and enhance previously used random case generators. Computational benchmarking and a performance analysis including a comparison between the two algorithms of Bárány and Onn and the one of Meunier and Deza, and random picking are presented.</p>"],"dc:description.degree":["Master of Science (MSc)"],"dc:identifier.other":["opendissertations/7421","8478","3343129"],"dc:identifier.uri":["http://hdl.handle.net/11375/12544","https://doi.org/10.71548/19208"],"dc:subject":["Colourful","Caratheodory","Banany-Onn","Meunier-Deza","Convex Hull","Simplex","Computer Sciences","Theory and Algorithms"],"dc:title":["ON ALGORITHMS FOR THE COLOURFUL LINEAR PROGRAMMING FEASIBILITY PROBLEM"],"dc:type":["thesis"],"others:access_status":["open.access"]},"updated_at":"2026-11-18T19:37:40Z"}