Exact and approximation algorithms for weighted matroid intersection

No abstract is available for this paper.

• Publication year

  2016

• Venue

  Mathematical programming

• Publication date

  2016-01-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s10107-018-1260-x
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• New Algorithms for Maximum Weight Matching and a Decomposition Theorem

  2017cited by this paper
• A Fast Approximation for Maximum Weight Matroid Intersection

  2016cited by this paper
• A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization

  2015cited by this paper
• Scaling Algorithms for Weighted Matching in General Graphs

  2014cited by this paper
• Linear-Time Approximation for Maximum Weight Matching

  2014cited by this paper
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs , and its Multicommodity Generalizations

  2013cited by this paper
• Capacitated Rank-Maximal Matchings

  2013cited by this paper
• A new approach to computing maximum flows using electrical flows

  2013cited by this paper
• Predictive model selection criteria for Bayesian lasso

  2013cited by this paper
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations

  2013cited by this paper
• Nearly Maximum Flows in Nearly Linear Time

  2013cited by this paper
• A simple reduction from maximum weight matching to maximum cardinality matching

  2012cited by this paper
• Multiplying matrices faster than coppersmith-winograd

  2012cited by this paper
• Fast matrix rank algorithms and applications

  2012influential reference
• On the maximal number of exceptional values of Gauss maps for various classes of surfaces

  2012cited by this paper
• Efficient algorithms for maximum weight matchings in general graphs with small edge weights

  2012cited by this paper
• Nonlinear regression modeling and detecting change points via the relevance vector machine

  2011cited by this paper
• Algebraic algorithms for linear matroid parity problems

  2011cited by this paper
• Network Coding and Matroid Theory

  2011cited by this paper
• An explicit formula for the discrete power function associated with circle patterns of Schramm type

  2011cited by this paper
• Explicit solutions to the semi-discrete modified KdV equation and motion of discrete plane curves

  2011cited by this paper
• A simple PTAS for weighted matroid matching on strongly base orderable matroids

  2011cited by this paper
• Asymptotic behaviors of solutions to evolution equations in the presence of translation and scaling invariance

  2011cited by this paper
• Asymptotic tail dependence of the normal copula

  2011cited by this paper
• Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs

  2010cited by this paper
• Variable selection via the grouped weighted lasso for factor analysis models

  2010cited by this paper
• Matroid matching: the power of local search

  2010cited by this paper
• On the Number of the Pairing-friendly Curves

  2010cited by this paper
• Finite element computation for scattering problems of micro-hologram using DtN map

  2010cited by this paper
• HYPER-PARAMETER SELECTION IN BAYESIAN STRUCTURAL EQUATION MODELS

  2010cited by this paper
• Algebraic Algorithms for Matching and Matroid Problems

  2009influential reference
• A Practical Implementation of a Symbolic-Numeric Cylindrical Algebraic Decomposition for Quantifier Elimination

  2009cited by this paper
• Maximum weight bipartite matching in matrix multiplication time

  2009cited by this paper
• A matroid intersection algorithm

  2008cited by this paper
• Reducing rank-maximal to maximum weight matching

  2007cited by this paper
• An algebraic algorithm for weighted linear matroid intersection

  2007cited by this paper
• Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems

  2006cited by this paper
• Rank-maximal matchings

  2004cited by this paper
• High-order lifting and integrality certification

  2003cited by this paper
• Combinatorial optimization. Polyhedra and efficiency.

  2003cited by this paper
• Approximate distance oracles

  2001cited by this paper
• Submodular Functions, Matroids, and Certain Polyhedra

  2001cited by this paper
• Kazuo Murota 著, Matrices and Matroids for Systems Analysis, Springer-Verlag, 483頁, 2000年, 定価15,870円(189マルク)

  2000cited by this paper
• Matrices and Matroids for Systems Analysis

  2000cited by this paper
• Matrices and matroids for systems analysis

  2000cited by this paper
• A Decomposition Theorem for Maximum Weight Bipartite Matchings

  2000cited by this paper
• Combinatorial optimization

  1997cited by this paper
• Efficient Theoretic and Practical Algorithms for Linear Matroid Intersection Problems

  1996cited by this paper
• AN EFFICIENT COST SCALING ALGORITHM FOR THE INDEPENDENT ASSIGNMENT PROBLEM

  1995cited by this paper
• A dual approximation approach to weighted matroid intersection

  1995cited by this paper
• Combinatorial Optimization

  1992cited by this paper
• Submodular functions and optimization

  1991cited by this paper
• Faster scaling algorithms for general graph matching problems

  1991cited by this paper
• Matroid theory and its applications in electric network theory and in statics

  1989cited by this paper
• Faster Scaling Algorithms for Network Problems

  1989cited by this paper
• Efficient algorithms for independent assignment on graphic and linear matroids

  1989influential reference
• Matrix multiplication via arithmetic progressions

  1987cited by this paper
• Combinatorial canonical form of layered mixed matrices and its application to block-triangularization of systems of linear/nonlinear equations

  1987cited by this paper
• Improved Bounds for Matroid Partition and Intersection Algorithms

  1986influential reference
• Two algorithms for weighted matroid intersection

  1986cited by this paper
• Efficient Algorithms for Graphic Intersection and Parity (Extended Abstract)

  1985cited by this paper
• Efficient Algorithms for Graphic Matroid Intersection and Parity (Extended Abstract)

  1985cited by this paper
• Complexity of Matroid Property Algorithms

  1982cited by this paper
• Applications of Matroid Theory

  1982cited by this paper
• A Weighted Matroid Intersection Algorithm

  1981influential reference
• An Analysis of the Greedy Heuristic for Independence Systems

  1978cited by this paper
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"

  1976cited by this paper
• Matroid intersection algorithms

  1975cited by this paper
• Matroids and the greedy algorithm

  1971cited by this paper
• MATCHING THEORY FOR COMBINATORIAL GEOMETRIES

  1970cited by this paper
• Matroid Intersection

  year unknowncited by this paper
• Kyushu University Institutional Repository ULTRADISCRETIZATION OF A SOLVABLE TWO-DIMENSIONAL CHAOTIC MAP ASSOCIATED WITH THE HESSE CUBIC CURVE

  year unknowncited by this paper

• A Weighted-to-Unweighted Reduction for Matroid Intersection

  2026cites this paper
• Popular Arborescences and Their Matroid Generalization

  2025cites this paper
• Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries

  2024cites this paper
• Faster Matroid Partition Algorithms

  2023cites this paper
• Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions

  2022cites this paper
• Subquadratic Weighted Matroid Intersection Under Rank Oracles

  2022cites this paper
• Matroid Intersection under Restricted Oracles

  2022cites this paper
• Optimal class assignment problem: a case study at Gunma University

  2021cites this paper
• Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems

  2021cites this paper
• On the Complexity of Recovering Incidence Matrices

  2020cites this paper
• Faster Matroid Intersection

  2019influential citation
• On a weighted linear matroid intersection algorithm by Deg-Det computation

  2019cites this paper
• Packing of arborescences with matroid constraints via matroid intersection

  2019cites this paper
• Matroid Intersection : Beating Half for Random Arrival ⋆

  2018cites this paper
• Finite-thickness effect on speed of a counter-rotating vortex pair at high Reynolds numbers

  2018cites this paper
• Making Bipartite Graphs DM-irreducible Kristóf Bérczi

  2018cites this paper
• The b-branching problem in digraphs

  2018cites this paper
• Combinatorial Optimization Under Uncertainty ( Probing and Stopping-Time Algorithms )

  2017cites this paper
• Making Bipartite Graphs DM-irreducible

  2016cites this paper
• A Fast Approximation for Maximum Weight Matroid Intersection

  2016cites this paper