BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
A filter oracle for a clutter consists of a finite set V along with an oracle which, given any set X⊆V, decides in unit time whether or not X contains a member of the clutter. Let A2n be an algorithm that, given any clutter C over 2n elements via a filter oracle, decides whether or not C is ideal. We prove that in the worst case, A2n must make at least 2n calls to the filter oracle. Our proof uses the theory of cuboids.
A vector is \emph{dyadic} if each of its entries is a dyadic rational number, i.e. of the form 2ka for some integers a,k with k≥0. A linear system Ax≤b with integral data is \emph{totally dual dyadic} if whenever min{b⊤y:A⊤y=w,y≥0} for w integral, has an optimal solution, it has a dyadic optimal solution. In this paper, we study total dual dyadicness, and give a co-NP characterization of it in terms of \emph{dyadic generating sets for cones and subspaces}, the former being the dyadic analogue of \emph{Hilbert bases}, and the latter a polynomial-time recognizable relaxation of the former. Along the way, we see some surprising turn of events when compared to total dual integrality, primarily led by the \emph{density} of the dyadic rationals. Our study ultimately leads to a better understanding of total dual integrality and polyhedral integrality. We see examples from dyadic matrices, T-joins, cycles, and perfect matchings of a graph.
The mixing set with a knapsack constraint arises as a substructure in mixed-integer programming reformulations of chance-constrained programs with stochastic right-hand-sides over a finite discrete distribution. Recently, Luedtke et al. (2010) and Küçükyavuz (2012) studied valid inequalities for such sets. However, most of their results were focused on the equal probabilities case (equivalently when the knapsack reduces to a cardinality constraint), with only minor results in the general case. In this paper, we focus on the general probabilities case (general knapsack constraint). We characterize the valid inequalities that do not come from the knapsack polytope and use this characterization to generalize the inequalities previously derived for the equal probabilities case. We also show that one can separate over a large class of inequalities in polynomial time.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.