16 Search Results for "Woeginger, Gerhard J."


Document
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-dev.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
An Investigation of the Recoverable Robust Assignment Problem

Authors: Dennis Fischer, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)


Abstract
We investigate the so-called recoverable robust assignment problem on complete bipartite graphs, a mainstream problem in robust optimization: For two given linear cost functions c₁ and c₂ on the edges and a given integer k, the goal is to find two perfect matchings M₁ and M₂ that minimize the objective value c₁(M₁)+c₂(M₂), subject to the constraint that M₁ and M₂ have at least k edges in common. We derive a variety of results on this problem. First, we show that the problem is W[1]-hard with respect to parameter k, and also with respect to the complementary parameter k' = n/2-k. This hardness result holds even in the highly restricted special case where both cost functions c₁ and c₂ only take the values 0 and 1. (On the other hand, containment of the problem in XP is straightforward to see.) Next, as a positive result we construct a polynomial time algorithm for the special case where one cost function is Monge, whereas the other one is Anti-Monge. Finally, we study the variant where matching M₁ is frozen, and where the optimization goal is to compute the best corresponding matching M₂. This problem variant is known to be contained in the randomized parallel complexity class RNC², and we show that it is at least as hard as the infamous problem Exact Red-Blue Matching in Bipartite Graphs whose computational complexity is a long-standing open problem.

Cite as

Dennis Fischer, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. An Investigation of the Recoverable Robust Assignment Problem. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.IPEC.2021.19,
  author =	{Fischer, Dennis and Hartmann, Tim A. and Lendl, Stefan and Woeginger, Gerhard J.},
  title =	{{An Investigation of the Recoverable Robust Assignment Problem}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.19},
  URN =		{urn:nbn:de:0030-drops-154025},
  doi =		{10.4230/LIPIcs.IPEC.2021.19},
  annote =	{Keywords: assignment problem, matchings, exact matching, robust optimization, fixed paramter tractablity, RNC}
}
Document
Dispersing Obnoxious Facilities on a Graph

Authors: Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
We study a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that any two facilities have at least distance delta from each other. We investigate the complexity of this problem in terms of the rational parameter delta. The problem is polynomially solvable, if the numerator of delta is 1 or 2, while all other cases turn out to be NP-hard.

Cite as

Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. Dispersing Obnoxious Facilities on a Graph. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 33:1-33:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{grigoriev_et_al:LIPIcs.STACS.2019.33,
  author =	{Grigoriev, Alexander and Hartmann, Tim A. and Lendl, Stefan and Woeginger, Gerhard J.},
  title =	{{Dispersing Obnoxious Facilities on a Graph}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{33:1--33:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.33},
  URN =		{urn:nbn:de:0030-drops-102729},
  doi =		{10.4230/LIPIcs.STACS.2019.33},
  annote =	{Keywords: algorithms, complexity, optimization, graph theory, facility location}
}
Document
Graph Similarity and Approximate Isomorphism

Authors: Martin Grohe, Gaurav Rattan, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)


Abstract
The graph similarity problem, also known as approximate graph isomorphism or graph matching problem, has been extensively studied in the machine learning community, but has not received much attention in the algorithms community: Given two graphs G,H of the same order n with adjacency matrices A_G,A_H, a well-studied measure of similarity is the Frobenius distance dist(G,H):=min_{pi}|A_G^{pi}-A_H|_F, where pi ranges over all permutations of the vertex set of G, where A_G^pi denotes the matrix obtained from A_G by permuting rows and columns according to pi, and where |M |_F is the Frobenius norm of a matrix M. The (weighted) graph similarity problem, denoted by GSim (WSim), is the problem of computing this distance for two graphs of same order. This problem is closely related to the notoriously hard quadratic assignment problem (QAP), which is known to be NP-hard even for severely restricted cases. It is known that GSim (WSim) is NP-hard; we strengthen this hardness result by showing that the problem remains NP-hard even for the class of trees. Identifying the boundary of tractability for WSim is best done in the framework of linear algebra. We show that WSim is NP-hard as long as one of the matrices has unbounded rank or negative eigenvalues: hence, the realm of tractability is restricted to positive semi-definite matrices of bounded rank. Our main result is a polynomial time algorithm for the special case where the associated (weighted) adjacency graph for one of the matrices has a bounded number of twin equivalence classes. The key parameter underlying our algorithm is the clustering number of a graph; this parameter arises in context of the spectral graph drawing machinery.

Cite as

Martin Grohe, Gaurav Rattan, and Gerhard J. Woeginger. Graph Similarity and Approximate Isomorphism. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.MFCS.2018.20,
  author =	{Grohe, Martin and Rattan, Gaurav and Woeginger, Gerhard J.},
  title =	{{Graph Similarity and Approximate Isomorphism}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.20},
  URN =		{urn:nbn:de:0030-drops-96021},
  doi =		{10.4230/LIPIcs.MFCS.2018.20},
  annote =	{Keywords: Graph Similarity, Quadratic Assignment Problem, Approximate Graph Isomorphism}
}
Document
The Open Shop Scheduling Problem

Authors: Gerhard J. Woeginger

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)


Abstract
We discuss the computational complexity, the approximability, the algorithmics and the combinatorics of the open shop scheduling problem. We summarize the most important results from the literature and explain their main ideas, we sketch the most beautiful proofs, and we also list a number of open problems.

Cite as

Gerhard J. Woeginger. The Open Shop Scheduling Problem. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{woeginger:LIPIcs.STACS.2018.4,
  author =	{Woeginger, Gerhard J.},
  title =	{{The Open Shop Scheduling Problem}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.4},
  URN =		{urn:nbn:de:0030-drops-85375},
  doi =		{10.4230/LIPIcs.STACS.2018.4},
  annote =	{Keywords: Algorithms, Complexity, Scheduling, Approximation}
}
Document
Motion planning with pulley, rope, and baskets

Authors: Christian E.J. Eggermont and Gerhard J. Woeginger

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)


Abstract
We study a motion planning problem where items have to be transported from the top room of a tower to the bottom of the tower, while simultaneously other items have to be transported into the opposite direction. Item sets are moved in two baskets hanging on a rope and pulley. To guarantee stability of the system, the weight difference between the contents of the two baskets must always stay below a given threshold. We prove that it is Pi-2-p-complete to decide whether some given initial situation of the underlying discrete system can lead to a given goal situation. Furthermore we identify several polynomially solvable special cases of this reachability problem, and we also settle the computational complexity of a number of related questions.

Cite as

Christian E.J. Eggermont and Gerhard J. Woeginger. Motion planning with pulley, rope, and baskets. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 374-383, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{eggermont_et_al:LIPIcs.STACS.2012.374,
  author =	{Eggermont, Christian E.J. and Woeginger, Gerhard J.},
  title =	{{Motion planning with pulley, rope, and baskets}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{374--383},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.374},
  URN =		{urn:nbn:de:0030-drops-33900},
  doi =		{10.4230/LIPIcs.STACS.2012.374},
  annote =	{Keywords: planning and scheduling; computational complexity}
}
Document
Analysis of multi-stage open shop processing systems

Authors: Christian E.J. Eggermont, Alexander Schrijver, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)


Abstract
We study algorithmic problems in multi-stage open shop processing systems that are centered around reachability and deadlock detection questions. We characterize safe and unsafe system states. We show that it is easy to recognize system states that can be reached from the initial state (where the system is empty), but that in general it is hard to decide whether one given system state is reachable from another given system state. We show that the problem of identifying reachable deadlock states is hard in general open shop systems, but is easy in the special case where no job needs processing on more than two machines (by linear programming and matching theory), and in the special case where all machines have capacity one (by graph-theoretic arguments).

Cite as

Christian E.J. Eggermont, Alexander Schrijver, and Gerhard J. Woeginger. Analysis of multi-stage open shop processing systems. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 484-494, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{eggermont_et_al:LIPIcs.STACS.2011.484,
  author =	{Eggermont, Christian E.J. and Schrijver, Alexander and Woeginger, Gerhard J.},
  title =	{{Analysis of multi-stage open shop processing systems}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{484--494},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.484},
  URN =		{urn:nbn:de:0030-drops-30373},
  doi =		{10.4230/LIPIcs.STACS.2011.484},
  annote =	{Keywords: scheduling, resource allocation, deadlock, computational complexity}
}
Document
10071 Open Problems – Scheduling

Authors: Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)


Abstract
Collection of the open problems presented at the scheduling seminar.

Cite as

Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger. 10071 Open Problems – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.10071.3,
  author =	{Anderson, Jim and Andersson, Bj\"{o}rn and Azar, Yossi and Bansal, Nikhil and Bini, Enrico and Chrobak, Marek and Correa, Jos\'{e} and Cucu-Grosjean, Liliana and Davis, Rob and Easwaran, Arvind and Edmonds, Jeff and Funk, Shelby and Gopalakrishnan, Sathish and Hoogeveen, Han and Mathieu, Claire and Megow, Nicole and Naor, Seffi and Pruhs, Kirk and Queyranne, Maurice and Ros\'{e}n, Adi and Schabanel, Nicolas and Sgall, Ji\v{r}{\'\i} and Sitters, Ren\'{e} and Stiller, Sebastian and Uetz, Marc and Vredeveld, Tjark and Woeginger, Gerhard J.},
  title =	{{10071 Open Problems – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.3},
  URN =		{urn:nbn:de:0030-drops-25367},
  doi =		{10.4230/DagSemProc.10071.3},
  annote =	{Keywords: Open problems, scheduling}
}
Document
The Traveling Salesman Problem under Squared Euclidean Distances

Authors: Fred van Nijnatten, René Sitters, Gerhard J. Woeginger, Alexander Wolff, and Mark de Berg

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)


Abstract
Let $P$ be a set of points in $\Reals^d$, and let $\alpha \ge 1$ be a real number. We define the distance between two points $p,q\in P$ as $|pq|^{\alpha}$, where $|pq|$ denotes the standard Euclidean distance between $p$ and $q$. We denote the traveling salesman problem under this distance function by \tsp($d,\alpha$). We design a 5-approximation algorithm for \tsp(2,2) and generalize this result to obtain an approximation factor of $3^{\alpha-1}+\sqrt{6}^{\,\alpha}\!/3$ for $d=2$ and all $\alpha\ge2$. We also study the variant Rev-\tsp\ of the problem where the traveling salesman is allowed to revisit points. We present a polynomial-time approximation scheme for Rev-\tsp$(2,\alpha)$ with $\alpha\ge2$, and we show that Rev-\tsp$(d, \alpha)$ is \apx-hard if $d\ge3$ and $\alpha>1$. The \apx-hardness proof carries over to \tsp$(d, \alpha)$ for the same parameter ranges.

Cite as

Fred van Nijnatten, René Sitters, Gerhard J. Woeginger, Alexander Wolff, and Mark de Berg. The Traveling Salesman Problem under Squared Euclidean Distances. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 239-250, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{vannijnatten_et_al:LIPIcs.STACS.2010.2458,
  author =	{van Nijnatten, Fred and Sitters, Ren\'{e} and Woeginger, Gerhard J. and Wolff, Alexander and de Berg, Mark},
  title =	{{The Traveling Salesman Problem under Squared Euclidean Distances}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{239--250},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2458},
  URN =		{urn:nbn:de:0030-drops-24580},
  doi =		{10.4230/LIPIcs.STACS.2010.2458},
  annote =	{Keywords: Geometric traveling salesman problem, power-assignment in wireless networks, distance-power gradient, NP-hard, APX-hard}
}
Document
07261 Abstracts Collection – Fair Division

Authors: Steven J. Brams and Kirk Pruhs

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)


Abstract
From 24.06. to 29.06.2007, the Dagstuhl Seminar 07261 % generate automatically ``Fair Division'' % generate automatically was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Steven J. Brams and Kirk Pruhs. 07261 Abstracts Collection – Fair Division. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{brams_et_al:DagSemProc.07261.1,
  author =	{Brams, Steven J. and Pruhs, Kirk},
  title =	{{07261 Abstracts Collection – Fair Division}},
  booktitle =	{Fair Division},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.1},
  URN =		{urn:nbn:de:0030-drops-12444},
  doi =		{10.4230/DagSemProc.07261.1},
  annote =	{Keywords: Economics, Fairness, Allocation, Political Science}
}
Document
07261 Summary – Fair Division

Authors: Steven J. Brams and Kirk Pruhs

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)


Abstract
The problem of fair division – dividing goods or "bads" (e.g., costs) among entities in an impartial and equitable way – is one of the most important problems that society faces. A Google search on the phrase "fair allocation" returns over 100K links, referring to the division of sports tickets, health resources, computer networking resources, voting power, intellectual property licenses, costs of environmental improvements, etc.

Cite as

Steven J. Brams and Kirk Pruhs. 07261 Summary – Fair Division. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{brams_et_al:DagSemProc.07261.2,
  author =	{Brams, Steven J. and Pruhs, Kirk},
  title =	{{07261 Summary  – Fair Division}},
  booktitle =	{Fair Division},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.2},
  URN =		{urn:nbn:de:0030-drops-12434},
  doi =		{10.4230/DagSemProc.07261.2},
  annote =	{Keywords: Economics, Fairness, Allocation, Political Science}
}
Document
Better Ways to Cut a Cake - Revisited

Authors: Steven J. Brams, Michael A. Jones, and Christian Klamler

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)


Abstract
Procedures to divide a cake among n people with n-1 cuts (the minimum number) are analyzed and compared. For 2 persons, cut-and-choose, while envy-free and efficient, limits the cutter to exactly 50% if he or she is ignorant of the chooser's preferences, whereas the chooser can generally obtain more. By comparison, a new 2-person surplus procedure (SP'), which induces the players to be truthful in order to maximize their minimum allocations, leads to a proportionally equitable division of the surplus - the part that remains after each player receives 50% - by giving each person a certain proportion of the surplus as he or she values it. For n geq 3 persons, a new equitable procedure (EP) yields a maximally equitable division of a cake. This division gives all players the highest common value that they can achieve and induces truthfulness, but it may not be envy-free. The applicability of SP' and EP to the fair division of a heterogeneous, divisible good, like land, is briefly discussed.

Cite as

Steven J. Brams, Michael A. Jones, and Christian Klamler. Better Ways to Cut a Cake - Revisited. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{brams_et_al:DagSemProc.07261.5,
  author =	{Brams, Steven J. and Jones, Michael A. and Klamler, Christian},
  title =	{{Better Ways to Cut a Cake - Revisited}},
  booktitle =	{Fair Division},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.5},
  URN =		{urn:nbn:de:0030-drops-12278},
  doi =		{10.4230/DagSemProc.07261.5},
  annote =	{Keywords: Fair division, cake-cutting, envy-freeness, strategy-proofness}
}
Document
Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Procedure

Authors: Steven J. Brams, Michael A. Jones, and Christian Klamler

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)


Abstract
Properties of discrete cake-cutting procedures that use a minimal number of cuts (n-1 if there are n players) are analyzed. None is always envy-free or efficient, but divide-and-conquer (D&C) minimizes the maximum number of players that any single player may envy. It works by asking n ≥ 2 players successively to place marks on a cake that divide it into equal or approximately equal halves, then halves of these halves, and so on. Among other properties, D&C (i) ensures players of more than 1/n shares if their marks are different and (ii) is strategyproof for risk-averse players. However, D&C may not allow players to obtain proportional, connected pieces if they have unequal entitlements. Possible applications of D&C to land division are briefly discussed.

Cite as

Steven J. Brams, Michael A. Jones, and Christian Klamler. Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Procedure. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{brams_et_al:DagSemProc.07261.6,
  author =	{Brams, Steven J. and Jones, Michael A. and Klamler, Christian},
  title =	{{Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Procedure}},
  booktitle =	{Fair Division},
  pages =	{1--31},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.6},
  URN =		{urn:nbn:de:0030-drops-12211},
  doi =		{10.4230/DagSemProc.07261.6},
  annote =	{Keywords: Cake-cutting, proportionality, envy-freeness, efficiency, strategy-proofness}
}
Document
The Travelling Salesman Problem (Dagstuhl Seminar 02261)

Authors: David S. Johnson, Jan Karel Lenstra, and Gerhard J. Woeginger

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

David S. Johnson, Jan Karel Lenstra, and Gerhard J. Woeginger. The Travelling Salesman Problem (Dagstuhl Seminar 02261). Dagstuhl Seminar Report 346, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2004)


Copy BibTex To Clipboard

@TechReport{johnson_et_al:DagSemRep.346,
  author =	{Johnson, David S. and Lenstra, Jan Karel and Woeginger, Gerhard J.},
  title =	{{The Travelling Salesman Problem (Dagstuhl Seminar 02261)}},
  pages =	{1--17},
  ISSN =	{1619-0203},
  year =	{2004},
  type = 	{Dagstuhl Seminar Report},
  number =	{346},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.346},
  URN =		{urn:nbn:de:0030-drops-152271},
  doi =		{10.4230/DagSemRep.346},
}
Document
Graph Colorings (Dagstuhl Seminar 03391)

Authors: Jaroslav Nesetril and Gerhard J. Woeginger

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Jaroslav Nesetril and Gerhard J. Woeginger. Graph Colorings (Dagstuhl Seminar 03391). Dagstuhl Seminar Report 395, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)


Copy BibTex To Clipboard

@TechReport{nesetril_et_al:DagSemRep.395,
  author =	{Nesetril, Jaroslav and Woeginger, Gerhard J.},
  title =	{{Graph Colorings (Dagstuhl Seminar 03391)}},
  pages =	{1--6},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{395},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.395},
  URN =		{urn:nbn:de:0030-drops-152757},
  doi =		{10.4230/DagSemRep.395},
}
  • Refine by Author
  • 11 Woeginger, Gerhard J.
  • 4 Brams, Steven J.
  • 3 Pruhs, Kirk
  • 2 Eggermont, Christian E.J.
  • 2 Hartmann, Tim A.
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Discrete optimization
  • Show More...

  • Refine by Keyword
  • 2 Allocation
  • 2 Economics
  • 2 Fairness
  • 2 Political Science
  • 2 envy-freeness
  • Show More...

  • Refine by Type
  • 16 document

  • Refine by Publication Year
  • 4 2007
  • 2 2010
  • 2 2018
  • 1 2002
  • 1 2003
  • Show More...

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