Search Results

Documents authored by Chen, Jiehua

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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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