Search results for "Matroid"

Hits ?▲	Authors	Title	Venue	Year	Link
15	Vignesh Viswanathan, Yair Zick	Yankee Swap: A Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations.	AAMAS	2023	DBLP BibTeX RDF
15	Ilan Doron Arad, Ariel Kulik, Hadas Shachnai	Budgeted Matroid Maximization: a Parameterized Viewpoint.	IPEC	2023	DBLP DOI BibTeX RDF
15	Satoru Fujishige, Tamás Király, Kazuhisa Makino, Kenjiro Takazawa, Shin-ichi Tanigawa	Minimizing submodular functions on diamonds via generalized fractional matroid matchings.	J. Comb. Theory, Ser. B	2022	DBLP DOI BibTeX RDF
15	Zach Walsh	A New Matroid Lift Construction and an Application to Group-Labeled Graphs.	Electron. J. Comb.	2022	DBLP DOI BibTeX RDF
15	Eric Balkanski, Aviad Rubinstein, Yaron Singer	An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model.	Oper. Res.	2022	DBLP DOI BibTeX RDF
15	Peter Nelson, Shayla Redlin, Jorn G. van der Pol	Enumeration of extensions of the cycle matroid of a complete graph.	Adv. Appl. Math.	2022	DBLP DOI BibTeX RDF
15	Naoyuki Kamiyama	A Matroid Generalization of the Super-Stable Matching Problem.	SIAM J. Discret. Math.	2022	DBLP DOI BibTeX RDF
15	Guillermo Pineda-Villavicencio, Benjamin Schröter	Reconstructibility of Matroid Polytopes.	SIAM J. Discret. Math.	2022	DBLP DOI BibTeX RDF
15	Kazuki Matoya, Taihei Oki	Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems.	SIAM J. Discret. Math.	2022	DBLP DOI BibTeX RDF
15	Chien-Chung Huang, Naonori Kakimura, Simon Mauras, Yuichi Yoshida	Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model.	SIAM J. Discret. Math.	2022	DBLP DOI BibTeX RDF
15	Luiz F. O. Chamon, Alexandre Amice, Alejandro Ribeiro	Approximately Supermodular Scheduling Subject to Matroid Constraints.	IEEE Trans. Autom. Control.	2022	DBLP DOI BibTeX RDF
15	Walter D. Morris Jr.	On the Holt-Klee property for oriented matroid programming.	Eur. J. Comb.	2022	DBLP DOI BibTeX RDF
15	Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi 0001, Yu Yokoi	Approximation by lexicographically maximal solutions in matching and matroid intersection problems.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
15	Takuro Fukunaga, R. Ravi 0001, Oleksandr Rudenko, Ziye Tang	Approximation algorithm for the 2-stage stochastic matroid base problem.	Oper. Res. Lett.	2022	DBLP DOI BibTeX RDF
15	Manuel Aprile	Extended formulations for matroid polytopes through randomized protocols.	Oper. Res. Lett.	2022	DBLP DOI BibTeX RDF
15	Simon Park	Extension of Simple Algorithms to the Matroid Secretary Problem.	CoRR	2022	DBLP DOI BibTeX RDF
15	José F. De Jesús, Alexander K. Kelmans	Graphs with the same truncated cycle matroid.	CoRR	2022	DBLP DOI BibTeX RDF
15	Gergely Kál Csáji, Tamás Király, Yu Yokoi	Solving the Maximum Popular Matching Problem with Matroid Constraints.	CoRR	2022	DBLP DOI BibTeX RDF
15	Georg Anegg, Laura Vargas Koch, Rico Zenklusen	A Simple Combinatorial Algorithm for Robust Matroid Center.	CoRR	2022	DBLP DOI BibTeX RDF
15	Lan N. Nguyen, My T. Thai	Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint.	CoRR	2022	DBLP DOI BibTeX RDF
15	Gianira N. Alfarano, Eimear Byrne	The Cyclic Flats of a q-Matroid.	CoRR	2022	DBLP DOI BibTeX RDF
15	Tanvi Bajpai, Chandra Chekuri	Bicriteria Approximation Algorithms for Priority Matroid Median.	CoRR	2022	DBLP DOI BibTeX RDF
15	Ilan Doron Arad, Ariel Kulik, Hadas Shachnai	Bin Packing with Partition Matroid can be Approximated within $o(OPT)$ Bins.	CoRR	2022	DBLP DOI BibTeX RDF
15	Adam Brown, Aditi Laddha, Madhusudhan Pittu, Mohit Singh, Prasad Tetali	Determinant Maximization via Matroid Intersection Algorithms.	CoRR	2022	DBLP DOI BibTeX RDF
15	Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, Rico Zenklusen	Submodular Maximization Subject to Matroid Intersection on the Fly.	CoRR	2022	DBLP DOI BibTeX RDF
15	Taihei Oki, Tasuku Soma	Algebraic Algorithms for Fractional Linear Matroid Parity via Non-commutative Rank.	CoRR	2022	DBLP DOI BibTeX RDF
15	Ilan Doron Arad, Ariel Kulik, Hadas Shachnai	An EPTAS for Budgeted Matroid Independent Set.	CoRR	2022	DBLP DOI BibTeX RDF
15	Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg	An Improved Lower Bound for Matroid Intersection Prophet Inequalities.	CoRR	2022	DBLP DOI BibTeX RDF
15	Vignesh Viswanathan, Yair Zick	Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations.	CoRR	2022	DBLP DOI BibTeX RDF
15	Naoyuki Kamiyama	Strongly Stable Matchings under Matroid Constraints.	CoRR	2022	DBLP DOI BibTeX RDF
15	Vignesh Viswanathan, Yair Zick	A General Framework for Fair Allocation with Matroid Rank Valuations.	CoRR	2022	DBLP DOI BibTeX RDF
15	Ta-Wei Tu	Subquadratic Weighted Matroid Intersection Under Rank Oracles.	CoRR	2022	DBLP DOI BibTeX RDF
15	Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi 0001, Yu Yokoi	Matroid Intersection under Restricted Oracles.	CoRR	2022	DBLP DOI BibTeX RDF
15	Anja Fischer, Frank Fischer 0002, S. Thomas McCormick	Matroid optimization problems with monotone monomials in the objective.	Discret. Appl. Math.	2022	DBLP DOI BibTeX RDF
15	Lorenzo Traldi	A note on geometric duality in matroid theory and knot theory.	Discret. Appl. Math.	2022	DBLP DOI BibTeX RDF
15	Yuni Iwamasa, Kenjiro Takazawa	Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications.	Math. Program.	2022	DBLP DOI BibTeX RDF
15	Stefan Lendl, Britta Peis, Veerle Timmermans	Matroid bases with cardinality constraints on the intersection.	Math. Program.	2022	DBLP DOI BibTeX RDF
15	Manoel Lemos	A matroid operation that commutes with duality.	Discret. Math.	2022	DBLP DOI BibTeX RDF
15	James Dylan Douthitt, James G. Oxley	Bounding the number of bases of a matroid.	Discret. Math.	2022	DBLP DOI BibTeX RDF
15	Satoru Iwata 0001, Yusuke Kobayashi 0001	A Weighted Linear Matroid Parity Algorithm.	SIAM J. Comput.	2022	DBLP DOI BibTeX RDF
15	Georg Grasegger, Hakan Guler, Bill Jackson, Anthony Nixon	Flexible circuits in the d-dimensional rigidity matroid.	J. Graph Theory	2022	DBLP DOI BibTeX RDF
15	Ta-Wei Tu	Subquadratic Weighted Matroid Intersection Under Rank Oracles.	ISAAC	2022	DBLP DOI BibTeX RDF
15	Anupam Gupta 0001, Euiwoong Lee, Jason Li 0006, Marcin Mucha, Heather Newman, Sherry Sarkar	Matroid-Based TSP Rounding for Half-Integral Solutions.	IPCO	2022	DBLP DOI BibTeX RDF
15	Sumanta Ghosh, Rohit Gurjar, Roshan Raj	A Deterministic Parallel Reduction from Weighted Matroid Intersection Search to Decision.	SODA	2022	DBLP DOI BibTeX RDF
15	Shaddin Dughmi	Matroid Secretary Is Equivalent to Contention Resolution.	ITCS	2022	DBLP DOI BibTeX RDF
15	Zhicheng Liu, Jing Jin, Donglei Du, Xiaoyan Zhang 0001	Two-Stage Submodular Maximization Under Knapsack and Matroid Constraints.	TAMC	2022	DBLP DOI BibTeX RDF
15	Yunjing Sun, Yuezhu Liu, Min Li	Maximization of k-Submodular Function with a Matroid Constraint.	TAMC	2022	DBLP DOI BibTeX RDF
15	Yijing Wang, Dongmei Zhang 0002, Yapu Zhang, Zhenning Zhang	Weakly k-submodular Maximization Under Matroid Constraint.	TAMC	2022	DBLP DOI BibTeX RDF
15	Yanjun Jiang, Yijing Wang, Ruiqi Yang, Weina Ye	Maximizing Approximately Non-k-Submodular Monotone Set Function with Matroid Constraint.	TAMC	2022	DBLP DOI BibTeX RDF
15	Adam Brown, Aditi Laddha, Madhusudhan Pittu, Mohit Singh, Prasad Tetali	Determinant Maximization via Matroid Intersection Algorithms.	FOCS	2022	DBLP DOI BibTeX RDF
15	Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, Rico Zenklusen	Submodular Maximization Subject to Matroid Intersection on the Fly.	ESA	2022	DBLP DOI BibTeX RDF
15	Moran Feldman, Paul Liu 0001, Ashkan Norouzi-Fard, Ola Svensson, Rico Zenklusen	Streaming Submodular Maximization Under Matroid Constraints.	ICALP	2022	DBLP DOI BibTeX RDF
15	Joakim Blikstad	Sublinear-Round Parallel Matroid Intersection.	ICALP	2022	DBLP DOI BibTeX RDF
15	Siddharth Barman, Paritosh Verma	Truthful and Fair Mechanisms for Matroid-Rank Valuations.	AAAI	2022	DBLP DOI BibTeX RDF
15	Benwei Wu, Kai Han 0003	Fast Algorithm for Big Data Summarization with Knapsack and Partition Matroid Constraints.	INISTA	2022	DBLP DOI BibTeX RDF
15	Chien-Chung Huang, François Sellier	Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms.	SWAT	2022	DBLP DOI BibTeX RDF
15	Theophile Thiery, Justin Ward	Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression.	COLT	2022	DBLP BibTeX RDF
15	Arturo I. Merino, Torsten Mütze, Aaron Williams	All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges.	FUN	2022	DBLP DOI BibTeX RDF
15	Hong Chang, Zhicheng Liu, Donglei Du, Xiaoyan Zhang 0001	Two-Stage BP Maximization Under p-matroid Constraint.	COCOON	2022	DBLP DOI BibTeX RDF
15	Lan N. Nguyen, My T. Thai	Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint.	IJCAI	2022	DBLP DOI BibTeX RDF
15	Kemin Yu, Min Li 0028, Yang Zhou 0018, Qian Liu	Guarantees for Maximization of k-Submodular Functions with a Knapsack and a Matroid Constraint.	AAIM	2022	DBLP DOI BibTeX RDF
15	Alice L. L. Gao, Matthew H. Y. Xie	The inverse Kazhdan-Lusztig polynomial of a matroid.	J. Comb. Theory, Ser. B	2021	DBLP DOI BibTeX RDF
15	Florian Hörsch, Zoltán Szigeti	Packing of Mixed Hyperarborescences with Flexible Roots via Matroid Intersection.	Electron. J. Comb.	2021	DBLP DOI BibTeX RDF
15	Darij Grinberg, Fedor Petrov 0001	A Greedoid and a Matroid Inspired by Bhargava's $p$-Orderings.	Electron. J. Comb.	2021	DBLP DOI BibTeX RDF
15	Preston Cranford, Anton Dochtermann, Evan Haithcock, Joshua Marsh, Suho Oh, Anna Truman	Biconed Graphs, Weighted Forests, and $h$-Vectors of Matroid Complexes.	Electron. J. Comb.	2021	DBLP DOI BibTeX RDF
15	Yijing Wang, Donglei Du, Yanjun Jiang, Xianzhao Zhang	Non-Submodular Maximization with Matroid and Knapsack Constraints.	Asia Pac. J. Oper. Res.	2021	DBLP DOI BibTeX RDF
15	Huimin Xiao, Meiqi Wang	Research on hesitant fuzzy matroid based on satisfaction function.	J. Intell. Fuzzy Syst.	2021	DBLP DOI BibTeX RDF
15	Deyin Wu, Yonghong Li	The induced basis axioms for a closed G-V fuzzy matroid.	J. Intell. Fuzzy Syst.	2021	DBLP DOI BibTeX RDF
15	Wenyu Ouyang, Mohammad S. Obaidat, Xuxun Liu 0001, Xiaoting Long, Wenzheng Xu, Tang Liu 0001	Importance-Different Charging Scheduling Based on Matroid Theory for Wireless Rechargeable Sensor Networks.	IEEE Trans. Wirel. Commun.	2021	DBLP DOI BibTeX RDF
15	Jongmin Lee, Gwang Kim, Ilkyeong Moon	A mobile multi-agent sensing problem with submodular functions under a partition matroid.	Comput. Oper. Res.	2021	DBLP DOI BibTeX RDF
15	Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi 0001, Yair Zick	Finding Fair and Efficient Allocations for Matroid Rank Valuations.	ACM Trans. Economics and Comput.	2021	DBLP DOI BibTeX RDF
15	Ragnar Freij-Hollanti, Olga Kuznetsova	Information hiding using matroid theory.	Adv. Appl. Math.	2021	DBLP DOI BibTeX RDF
15	Kristóf Bérczi, Naonori Kakimura, Yusuke Kobayashi 0001	Market Pricing for Matroid Rank Valuations.	SIAM J. Discret. Math.	2021	DBLP DOI BibTeX RDF
15	Qiqiang Hou, Andrew Clark 0001	Robust Maximization of Correlated Submodular Functions Under Cardinality and Matroid Constraints.	IEEE Trans. Autom. Control.	2021	DBLP DOI BibTeX RDF
15	Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita	Optimal Matroid Partitioning Problems.	Algorithmica	2021	DBLP DOI BibTeX RDF
15	Federico Castillo, José Alejandro Samper	Finiteness theorems for matroid complexes with prescribed topology.	Eur. J. Comb.	2021	DBLP DOI BibTeX RDF
15	Xin Sun, Dachuan Xu, Longkun Guo, Min Li 0028	Deterministic approximation algorithm for submodular maximization subject to a matroid constraint.	Theor. Comput. Sci.	2021	DBLP DOI BibTeX RDF
15	Naoyuki Kamiyama	Envy-free matchings with one-sided preferences and matroid constraints.	Oper. Res. Lett.	2021	DBLP DOI BibTeX RDF
15	Sungjin Im, Benjamin Moseley, Kirk Pruhs	The matroid intersection cover problem.	Oper. Res. Lett.	2021	DBLP DOI BibTeX RDF
15	Orcun Karaca, Daniel Tihanyi, Maryam Kamgarpour	Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid.	Oper. Res. Lett.	2021	DBLP DOI BibTeX RDF
15	Sungjin Im, Benjamin Moseley, Rudy Zhou	The Matroid Cup Game.	Oper. Res. Lett.	2021	DBLP DOI BibTeX RDF
15	Sumanta Ghosh, Rohit Gurjar	Matroid Intersection: A pseudo-deterministic parallel reduction from search to weighted-decision.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
15	Jessica Sidman, Will Traves, Ashley Wheeler	Geometric equations for matroid varieties.	J. Comb. Theory, Ser. A	2021	DBLP DOI BibTeX RDF
15	Ngoc Mai Tran	The Finite Matroid-Based Valuation Conjecture is False.	SIAM J. Appl. Algebra Geom.	2021	DBLP DOI BibTeX RDF
15	Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, Rico Zenklusen	Streaming Submodular Maximization with Matroid and Matching Constraints.	CoRR	2021	DBLP BibTeX RDF
15	Deeparnab Chakrabarty, Yu Chen 0039, Sanjeev Khanna	A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection.	CoRR	2021	DBLP BibTeX RDF
15	Chien-Chung Huang, Theophile Thiery, Justin Ward	Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints.	CoRR	2021	DBLP BibTeX RDF
15	Joakim Blikstad	Breaking O(nr) for Matroid Intersection.	CoRR	2021	DBLP BibTeX RDF
15	Goran Malic, Ileana Streinu	Combinatorial Resultants in the Algebraic Rigidity Matroid.	CoRR	2021	DBLP BibTeX RDF
15	Shaddin Dughmi	Matroid Secretary is Equivalent to Contention Resolution.	CoRR	2021	DBLP BibTeX RDF
15	Marilena Leichter, Benjamin Moseley, Kirk Pruhs	An Efficient Reduction of a Gammoid to a Partition Matroid.	CoRR	2021	DBLP BibTeX RDF
15	Manuel Aprile	Extended formulations for matroid polytopes through randomized protocols.	CoRR	2021	DBLP BibTeX RDF
15	Anupam Gupta 0001, Euiwoong Lee, Jason Li 0006, Marcin Mucha, Heather Newman, Sherry Sarkar	Matroid-Based TSP Rounding for Half-Integral Solutions.	CoRR	2021	DBLP BibTeX RDF
15	Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai	Breaking the Quadratic Barrier for Matroid Intersection.	CoRR	2021	DBLP BibTeX RDF
15	Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi 0001, Yu Yokoi	Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems.	CoRR	2021	DBLP BibTeX RDF
15	Siddharth Barman, Paritosh Verma	Truthful and Fair Mechanisms for Matroid-Rank Valuations.	CoRR	2021	DBLP BibTeX RDF
15	Maryam Bahrani, Hedyeh Beyhaghi, Sahil Singla 0001, S. Matthew Weinberg	Formal Barriers to Simple Algorithms for the Matroid Secretary Problem.	CoRR	2021	DBLP BibTeX RDF
15	Paritosh Garg, Linus Jordan, Ola Svensson	Semi-Streaming Algorithms for Submodular Matroid Intersection.	CoRR	2021	DBLP BibTeX RDF
15	Orestis Papadigenopoulos, Constantine Caramanis	Recurrent Submodular Welfare and Matroid Blocking Bandits.	CoRR	2021	DBLP BibTeX RDF
15	Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan	Matroid Partition Property and the Secretary Problem.	CoRR	2021	DBLP BibTeX RDF