research
∙
07/17/2023
Hypergraph Splitting-off and Covering Skew-Supermodular Functions in Strongly Polynomial Time
We consider hypergraph network design problems where the goal is to cons...
share
research
∙
02/26/2023
Newton-type algorithms for inverse optimization II: weighted span objective
In inverse optimization problems, the goal is to modify the costs in an ...
research
∙
02/26/2023
Newton-type algorithms for inverse optimization I: weighted bottleneck Hamming distance and ℓ_∞-norm objectives
In minimum-cost inverse optimization problems, we are given a feasible s...
research
∙
02/02/2023
Partitioning into common independent sets via relaxing strongly base orderability
The problem of covering the ground set of two matroids by a minimum numb...
research
∙
01/17/2023
Matroid Horn functions
Hypergraph Horn functions were introduced as a subclass of Horn function...
research
∙
01/13/2023
Hypergraph Horn functions
Horn functions form a subclass of Boolean functions possessing interesti...
research
∙
01/04/2023
Envy-free dynamic pricing schemes
A combinatorial market consists of a set of indivisible items and a set ...
research
∙
11/23/2022
Weighted exchange distance of basis pairs
Two pairs of disjoint bases 𝐏_1=(R_1,B_1) and 𝐏_2=(R_2,B_2) of a matroid...
research
∙
09/29/2022
Matroid Intersection under Restricted Oracles
Matroid intersection is one of the most powerful frameworks of matroid t...
research
∙
09/05/2022
Resolving Infeasibility of Linear Systems: A Parameterized Approach
Deciding feasibility of large systems of linear equations and inequaliti...
research
∙
06/23/2022
On the complexity of packing rainbow spanning trees
One of the most important questions in matroid optimization is to find d...
research
∙
06/20/2022
On approximating the rank of graph divisors
Baker and Norine initiated the study of graph divisors as a graph-theore...
research
∙
04/28/2022
Manipulating the outcome of stable matching and roommates problems
The stable marriage and stable roommates problems have been extensively ...
research
∙
03/03/2022
Exchange distance of basis pairs in split matroids
The basis exchange axiom has been a driving force in the development of ...
research
∙
02/09/2022
Hypergraph characterization of split matroids
We provide a combinatorial study of split matroids, a class that was mot...
research
∙
01/09/2022
Inverse optimization problems with multiple weight functions
We introduce a new class of inverse optimization problems in which an in...
research
∙
01/06/2022
Efficient Approximations for Many-Visits Multiple Traveling Salesman Problems
A fundamental variant of the classical traveling salesman problem (TSP) ...
research
∙
07/21/2021
Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems
We study how good a lexicographically maximal solution is in the weighte...
research
∙
07/11/2021
A dual approach for dynamic pricing in multi-demand markets
Dynamic pricing schemes were introduced as an alternative to posted-pric...
research
∙
12/09/2020
Rainbow and monochromatic circuits and cuts in binary matroids
Given a matroid together with a coloring of its ground set, a subset of ...
research
∙
07/21/2020
A 3/2-Approximation for the Metric Many-visits Path TSP
In the Many-visits Path TSP, we are given a set of n cities along with t...
research
∙
07/17/2020
Market Pricing for Matroid Rank Valuations
In this paper, we study the problem of maximizing social welfare in comb...
research
∙
06/08/2020
Envy-free Relaxations for Goods, Chores, and Mixed Items
In fair division problems, we are given a set S of m items and a set N o...
research
∙
02/17/2020
Unique key Horn functions
Given a relational database, a key is a set of attributes such that a va...
research
∙
02/17/2020
Generating clause sequences of a CNF formula
Given a CNF formula Φ with clauses C_1,...,C_m and variables V={x_1,...,...
research
∙
11/26/2019
Scheduling with Non-Renewable Resources: Minimizing the Sum of Completion Times
The paper considers single-machine scheduling problems with a non-renewa...
research
∙
11/24/2019
List colouring of two matroids through reduction to partition matroids
In the list colouring problem for two matroids, we are given matroids M_...
research
∙
11/22/2019
Degree-Bounded Generalized Polymatroids and Approximating the Metric Many-Visits TSP
In the Bounded Degree Matroid Basis Problem, we are given a matroid and ...
research
∙
03/08/2019
Complexity of packing common bases in matroids
One of the most intriguing unsolved questions of matroid optimization is...
research
∙
11/13/2018
Approximating minimum representations of key Horn functions
Horn functions form a subclass of Boolean functions and appear in many d...
research
∙
07/25/2018
