- Προσαρμοστική υπομονάδα βελτιστοποίησης υπό Matroid περιορισμούς (arXiv)
Συγγραφέας: Daniel Golovin, Andreas Krause
Περίληψη: Πολλά σημαντικά προβλήματα στη διακριτή βελτιστοποίηση απαιτούν μεγιστοποίηση μιας μονοτονικής υποαρθρωτής συνάρτησης που υπόκειται σε περιορισμούς μητροειδούς. Για αυτά τα προβλήματα, ένας απλός άπληστος αλγόριθμος είναι εγγυημένος για την απόκτηση σχεδόν βέλτιστων λύσεων. Σε αυτό το άρθρο, επεκτείνουμε αυτό το κλασικό αποτέλεσμα σε μια γενική κατηγορία προβλημάτων προσαρμοστικής βελτιστοποίησης υπό μερική παρατηρησιμότητα, όπου κάθε επιλογή μπορεί να εξαρτάται από παρατηρήσεις που προκύπτουν από προηγούμενες επιλογές. Συγκεκριμένα, αποδεικνύουμε ότι ένας φυσικός προσαρμοστικός άπληστος αλγόριθμος παρέχει μια προσέγγιση 1/(p+1) για το πρόβλημα της μεγιστοποίησης μιας προσαρμοστικής μονότονης υποαρθρωτής συνάρτησης που υπόκειται σε περιορισμούς p μητροειδούς και γενικότερα σε αυθαίρετα συστήματα p-ανεξαρτησίας. Εικονίζουμε τη χρησιμότητα του αποτελέσματός μας σε μια σύνθετη προσαρμοστική εφαρμογή δημιουργίας αντιστοιχιών
2. Αποσυνθέσεις ριζωμένων δέντρων με περιορισμούς Matroid και την απειροελάχιστη ακαμψία των πλαισίων με όρια (arXiv)
Συγγραφέας: Naoki Katoh, Shin-ichi Tanigawa
Περίληψη: Ως επέκταση ενός κλασικού προβλήματος κατανομής δέντρων, εξετάζουμε τις αποσυνθέσεις των γραφημάτων σε δέντρα με ασυνάρτητα άκρα (ρίζες-) με έναν επιπλέον περιορισμό μητροειδούς. Συγκεκριμένα, ας υποθέσουμε ότι μας δίνεται ένα γράφημα G=(V,E), ένα πολυσύνολο R={r1,…,rt} κορυφών στο V και ένα μητρώο M στο R. Αποδεικνύουμε μια απαραίτητη και επαρκή συνθήκη για να είναι το G αποσυντίθεται σε t υπογραφήματα ασυνεχούς ακμής G1=(V1,T1),…,Gt=(Vt,Tt) έτσι ώστε (i) για κάθε i, Gi είναι ένα δέντρο με ri∈Vi, και (ii) για κάθε v∈ V, το πολυσύνολο {ri∈R∣v∈Vi} είναι μια βάση του M. Εάν το M είναι ελεύθερο μητροειδές, αυτό είναι μια αποσύνθεση σε t που εκτείνονται σε ασυνεχή δέντρα. Έτσι, το αποτέλεσμά μας είναι μια σωστή επέκταση του θεωρήματος δενδροδιαμερισμού του Nash-Williams. Ένας τέτοιος περιορισμός μητροειδούς υποκινείται από τη συνδυαστική θεωρία ακαμψίας. Ως άμεση εφαρμογή του θεωρήματος αποσύνθεσής μας, παρουσιάζουμε χαρακτηρισμούς της απειροελάχιστης ακαμψίας πλαισίων με μη γενικό «όριο», που επεκτείνουν το κλασικό θεώρημα του Laman για το γενικό 2-ακαμψία των πλαισίων ράβδου και το θεώρημα του Tay για τη γενική d-ακαμψία του πλαίσια σώματος-μπαρ.
