Source author record

Katarzyna Paluch

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Computer Science and Game Theory

Catalog footprint

Research overview

9works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges

We consider three variants of the problem of finding a maximum weight restricted $2$ -matching in a subcubic graph $G$ . (A $2$ -matching is any subset of the edges such that each vertex is incident to at most two of its edges.) Depending on the variant a restricted $2$ -matching means a $2$ -matching that is either triangle-free or square-free or both triangle- and square-free. While there exist polynomial time algorithms for the first two types of $2$ -matchings, they are quite complicated or use advanced methodology. For each of the three problems we present a simple reduction to the computation of a maximum weight $b$ -matching. The reduction is conducted with the aid of half-edges. A half-edge of edge $e$ is, informally speaking, a half of $e$ containing exactly one of its endpoints. For a subset of triangles of $G$ , we replace each edge of such a triangle with two half-edges. Two half-edges of one edge $e$ of weight $w(e)$ may get different weights, not necessarily equal to $\frac{1}{2}w(e)$ . In the metric setting when the edge weights satisfy the triangle inequality, this has a geometric interpretation connected to how an incircle partitions the edges of a triangle. Our algorithms are additionally faster than those known before. The running time of each of them is $O(n^2\log{n})$ , where $n$ denotes the number of vertices in the graph.

preprint2020arXiv

The Dynamics of Rank-Maximal and Popular Matchings

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} matching is one in which the maximum number of applicants is matched to their rank one posts and subject to this condition, the maximum number of applicants is matched to their rank two posts, and so on. We study the dynamic version of the problem in which a new applicant or post may be added to the graph and we would like to maintain a rank-maximal matching. We show that after the arrival of one vertex, we are always able to update the existing rank-maximal matching in $\mathcal{O}(\min(c'n ,n^2) + m)$ time, where $n$ denotes the number of applicants, $m$ the number of edges and $c'$ the maximum rank of an edge in an optimal solution. Additionally, we update the matching using a minimal number of changes (replacements). All cases of a deletion of a vertex/edge and an addition of an edge can be reduced to the problem of handling the addition of a vertex. As a by-product, we also get an analogous $\mathcal{O}(m)$ result for the dynamic version of the (one-sided) popular matching problem. Our results are based on the novel use of the properties of the Edmonds-Gallai decomposition. The presented ideas may find applications in other (dynamic) matching problems.

preprint2016arXiv

A $4/5$ - Approximation Algorithm for the Maximum Traveling Salesman Problem

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 of maximum weight. We present a fast combinatorial $\frac 45$ - approximation algorithm for Max TSP. The previous best approximation for this problem was $\frac 79$ . The new algorithm is based on a novel technique of eliminating difficult subgraphs via half-edges, a new method of edge coloring and a technique of exchanging edges. A half-edge of edge $e=(u,v)$ is informally speaking "a half of $e$ containing either $u$ or $v$ ".

preprint2015arXiv

Characterisation of Strongly Stable Matchings

An instance of a strongly stable matching problem (SSMP) is an undirected bipartite graph $G=(A \cup B, E)$ , with an adjacency list of each vertex being a linearly ordered list of ties, which are subsets of vertices equally good for a given vertex. Ties are disjoint and may contain one vertex. A matching $M$ is a set of vertex-disjoint edges. An edge $(x,y) \in E \setminus M$ is a {\em blocking edge} for $M$ if $x$ is either unmatched or strictly prefers $y$ to its current partner in $M$ , and $y$ is either unmatched or strictly prefers $x$ to its current partner in $M$ or is indifferent between them. A matching is {\em strongly stable} if there is no blocking edge with respect to it. We present an algorithm for the generation of all strongly stable matchings, thus solving an open problem already stated in the book by Gusfield and Irving \cite{GI}. It has previously been shown that strongly stable matchings form a distributive lattice and although the number of strongly stable matchings can be exponential in the number of vertices, we show that there exists a partial order with $O(m)$ elements representing all strongly stable matchings, where $m$ denotes the number of edges in the graph. We give two algorithms that construct two such representations: one in $O(nm^2)$ time and the other in $O(nm)$ time, where $n$ denotes the number of vertices in the graph. Note that the construction of the second representation has the same time complexity as that of computing a single strongly stable matching.

preprint2014arXiv

Better Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring

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 salesman tour of maximum weight. In this paper we give a fast combinatorial $\frac 34$ -approximation algorithm for Max ATSP. It is based on a novel use of {\it half-edges}, matchings and a new method of edge coloring. (A {\it half-edge} of edge $(u,v)$ is informally speaking "either a head or a tail of $(u,v)$ ".) The current best approximation algorithms for Max ATSP, achieving the approximation guarantee of $\frac 23$ , are due to Kaplan, Lewenstein, Shafrir and Sviridenko and Elbassioni, Paluch, van Zuylen. Using a recent result by Mucha, which states that an $α$ -approximation algorithm for Max ATSP implies a $(2+\frac{11(1-α)}{9-2α})$ -approximation algorithm for the shortest superstring problem (SSP), we obtain also a $(2 \frac{11}{30} \approx 2,3667)$ -approximation algorithm for SSP, beating the previously best known (having approximation factor equal to $2 \frac{11}{23} \approx 2,4782$ .)

preprint2014arXiv

Faster and simpler approximation of stable matchings

We give a 3/2-approximation algorithm for stable matchings that runs in $O(m)$ time. The previously best known algorithm by McDermid has the same approximation ratio but runs in $O(n^{3/2}m)$ time, where $n$ denotes the number of people and $m$ is the total length of the preference lists in a given instance. Also the algorithm and the analysis are much simpler. We also give the extension of the algorithm for the many-to-many setting. (This is the version of the paper from March 2011)

preprint2014arXiv

Maximum ATSP with Weights Zero and One via Half-Edges

We present a fast combinatorial $3/4$ -approximation algorithm for the maximum asymmetric TSP with weights zero and one. The approximation factor of this algorithm matches the currently best one given by Bläser in 2004 and based on linear programming. Our algorithm first computes a maximum size matching and a maximum weight cycle cover without certain cycles of length two but possibly with {\em half-edges} - a half-edge of a given edge $e$ is informally speaking a half of $e$ that contains one of the endpoints of $e$ . Then from the computed matching and cycle cover it extracts a set of paths, whose weight is large enough to be able to construct a traveling salesman tour with the claimed guarantee.

preprint2010arXiv

Popular b-matchings

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 number of correspondingly agents/houses that can be matched to him/her/it. We want to find a matching $M$ , for which there is no other matching $M'$ such that more agents prefer $M'$ to $M$ than $M$ to $M'$ . (What it means that an agent prefers one matching to the other is explained in the paper.) Popular matchings have been studied quite extensively, especially in the one-to-one setting. We provide a characterization of popular b-matchings for two defintions of popularity, show some $NP$ -hardness results and for certain versions describe polynomial algorithms.

preprint2008arXiv

A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem

We give a 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Katarzyna Paluch

Research overview

Is this your work?

9 publications

A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges

The Dynamics of Rank-Maximal and Popular Matchings

A $4/5$ - Approximation Algorithm for the Maximum Traveling Salesman Problem

Characterisation of Strongly Stable Matchings

Better Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring

Faster and simpler approximation of stable matchings

Maximum ATSP with Weights Zero and One via Half-Edges

Popular b-matchings

A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem

See the researcher in context

Building this map preview

Katarzyna Paluch

Research overview

Is this your work?

9 publications

A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges

The Dynamics of Rank-Maximal and Popular Matchings

A 4/54/54/5 - Approximation Algorithm for the Maximum Traveling Salesman Problem

Characterisation of Strongly Stable Matchings

Better Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring

Faster and simpler approximation of stable matchings

Maximum ATSP with Weights Zero and One via Half-Edges

Popular b-matchings

A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem

See the researcher in context

Building this map preview

A $4/5$ - Approximation Algorithm for the Maximum Traveling Salesman Problem