Σε αυτή τη διατριβή μελετάμε τα όρια της ισχύος του γραμμικού προγραμματισμού
όσον αφορά την επίλυση προβλημάτων της συνδυαστικής βελτιστοποίησης. Δίνουμε
αποτελέσματα σχετικά με την προσεγγισιμότητα μέσω γραμμικού προγραμματισμού
facility location προβλημάτων με χωρητικότητες όπως το capacitated facility
location (Cfl) και το lower bounded facility location (Lbfl). Δίνουμε αρνητικά
αποτελέσματα στα μοντέλα των ιεραρχιών και των extended formulations και επίσης
μελετούμε μία ανεξάρτητη από τα προηγούμενα οικογένεια χαλαρώσεων.
Στις ιεραρχίες, δείχνουμε ότι οι χαλαρώσεις που προκύπτουν από το κλασσικό
γραμμικό πρόγραμμα για το Cfl σε Ω(n) επίπεδα της semidefinite Lovasz-Schrijver
ιεραρχίας για mixed προγράμματα και σε Ω(n) επίπεδα της Sherali-Adams
ιεραρχίας, έχουν integrality gap Ω(n). Αποδεικνύουμε ότι το κλασσικό γραμμικό
πρόγραμμα για το Cfl έχει μη φραγμένο integrality gap ακόμα και μετά την
εισαγωγή των submodular inequalities του [1].
Προτείνουμε μία μεθοδολογία για το φράξιμο του μεγέθους των extended
formulations και ως εφαρμογή δείχνουμε εκθετικό φράγμα στο μέγεθος για το Cfl
ενός ειδικού τύπου extended formulations. Τέλος εισάγουμε και μελετούμε την
οικογένεια των proper relaxations τα οποία γενικεύουν το star relaxation και
μοντελοποιεί γενικά configuration-style LPs. Χαρακτηρίζουμε τη συμπεριφορά των
proper relaxations για το Cfl και Lbfl μέσω ενός φαινομένου κατωφλίου.
(EL)
In this thesis we study the limitation of linear programming as far as
combinatorial optimization problems are concerned. We give results regarding
the linear programming approximability of the capacitated versions of the
metric facility location problem such as the capacitated facility location
(Cfl) and lower bounded facility location (Lbfl). We give impossibility results
in the hierarchy and in the extended formulations models and we consider
another, independent family of relaxations.
Regarding our hierarchy related results, we show that the relaxations obtained
from the natural LP at Ω (n) levels of the semidefinite Lovasz-Schriver
hierarchy for mixed programs, and at Ω(n) levels of the Sherali-Adams
hierarchy, have an integrality gap of Ω(n). We prove that the standard Cfl
relaxation enriched with the submodular inequalities of [1] has also an Ω(n)
gap.
We propose a framework for proving lower bounds on the size of extended
formulations and, as an application, we show for Cfl an exponential lower bound
on the size of a restricted type of extended. We finally introduce the family
of proper relaxations which generalizes the classic star relaxation and
captures general configuration-style LPs. We characterize the behavior of
proper relaxations for Cfl and Lbfl through a sharp threshold phenomenon.
(EN)
/aggregator-openarchives/portal/institutions/uoa
