11 Search Results for "Chen, Jiehua"

Document
DOI: 10.4230/DagRep.15.8.29
Frontiers of Parameterized Algorithmics of Matching under Preferences (Dagstuhl Seminar 25342)

Authors: Jiehua Chen, Christine Cheng, David Manlove, Ildikó Schlotter, and Manuel Sorge

Published in: Dagstuhl Reports, Volume 15, Issue 8 (2026)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 25342 "Frontiers of Parameterized Algorithmics of Matching under Preferences", held from August 17-22, 2025. The seminar brought together researchers from the Matching Under Preferences (MATCH-UP) and Parameterized Complexity Theory (PCT) communities to systematically apply parameterized techniques to computationally hard matching problems. The program included tutorials on parameterized algorithmics, surveys on MATCH-UP complexity and structure of stable matchings, contributed talks, and intensive working group sessions that explored fundamental open problems. This seminar represents the first focused effort to comprehensively map the parameterized complexity landscape of matching markets, establishing frameworks for ongoing collaboration between these communities. The report presents abstracts of talks, tutorials, working groups, and open problems in alphabetical order by speaker.
Cite as

Jiehua Chen, Christine Cheng, David Manlove, Ildikó Schlotter, and Manuel Sorge. Frontiers of Parameterized Algorithmics of Matching under Preferences (Dagstuhl Seminar 25342). In Dagstuhl Reports, Volume 15, Issue 8, pp. 29-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{chen_et_al:DagRep.15.8.29,
  author =	{Chen, Jiehua and Cheng, Christine and Manlove, David and Schlotter, Ildik\'{o} and Sorge, Manuel},
  title =	{{Frontiers of Parameterized Algorithmics of Matching under Preferences (Dagstuhl Seminar 25342)}},
  pages =	{29--45},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2026},
  volume =	{15},
  number =	{8},
  editor =	{Chen, Jiehua and Cheng, Christine and Manlove, David and Schlotter, Ildik\'{o} and Sorge, Manuel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.8.29},
  URN =		{urn:nbn:de:0030-drops-257744},
  doi =		{10.4230/DagRep.15.8.29},
  annote =	{Keywords: Algorithmic design and complexity analysis, Matching markets, Matching theory, Parameterizec complexity analysis}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.14
A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma

Authors: Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, and Meirav Zehavi

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We present an algorithm for a class of n-fold ILPs whose existing algorithms in literature are often either (1) based on the augmentation framework where one starts with an arbitrary solution and then iteratively moves towards an optimal solution by solving appropriate programs; or (2) require solving a linear relaxation of the program; or (3) are based on decomposition/proximity based arguments. Combinatorial n-fold ILPs is a class of n-fold ILPs introduced and studied by Knop et al. [MP2020] that captures several other problems in a variety of domains. We present a simple and direct algorithm that solves combinatorial n-fold ILPs with unbounded non-negative variables via an application of the Steinitz lemma. Depending on the structure of the input ILP, we also improve upon the existing algorithms in the literature in terms of the running time, thereby showing an improvement that mirrors the one shown by Rohwedder [ICALP2025] contemporaneously and independently.
Cite as

Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, and Meirav Zehavi. A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.IPEC.2025.14,
  author =	{Gupta, Sushmita and Jain, Pallavi and Seetharaman, Sanjay and Zehavi, Meirav},
  title =	{{A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.14},
  URN =		{urn:nbn:de:0030-drops-251467},
  doi =		{10.4230/LIPIcs.IPEC.2025.14},
  annote =	{Keywords: n-fold integer linear program, parameterized algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.38
Fairness and Efficiency in Two-Sided Matching Markets

Authors: Pallavi Jain, Palash Jha, and Shubham Solanki

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We propose a new fairness notion, motivated by the practical challenge of allocating teaching assistants (TAs) to courses in a department. Each course requires a certain number of TAs and each TA has preferences over the courses they want to assist. Similarly, each course instructor has preferences over the TAs who applied for their course. We demand fairness and efficiency for both sides separately, giving rise to the following criteria: (i) every course gets the required number of TAs and the average utility of the assigned TAs meets a threshold; (ii) the allocation of courses to TAs is envy-free, where a TA envies another TA if the former prefers the latter’s course and has a higher or equal grade in that course. Note that the definition of envy-freeness here differs from the one in the literature, and we call it merit-based envy-freeness. We show that the problem of finding a merit-based envy-free and efficient matching is NP-hard even for very restricted settings, such as two courses and uniform valuations; constant degree, constant capacity of TAs for every course, valuations in the range {0,1,2,3}, identical valuations from TAs, and even more. To find tractable results, we consider some restricted instances, such as, strict valuation of TAs for courses, the difference between the number of positively valued TAs for a course and the capacity, the number of positively valued TAs/courses, types of valuation functions, and obtained some polynomial-time solvable cases, showing the contrast with intractable results. We further studied the problem in the paradigm of parameterized algorithms and designed some exact and approximation algorithms.
Cite as

Pallavi Jain, Palash Jha, and Shubham Solanki. Fairness and Efficiency in Two-Sided Matching Markets. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jain_et_al:LIPIcs.FSTTCS.2025.38,
  author =	{Jain, Pallavi and Jha, Palash and Solanki, Shubham},
  title =	{{Fairness and Efficiency in Two-Sided Matching Markets}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.38},
  URN =		{urn:nbn:de:0030-drops-251186},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.38},
  annote =	{Keywords: Fair Matching, Envy-Freeness, Efficiency}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.54
Reforming an Unfair Allocation by Exchanging Goods

Authors: Sheung Man Yuen, Ayumi Igarashi, Naoyuki Kamiyama, and Warut Suksompong

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Fairly allocating indivisible goods is a frequently occurring task in everyday life. Given an initial allocation of the goods, we consider the problem of reforming it via a sequence of exchanges to attain fairness in the form of envy-freeness up to one good (EF1). We present a vast array of results on the complexity of determining whether it is possible to reach an EF1 allocation from the initial allocation and, if so, the minimum number of exchanges required. In particular, we uncover several distinctions based on the number of agents involved and their utility functions. Furthermore, we derive essentially tight bounds on the worst-case number of exchanges needed to achieve EF1.
Cite as

Sheung Man Yuen, Ayumi Igarashi, Naoyuki Kamiyama, and Warut Suksompong. Reforming an Unfair Allocation by Exchanging Goods. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 54:1-54:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{yuen_et_al:LIPIcs.ISAAC.2025.54,
  author =	{Yuen, Sheung Man and Igarashi, Ayumi and Kamiyama, Naoyuki and Suksompong, Warut},
  title =	{{Reforming an Unfair Allocation by Exchanging Goods}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{54:1--54:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.54},
  URN =		{urn:nbn:de:0030-drops-249626},
  doi =		{10.4230/LIPIcs.ISAAC.2025.54},
  annote =	{Keywords: fair division, indivisible goods, envy-freeness, exchanges}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.9
Geometric Realizations of Dichotomous Ordinal Graphs

Authors: Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, and Antonios Symvonis

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
A dichotomous ordinal graph consists of an undirected graph with a partition of the edges into short and long edges. A geometric realization of a dichotomous ordinal graph G in a metric space X is a drawing of G in X in which every long edge is strictly longer than every short edge. We call a graph G pandichotomous in X if G admits a geometric realization in X for every partition of its edge set into short and long edges. We exhibit a very close relationship between the degeneracy of a graph G and its pandichotomic Euclidean or spherical dimension, that is, the smallest dimension k such that G is pandichotomous in ℝ^k or the sphere 𝒮^k, respectively. First, every d-degenerate graph is pandichotomous in ℝ^d and 𝒮^{d-1} and these bounds are tight for the sphere and for ℝ² and almost tight for ℝ^d, for d ≥ 3. Second, every n-vertex graph that is pandichotomous in ℝ^k has at most μ kn edges, for some absolute constant μ < 7.23. This shows that the pandichotomic Euclidean dimension of any graph is linearly tied to its degeneracy and in the special case k ∈ {1,2} resolves open problems posed by Alam, Kobourov, Pupyrev, and Toeniskoetter. Further, we characterize which complete bipartite graphs are pandichotomous in ℝ²: These are exactly the K_{m,n} with m ≤ 3 or m = 4 and n ≤ 6. For general bipartite graphs, we can guarantee realizations in ℝ² if the short or the long subgraph is constrained: namely if the short subgraph is outerplanar or a subgraph of a rectangular grid, or if the long subgraph forms a caterpillar.
Cite as

Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, and Antonios Symvonis. Geometric Realizations of Dichotomous Ordinal Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.SoCG.2025.9,
  author =	{Angelini, Patrizio and Cornelsen, Sabine and Haase, Carolina and Hoffmann, Michael and Katsanou, Eleni and Montecchiani, Fabrizio and Steiner, Raphael and Symvonis, Antonios},
  title =	{{Geometric Realizations of Dichotomous Ordinal Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.9},
  URN =		{urn:nbn:de:0030-drops-231616},
  doi =		{10.4230/LIPIcs.SoCG.2025.9},
  annote =	{Keywords: Ordinal embeddings, geometric graphs, graph representations}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.20
Group Fairness and Multi-Criteria Optimization in School Assignment

Authors: Santhini K. A., Kamesh Munagala, Meghana Nasre, and Govind S. Sankar

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract
We consider the problem of assigning students to schools when students have different utilities for schools and schools have limited capacities. The students belong to demographic groups, and fairness over these groups is captured either by concave objectives, or additional constraints on the utility of the groups. We present approximation algorithms for this assignment problem with group fairness via convex program rounding. These algorithms achieve various trade-offs between capacity violation and running time. We also show that our techniques easily extend to the setting where there are arbitrary constraints on the feasible assignment, capturing multi-criteria optimization. We present simulation results that demonstrate that the rounding methods are practical even on large problem instances, with the empirical capacity violation being much better than the theoretical bounds.
Cite as

Santhini K. A., Kamesh Munagala, Meghana Nasre, and Govind S. Sankar. Group Fairness and Multi-Criteria Optimization in School Assignment. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{k.a._et_al:LIPIcs.FORC.2025.20,
  author =	{K. A., Santhini and Munagala, Kamesh and Nasre, Meghana and S. Sankar, Govind},
  title =	{{Group Fairness and Multi-Criteria Optimization in School Assignment}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.20},
  URN =		{urn:nbn:de:0030-drops-231471},
  doi =		{10.4230/LIPIcs.FORC.2025.20},
  annote =	{Keywords: School Assignment, Approximation Algorithms, Group Fairness}
}
Document
DOI: 10.4230/DagRep.12.7.1
Algorithms for Participatory Democracy (Dagstuhl Seminar 22271)

Authors: Markus Brill, Jiehua Chen, Andreas Darmann, David Pennock, and Matthias Greger

Published in: Dagstuhl Reports, Volume 12, Issue 7 (2023)

Abstract
Participatory democracy aims to make democratic processes more engaging and responsive by giving all citizens the opportunity to participate, and express their preferences, at many stages of decision-making processes beyond electing representatives. Recent years have witnessed an increasing interest in participatory democracy systems, enabled by modern information and communication technology. Participation at scale gives rise to a number of algorithmic challenges. In this seminar, we addressed these challenges by bringing together experts from computational social choice (COMSOC) and related fields. In particular, we studied algorithms for online decision-making platforms and for participatory budgeting processes. We also explored how innovations such as prediction markets, liquid democracy, quadratic voting, and blockchain can be employed to improve participatory decision-making systems.
Cite as

Markus Brill, Jiehua Chen, Andreas Darmann, David Pennock, and Matthias Greger. Algorithms for Participatory Democracy (Dagstuhl Seminar 22271). In Dagstuhl Reports, Volume 12, Issue 7, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{brill_et_al:DagRep.12.7.1,
  author =	{Brill, Markus and Chen, Jiehua and Darmann, Andreas and Pennock, David and Greger, Matthias},
  title =	{{Algorithms for Participatory Democracy (Dagstuhl Seminar 22271)}},
  pages =	{1--18},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{7},
  editor =	{Brill, Markus and Chen, Jiehua and Darmann, Andreas and Pennock, David and Greger, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.7.1},
  URN =		{urn:nbn:de:0030-drops-176096},
  doi =		{10.4230/DagRep.12.7.1},
  annote =	{Keywords: liquid democracy, participatory budgeting, social choice and currency, platforms for collective decision making}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.36
Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space

Authors: Jiehua Chen and Sanjukta Roy

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We investigate the Euclidean 𝖽-Dimensional Stable Roommates problem, which asks whether a given set V of 𝖽⋅ n points from the 2-dimensional Euclidean space can be partitioned into n disjoint (unordered) subsets Π = {V₁,…,V_{n}} with |V_i| = 𝖽 for each V_i ∈ Π such that Π is {stable}. Here, {stability} means that no point subset W ⊆ V is blocking Π, and W is said to be {blocking} Π if |W| = 𝖽 such that ∑_{w' ∈ W}δ(w,w') < ∑_{v ∈ Π(w)}δ(w,v) holds for each point w ∈ W, where Π(w) denotes the subset V_i ∈ Π which contains w and δ(a,b) denotes the Euclidean distance between points a and b. Complementing the existing known polynomial-time result for 𝖽 = 2, we show that such polynomial-time algorithms cannot exist for any fixed number 𝖽 ≥ 3 unless P=NP. Our result for 𝖽 = 3 answers a decade-long open question in the theory of Stable Matching and Hedonic Games [Iwama et al., 2007; Arkin et al., 2009; Vladimir G. Deineko and Gerhard J. Woeginger, 2013; Vladimir G. Deineko and Gerhard J. Woeginger, 2013; David F. Manlove, 2013].
Cite as

Jiehua Chen and Sanjukta Roy. Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ESA.2022.36,
  author =	{Chen, Jiehua and Roy, Sanjukta},
  title =	{{Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.36},
  URN =		{urn:nbn:de:0030-drops-169741},
  doi =		{10.4230/LIPIcs.ESA.2022.36},
  annote =	{Keywords: stable matchings, multidimensional stable roommates, Euclidean preferences, coalition formation games, stable cores, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.28
On Computing Centroids According to the p-Norms of Hamming Distance Vectors

Authors: Jiehua Chen, Danny Hermelin, and Manuel Sorge

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In this paper we consider the p-Norm Hamming Centroid problem which asks to determine whether some given strings have a centroid with a bound on the p-norm of its Hamming distances to the strings. Specifically, given a set S of strings and a real k, we consider the problem of determining whether there exists a string s^* with (sum_{s in S} d^{p}(s^*,s))^(1/p) <=k, where d(,) denotes the Hamming distance metric. This problem has important applications in data clustering and multi-winner committee elections, and is a generalization of the well-known polynomial-time solvable Consensus String (p=1) problem, as well as the NP-hard Closest String (p=infty) problem. Our main result shows that the problem is NP-hard for all fixed rational p > 1, closing the gap for all rational values of p between 1 and infty. Under standard complexity assumptions the reduction also implies that the problem has no 2^o(n+m)-time or 2^o(k^(p/(p+1)))-time algorithm, where m denotes the number of input strings and n denotes the length of each string, for any fixed p > 1. The first bound matches a straightforward brute-force algorithm. The second bound is tight in the sense that for each fixed epsilon > 0, we provide a 2^(k^(p/((p+1))+epsilon))-time algorithm. In the last part of the paper, we complement our hardness result by presenting a fixed-parameter algorithm and a factor-2 approximation algorithm for the problem.
Cite as

Jiehua Chen, Danny Hermelin, and Manuel Sorge. On Computing Centroids According to the p-Norms of Hamming Distance Vectors. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ESA.2019.28,
  author =	{Chen, Jiehua and Hermelin, Danny and Sorge, Manuel},
  title =	{{On Computing Centroids According to the p-Norms of Hamming Distance Vectors}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.28},
  URN =		{urn:nbn:de:0030-drops-111495},
  doi =		{10.4230/LIPIcs.ESA.2019.28},
  annote =	{Keywords: Strings, Clustering, Multiwinner Election, Hamming Distance}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.24
Cluster Editing in Multi-Layer and Temporal Graphs

Authors: Jiehua Chen, Hendrik Molter, Manuel Sorge, and Ondrej Suchý

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-Layer Cluster Editing we receive a set of graphs on the same vertex set, called layers and aim to transform all layers into cluster graphs (disjoint unions of cliques) that differ only slightly. More specifically, we want to mark at most d vertices and to transform each layer into a cluster graph using at most k edge additions or deletions per layer so that, if we remove the marked vertices, we obtain the same cluster graph in all layers. In Temporal Cluster Editing we receive a sequence of layers and we want to transform each layer into a cluster graph so that consecutive layers differ only slightly. That is, we want to transform each layer into a cluster graph with at most k edge additions or deletions and to mark a distinct set of d vertices in each layer so that each two consecutive layers are the same after removing the vertices marked in the first of the two layers. We study the combinatorial structure of the two problems via their parameterized complexity with respect to the parameters d and k, among others. Despite the similar definition, the two problems behave quite differently: In particular, Multi-Layer Cluster Editing is fixed-parameter tractable with running time k^{O(k + d)} s^{O(1)} for inputs of size s, whereas Temporal Cluster Editing is W[1]-hard with respect to k even if d = 3.
Cite as

Jiehua Chen, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Cluster Editing in Multi-Layer and Temporal Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2018.24,
  author =	{Chen, Jiehua and Molter, Hendrik and Sorge, Manuel and Such\'{y}, Ondrej},
  title =	{{Cluster Editing in Multi-Layer and Temporal Graphs}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.24},
  URN =		{urn:nbn:de:0030-drops-99729},
  doi =		{10.4230/LIPIcs.ISAAC.2018.24},
  annote =	{Keywords: Cluster Editing, Temporal Graphs, Multi-Layer Graphs, Fixed-Parameter Algorithms, Polynomial Kernels, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.35
How Hard Is It to Satisfy (Almost) All Roommates?

Authors: Jiehua Chen, Danny Hermelin, Manuel Sorge, and Harel Yedidsion

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
The classic Stable Roommates problem (the non-bipartite generalization of the well-known Stable Marriage problem) asks whether there is a stable matching for a given set of agents, i.e. a partitioning of the agents into disjoint pairs such that no two agents induce a blocking pair. Herein, each agent has a preference list denoting who it prefers to have as a partner, and two agents are blocking if they prefer to be with each other rather than with their assigned partners. Since stable matchings may not be unique, we study an NP-hard optimization variant of Stable Roommates, called Egal Stable Roommates, which seeks to find a stable matching with a minimum egalitarian cost gamma, i.e. the sum of the dissatisfaction of the agents is minimum. The dissatisfaction of an agent is the number of agents that this agent prefers over its partner if it is matched; otherwise it is the length of its preference list. We also study almost stable matchings, called Min-Block-Pair Stable Roommates, which seeks to find a matching with a minimum number beta of blocking pairs. Our main result is that Egal Stable Roommates parameterized by gamma is fixed-parameter tractable, while Min-Block-Pair Stable Roommates parameterized by beta is W[1]-hard, even if the length of each preference list is at most five.
Cite as

Jiehua Chen, Danny Hermelin, Manuel Sorge, and Harel Yedidsion. How Hard Is It to Satisfy (Almost) All Roommates?. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2018.35,
  author =	{Chen, Jiehua and Hermelin, Danny and Sorge, Manuel and Yedidsion, Harel},
  title =	{{How Hard Is It to Satisfy (Almost) All Roommates?}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.35},
  URN =		{urn:nbn:de:0030-drops-90398},
  doi =		{10.4230/LIPIcs.ICALP.2018.35},
  annote =	{Keywords: NP-hard problems Data reduction rules Kernelizations Parameterized complexity analysis and algorithmics}
}
  • Refine by Type
  • 11 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 1 2023
  • 1 2022
  • 1 2019
  • Show More...

  • Refine by Author
  • 6 Chen, Jiehua
  • 4 Sorge, Manuel
  • 2 Hermelin, Danny
  • 2 Jain, Pallavi
  • 1 Angelini, Patrizio
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs
  • 2 DagRep

  • Refine by Classification
  • 4 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Algorithmic game theory and mechanism design
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Mathematics of computing → Combinatorial optimization
  • 2 Theory of computation → Algorithmic game theory
  • Show More...

  • Refine by Keyword
  • 1 Algorithmic design and complexity analysis
  • 1 Approximation Algorithms
  • 1 Cluster Editing
  • 1 Clustering
  • 1 Efficiency
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact