We study integer-valued matrices with bounded determinants. Such matrices appear in the theory of integer programs (IPs) with bounded determinants. For example, an IP can be solved in strongly polynomial time if the constraint matrix is bimodular: that is,...

A series-parallel matrix is a binary matrix that can be obtained from an empty matrix by successively adjoining rows or columns that are copies of an existing row/column or have at most one one-entry. Equivalently, series-parallel matrices are ...

We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a “unified” algorithm whose performance matches previous results developed in various ...

An Exponentially Faster Algorithm for Submodular Maximization Under a Matroid Constraint

This paper studies the problem of submodular maximization under a matroid constraint. It is known since the 1970s that the greedy algorithm obtains a constant-factor ...

In this paper, we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box ...

Halin proved that every minimally $k$-connected graph has a vertex of degree $k$. More generally, does every minimally vertically $k$-connected matroid have a $k$-element cocircuit? Results of Murty and Wong give an affirmative answer when $k \le 3$. We ...

The class of quasi-graphic matroids, recently introduced by Geelen, Gerards, and Whittle, is minor closed and contains both the class of lifted-graphic matroids and the class of frame matroids, each of which generalizes the class of graphic matroids. In ...

A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with $n$ variables and a constraint matrix with dual tree-depth $d$ and largest entry $\Delta$ are solvable in time $g(d,\Delta){...

A simple binary matroid is called $I_4$-free if none of its rank-4 flats are independent sets. These objects can be equivalently defined as the sets $E$ of points in $\mbox{PG}(n-1,2)$ for which $E \cap F$ is not a basis of $F$ for any four-dimensional ...

In the ordinal matroid secretary problem (MSP), candidates do not reveal numerical weights, but the decision maker can still discern if a candidate is better than another. An algorithm α is probability-competitive if every element from the optimum appears ...

In cost-sharing games with delays, a set of agents jointly uses a subset of resources. Each resource has a fixed cost that has to be shared by the players, and each agent has a nonshareable player-specific delay for each resource. A separable cost-sharing ...

In the list coloring problem for two matroids, we are given matroids $M_1=(S,{\mathcal{I}}_1)$ and $M_2=(S,{\mathcal{I}}_2)$ on the same ground set $S$, and the goal is to determine the smallest number $k$ such that, given arbitrary lists $L_s$ of $k$ ...

We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call ...

Diversity maximization is a fundamental problem in web search and data mining. For a given dataset S of n elements, the problem requires to determine a subset of S containing k≪n “representatives” which maximize some diversity function expressed in ...

We continue the development of matroid-based techniques for kernelization, initiated by the present authors [47]. We significantly extend the usefulness of matroid theory in kernelization by showing applications of a result on representative sets due to ...

We investigate the emergence of swarm intelligence using task allocation in large robot swarms. First, we compare task decomposition graphs of different levels of richness and measure the emergent intelligence arising from self-organized task allocation ...

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors $v_1,\ldots,v_m \in \mathbb{R}^d$ and a constraint family $\mathcal{B} \subseteq 2^{[m]}$, find a set $S \in \mathcal{B}$ that maximizes the ...

Given a dissimilarity map $\delta$ on a finite set $X$, the set of ultrametrics (equidistant tree metrics) which are $l^\infty$-nearest to $\delta$ is a tropical polytope. We give an internal description of this tropical polytope which we use to derive a ...

We prove that for every proper minor-closed class $\mathcal{M}$ of $\mathbb{F}_p$-representable matroids, there exists an $O(1)$-competitive algorithm for the matroid secretary problem on $\mathcal{M}$. This result relies on the extremely powerful ...

We consider parallel, or low adaptivity, algorithms for submodular function maximization. This line of work was recently initiated by Balkanski and Singer and has already led to several interesting results on the cardinality constraint and explicit ...

In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box ...