Robust Randomized Matchings

References

• Bertsimas D, Nasrabadi E, Orlin JB (2016) On the power of randomization in network interdiction. Oper. Res. Lett. 44(1):114–120.Crossref, Google Scholar
• Calvillo G (1980) The concavity and intersection properties for integral polyhedra. Ann. Discrete Math. 8:221–228.Crossref, Google Scholar
• Disser Y, Klimm M, Megow N, Stiller S (2014) Packing a knapsack of unknown capacity. Portier N, Wilke T, eds. Proc. 31st Internat. Sympos. Theoret. Aspects Comput. Sci., STACS ’14, Leibniz Internat. Proc. Informatics, Vol. 25 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Saarbrücken, Germany), 276–287.Google Scholar
• Dütting P, Roughgarden T, Talgam-Cohen I (2014) Modularity and greed in double auctions. Proc. 15th ACM Conf. Econom. Comput., EC ’14, (ACM, New York), 241–258.Google Scholar
• Fujita R, Kobayashi Y, Makino K (2013) Robust matchings and matroid intersections. SIAM J. Discrete Math. 27(3):1234–1256.Crossref, Google Scholar
• Fukunaga T, Halldórsson MM, Nagamochi H (2008) Robust cost colorings. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’08 (SIAM, Philadelphia), 1204–1212.Google Scholar
• Hassin R, Rubinstein S (2002) Robust matchings. SIAM J. Discrete Math. 15(4):530–537.Crossref, Google Scholar
• Hassin R, Segev D (2006) Robust subgraphs for trees and paths. ACM Trans. Algorithms 2(2):263–281.Crossref, Google Scholar
• Hausmann D, Korte B, Jenkyns TA (1980) Worst case analysis of greedy type algorithms for independence systems. Math. Programming Study 12:120–131.Crossref, Google Scholar
• Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301):13–30.Crossref, Google Scholar
• Kakimura N, Makino K (2013) Robust independence systems. SIAM J. Discrete Math. 27(3):1257–1273.Crossref, Google Scholar
• Kakimura N, Makino K, Seimi K (2012) Computing knapsack solutions with cardinality robustness. Japan J. Indust. Appl. Math. 29(3):469–483.Crossref, Google Scholar
• Kobayashi Y, Takazawa K (2017) Randomized strategies for cardinality robustness in the knapsack problem. Theoret. Comput. Sci. 699:53–62.Crossref, Google Scholar
• Mastin A, Jaillet P, Chin S (2015) Randomized minmax regret for combinatorial optimization under uncertainty. Algorithms and Computation, Lecture Notes in Computer Science, Vol. 9472 (Springer, New York), 491–501.Crossref, Google Scholar
• Matuschke J, Skutella M, Soto JA (2015) Robust randomized matchings. Indyk P, ed. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’15 (SIAM, Philadelphia), 1904–1915.Google Scholar
• Megow N, Mestre J (2013) Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints. Proc. 4th Conf. Innovations in Theoret. Comput. Sci., ITCS ’13 (ACM, New York), 495–504.Google Scholar
• Mestre J (2006) Greedy in approximation algorithms. Algorithms–ESA 2006, Lecture Notes in Computer Science, Vol. 4168 (Springer, New York), 528–539.Crossref, Google Scholar
• Schrijver A (2003) Combinatorial Optimization—Polyhedra and Efficiency (Springer, New York).Google Scholar
• Soto JA (2014) A simple PTAS for weighted matroid matching on strongly base orderable matroids. Discrete Appl. Math. 164:406–412.Crossref, Google Scholar
• Ward J (2012) Oblivious and non-oblivious local search for combinatorial optimization. PhD thesis, University of Toronto.Google Scholar