49 citations · 71 across the 10 of their papers we have counts for
13 papers
A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges
Katarzyna Paluch, Mateusz Wasylkiewicz
We consider three variants of the problem of finding a maximum weight restricted -matching in a subcubic graph . (A -matching is any subset of the edges such that each ver…
Rectangle Tiling Binary Arrays
Pratik Ghosal, Syed Mohammad Meesum, Katarzyna Paluch
The problem of rectangle tiling binary arrays is defined as follows. Given an array of zeros and ones and a natural number , our task is to partition into a…
New Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring
Katarzyna Paluch
In the maximum asymmetric traveling salesman problem (Max ATSP) we are given a complete directed graph with nonnegative weights on the edges and we wish to compute a traveling sale…
Manipulation Strategies for the Rank Maximal Matching Problem
Pratik Ghosal, Katarzyna Paluch
We consider manipulation strategies for the rank-maximal matching problem. In the rank-maximal matching problem we are given a bipartite graph such that den…
Optimal General Matchings
Szymon Dudycz, Katarzyna Paluch
Given a graph and for each vertex a subset of the set a -matching of is any set such that $d_F(v) \in B(v…
The Dynamics of Rank-Maximal and Popular Matchings
Pratik Ghosal, Adam Kunysz, Katarzyna Paluch
Given a bipartite graph, where the two sets of vertices are applicants and posts and ranks on the edges represent preferences of applicants over posts, a {\em rank-maximal} matchin…
A - Approximation Algorithm for the Maximum Traveling Salesman Problem
Szymon Dudycz, Jan Marcinkowski, Katarzyna Paluch +1
In the maximum traveling salesman problem (Max TSP) we are given a complete undirected graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour…
Characterisation of Strongly Stable Matchings
Pratik Ghosal, Adam Kunysz, Katarzyna Paluch
An instance of a strongly stable matching problem (SSMP) is an undirected bipartite graph , with an adjacency list of each vertex being a linearly ordered list of…
Maximum ATSP with Weights Zero and One via Half-Edges
Katarzyna Paluch
We present a fast combinatorial -approximation algorithm for the maximum asymmetric TSP with weights zero and one. The approximation factor of this algorithm matches the curre…
Better Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring
Katarzyna Paluch
In the maximum asymmetric traveling salesman problem (Max ATSP) we are given a complete directed graph with nonnegative weights on the edges and we wish to compute a traveling sale…
Popular b-matchings
Katarzyna Paluch
Suppose that each member of a set of agents has a preference list of a subset of houses, possibly involving ties and each agent and house has their capacity denoting the maximum nu…
Faster and simpler approximation of stable matchings
Katarzyna Paluch
We give a 3/2-approximation algorithm for stable matchings that runs in time. The previously best known algorithm by McDermid has the same approximation ratio but runs in $O…
A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
Katarzyna Paluch, Marcin Mucha, Aleksander Madry
We give a 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem.