93 Search Results for "Faliszewski, Piotr"


Volume

LIPIcs, Volume 58

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

MFCS 2016, August 22-26, 2016, Kraków, Poland

Editors: Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier

Document
Voting: Beyond Simple Majorities and Single-Winner Elections (Dagstuhl Seminar 17261)

Authors: Dorothea Baumeister, Piotr Faliszewski, Annick Laruelle, and Toby Walsh

Published in: Dagstuhl Reports, Volume 7, Issue 6 (2018)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17261 "Voting: Beyond simple majorities and single-winner elections". The seminar featured five survey talks, a series of classic scientific presentations, working group discussions, open problems sessions (with the first one used to establish working groups and the last one to present their results). The seminar was mostly focused on multiwinner elections (from discussions of their algorithmic properties to political-science considerations), but the topics of real-life voting experiments and strategic behavior received attention as well.

Cite as

Dorothea Baumeister, Piotr Faliszewski, Annick Laruelle, and Toby Walsh. Voting: Beyond Simple Majorities and Single-Winner Elections (Dagstuhl Seminar 17261). In Dagstuhl Reports, Volume 7, Issue 6, pp. 109-134, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@Article{baumeister_et_al:DagRep.7.6.109,
  author =	{Baumeister, Dorothea and Faliszewski, Piotr and Laruelle, Annick and Walsh, Toby},
  title =	{{Voting: Beyond Simple Majorities and Single-Winner Elections (Dagstuhl Seminar 17261)}},
  pages =	{109--134},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{6},
  editor =	{Baumeister, Dorothea and Faliszewski, Piotr and Laruelle, Annick and Walsh, Toby},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.6.109},
  URN =		{urn:nbn:de:0030-drops-82882},
  doi =		{10.4230/DagRep.7.6.109},
  annote =	{Keywords: artificial intelligence, collective decision making, computational social choice, multi agent systems, preference aggregation, preference elicitation}
}
Document
Complete Volume
LIPIcs, Volume 58, MFCS'16, Complete Volume

Authors: Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
LIPIcs, Volume 58, MFCS'16, Complete Volume

Cite as

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@Proceedings{faliszewski_et_al:LIPIcs.MFCS.2016,
  title =	{{LIPIcs, Volume 58, MFCS'16, Complete Volume}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016},
  URN =		{urn:nbn:de:0030-drops-65861},
  doi =		{10.4230/LIPIcs.MFCS.2016},
  annote =	{Keywords: Theory of Computation}
}
Document
Front Matter
Front Matter, Foreword, Conference Organization, External Reviewers, Table of Contents

Authors: Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
Front Matter, Foreword, Conference Organization, External Reviewers, Table of Contents

Cite as

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{faliszewski_et_al:LIPIcs.MFCS.2016.0,
  author =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  title =	{{Front Matter, Foreword, Conference Organization, External Reviewers, Table of Contents}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.0},
  URN =		{urn:nbn:de:0030-drops-64225},
  doi =		{10.4230/LIPIcs.MFCS.2016.0},
  annote =	{Keywords: front matter, foreword, conference organization, external reviewers, table of contents}
}
Document
Invited Talk
How Far Are We From Having a Satisfactory Theory of Clustering? (Invited Talk)

Authors: Shai Ben-David

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
This is an overview of the invited talk delivered at the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016).

Cite as

Shai Ben-David. How Far Are We From Having a Satisfactory Theory of Clustering? (Invited Talk). In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{bendavid:LIPIcs.MFCS.2016.1,
  author =	{Ben-David, Shai},
  title =	{{How Far Are We From Having a Satisfactory Theory of Clustering?}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.1},
  URN =		{urn:nbn:de:0030-drops-65078},
  doi =		{10.4230/LIPIcs.MFCS.2016.1},
  annote =	{Keywords: clustering, theory, algorithm tuning, computational complexity}
}
Document
Invited Talk
Decidable Extensions of MSO (Invited Talk)

Authors: Mikolaj Bojanczyk

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
This is an overview of the invited talk delivered at the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016).

Cite as

Mikolaj Bojanczyk. Decidable Extensions of MSO (Invited Talk). In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{bojanczyk:LIPIcs.MFCS.2016.2,
  author =	{Bojanczyk, Mikolaj},
  title =	{{Decidable Extensions of MSO}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.2},
  URN =		{urn:nbn:de:0030-drops-65089},
  doi =		{10.4230/LIPIcs.MFCS.2016.2},
  annote =	{Keywords: monadic second-order logic, extensions, decidability, automata}
}
Document
Invited Talk
Optimal Reachability in Weighted Timed Automata and Games (Invited Talk)

Authors: Patricia Bouyer-Decitre

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
This is an overview of the invited talk delivered at the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016).

Cite as

Patricia Bouyer-Decitre. Optimal Reachability in Weighted Timed Automata and Games (Invited Talk). In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 3:1-3:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{bouyerdecitre:LIPIcs.MFCS.2016.3,
  author =	{Bouyer-Decitre, Patricia},
  title =	{{Optimal Reachability in Weighted Timed Automata and Games}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{3:1--3:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.3},
  URN =		{urn:nbn:de:0030-drops-65090},
  doi =		{10.4230/LIPIcs.MFCS.2016.3},
  annote =	{Keywords: timed automata, model-checking, optimization}
}
Document
Invited Talk
Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms (Invited Talk)

Authors: Tobias Friedrich

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
The node degrees of large real-world networks often follow a power-law distribution. Such scale-free networks can be social networks, internet topologies, the web graph, power grids, or many other networks from literally hundreds of domains. The talk will introduce several mathematical models of scale-free networks (e.g. preferential attachment graphs, Chung-Lu graphs, hyperbolic random graphs) and analyze some of their properties (e.g. diameter, average distance, clustering). We then present several algorithms and distributed processes on and for these network models (e.g. rumor spreading, load balancing, de-anonymization, embedding) and discuss a number of open problems. The talk assumes no prior knowledge about scale-free networks, distributed computing or hyperbolic geometry.

Cite as

Tobias Friedrich. Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms (Invited Talk). In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 4:1-4:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{friedrich:LIPIcs.MFCS.2016.4,
  author =	{Friedrich, Tobias},
  title =	{{Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{4:1--4:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.4},
  URN =		{urn:nbn:de:0030-drops-65106},
  doi =		{10.4230/LIPIcs.MFCS.2016.4},
  annote =	{Keywords: power-law graphs, scale-free graphs, random graphs, distributed algorithms}
}
Document
Invited Talk
RNA-Folding - From Hardness to Algorithms (Invited Talk)

Authors: Virginia Vassilevska Williams

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
This is an overview of the invited talk delivered at the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016).

Cite as

Virginia Vassilevska Williams. RNA-Folding - From Hardness to Algorithms (Invited Talk). In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{vassilevskawilliams:LIPIcs.MFCS.2016.5,
  author =	{Vassilevska Williams, Virginia},
  title =	{{RNA-Folding - From Hardness to Algorithms}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{5:1--5:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.5},
  URN =		{urn:nbn:de:0030-drops-65115},
  doi =		{10.4230/LIPIcs.MFCS.2016.5},
  annote =	{Keywords: RNA folding, matrix multiplication}
}
Document
Integer Factoring Using Small Algebraic Dependencies

Authors: Manindra Agrawal, Nitin Saxena, and Shubham Sahai Srivastava

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
Integer factoring is a curious number theory problem with wide applications in complexity and cryptography. The best known algorithm to factor a number n takes time, roughly, exp(2*log^{1/3}(n)*log^{2/3}(log(n))) (number field sieve, 1989). One basic idea used is to find two squares, possibly in a number field, that are congruent modulo n. Several variants of this idea have been utilized to get other factoring algorithms in the last century. In this work we intend to explore new ideas towards integer factoring. In particular, we adapt the AKS primality test (2004) ideas for integer factoring. In the motivating case of semiprimes n=pq, i.e. p<q are primes, we exploit the difference in the two Frobenius morphisms (one over F_p and the other over F_q) to factor n in special cases. Specifically, our algorithm is polynomial time (on number theoretic conjectures) if we know a small algebraic dependence between p,q. We discuss families of n where our algorithm is significantly faster than the algorithms based on known techniques.

Cite as

Manindra Agrawal, Nitin Saxena, and Shubham Sahai Srivastava. Integer Factoring Using Small Algebraic Dependencies. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.MFCS.2016.6,
  author =	{Agrawal, Manindra and Saxena, Nitin and Srivastava, Shubham Sahai},
  title =	{{Integer Factoring Using Small Algebraic Dependencies}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.6},
  URN =		{urn:nbn:de:0030-drops-64234},
  doi =		{10.4230/LIPIcs.MFCS.2016.6},
  annote =	{Keywords: integer, factorization, factoring integers, algebraic dependence, dependencies}
}
Document
Routing with Congestion in Acyclic Digraphs

Authors: Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
We study the version of the k-disjoint paths problem where k demand pairs (s_1,t_1), ..., (s_k,t_k) are specified in the input and the paths in the solution are allowed to intersect, but such that no vertex is on more than c paths. We show that on directed acyclic graphs the problem is solvable in time n^{O(d)} if we allow congestion k-d for k paths. Furthermore, we show that, under a suitable complexity theoretic assumption, the problem cannot be solved in time f(k)n^{o(d*log(d))} for any computable function f.

Cite as

Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with Congestion in Acyclic Digraphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{amiri_et_al:LIPIcs.MFCS.2016.7,
  author =	{Amiri, Saeed Akhoondian and Kreutzer, Stephan and Marx, D\'{a}niel and Rabinovich, Roman},
  title =	{{Routing with Congestion in Acyclic Digraphs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{7:1--7:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.7},
  URN =		{urn:nbn:de:0030-drops-64244},
  doi =		{10.4230/LIPIcs.MFCS.2016.7},
  annote =	{Keywords: algorithms, disjoint paths, congestion, acyclic digraphs, XP, W\lbrack1\rbrack-hard}
}
Document
Stochastic Timed Games Revisited

Authors: S. Akshay, Patricia Bouyer, Shankara Narayanan Krishna, Lakshmi Manasa, and Ashutosh Trivedi

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
Stochastic timed games (STGs), introduced by Bouyer and Forejt, naturally generalize both continuous-time Markov chains and timed automata by providing a partition of the locations between those controlled by two players (Player Box and Player Diamond) with competing objectives and those governed by stochastic laws. Depending on the number of players - 2, 1, or 0 - subclasses of stochastic timed games are often classified as 2 1/2-player, 1 1/2-player, and 1/2-player games where the 1/2 symbolizes the presence of the stochastic "nature" player. For STGs with reachability objectives it is known that 1 1/2-player one-clock STGs are decidable for qualitative objectives, and that 2 1/2-player three-clock STGs are undecidable for quantitative reachability objectives. This paper further refines the gap in this decidability spectrum. We show that quantitative reachability objectives are already undecidable for 1 1/2 player four-clock STGs, and even under the time-bounded restriction for 2 1/2-player five-clock STGs. We also obtain a class of 1 1/2, 2 1/2 player STGs for which the quantitative reachability problem is decidable.

Cite as

S. Akshay, Patricia Bouyer, Shankara Narayanan Krishna, Lakshmi Manasa, and Ashutosh Trivedi. Stochastic Timed Games Revisited. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{akshay_et_al:LIPIcs.MFCS.2016.8,
  author =	{Akshay, S. and Bouyer, Patricia and Krishna, Shankara Narayanan and Manasa, Lakshmi and Trivedi, Ashutosh},
  title =	{{Stochastic Timed Games Revisited}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.8},
  URN =		{urn:nbn:de:0030-drops-64985},
  doi =		{10.4230/LIPIcs.MFCS.2016.8},
  annote =	{Keywords: timed automata, stochastic games, two-counter machines}
}
Document
Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results

Authors: Georgios Amanatidis, Evangelos Markakis, and Krzysztof Sornat

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
We study a revenue maximization problem in the context of social networks. Namely, we consider a model introduced by Alon, Mansour, and Tennenholtz (EC 2013) that captures inequity aversion, i.e., prices offered to neighboring vertices should not be significantly different. We first provide approximation algorithms for a natural class of instances, referred to as the class of single-value revenue functions. Our results improve on the current state of the art, especially when the number of distinct prices is small. This applies, for example, to settings where the seller will only consider a fixed number of discount types or special offers. We then resolve one of the open questions posed in Alon et al., by establishing APX-hardness for the problem. Surprisingly, we further show that the problem is NP-complete even when the price differences are allowed to be relatively large. Finally, we also provide some extensions of the model of Alon et al., regarding the allowed set of prices.

Cite as

Georgios Amanatidis, Evangelos Markakis, and Krzysztof Sornat. Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{amanatidis_et_al:LIPIcs.MFCS.2016.9,
  author =	{Amanatidis, Georgios and Markakis, Evangelos and Sornat, Krzysztof},
  title =	{{Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.9},
  URN =		{urn:nbn:de:0030-drops-64254},
  doi =		{10.4230/LIPIcs.MFCS.2016.9},
  annote =	{Keywords: inequity aversion, social networks, revenue maximization}
}
Document
Trading Determinism for Time in Space Bounded Computations

Authors: Vivek Anand T Kallampally and Raghunath Tewari

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
Savitch showed in 1970 that nondeterministic logspace (NL) is contained in deterministic O(log^2(n)) space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open. In this paper we give a partial solution to this problem and show that for every language in NL there exists an unambiguous nondeterministic algorithm that requires O(log^2(n)) space and simultaneously runs in polynomial time.

Cite as

Vivek Anand T Kallampally and Raghunath Tewari. Trading Determinism for Time in Space Bounded Computations. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{kallampally_et_al:LIPIcs.MFCS.2016.10,
  author =	{Kallampally, Vivek Anand T and Tewari, Raghunath},
  title =	{{Trading Determinism for Time in Space Bounded Computations}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.10},
  URN =		{urn:nbn:de:0030-drops-64268},
  doi =		{10.4230/LIPIcs.MFCS.2016.10},
  annote =	{Keywords: space complexity, unambiguous computations, Savitch's Theorem}
}
Document
Families of DFAs as Acceptors of omega-Regular Languages

Authors: Dana Angluin, Udi Boker, and Dana Fisman

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
Families of DFAs (FDFAs) provide an alternative formalism for recognizing omega-regular languages. The motivation for introducing them was a desired correlation between the automaton states and right congruence relations, in a manner similar to the Myhill-Nerode theorem for regular languages. This correlation is beneficial for learning algorithms, and indeed it was recently shown that omega-regular languages can be learned from membership and equivalence queries, using FDFAs as the acceptors. In this paper, we look into the question of how suitable FDFAs are for defining omega-regular languages. Specifically, we look into the complexity of performing Boolean operations, such as complementation and intersection, on FDFAs, the complexity of solving decision problems, such as emptiness and language containment, and the succinctness of FDFAs compared to standard deterministic and nondeterministic omega-automata. We show that FDFAs enjoy the benefits of deterministic automata with respect to Boolean operations and decision problems. Namely, they can all be performed in nondeterministic logarithmic space. We provide polynomial translations of deterministic Buchi and coBuchi automata to FDFAs and of FDFAs to nondeterministic Buchi automata (NBAs). We show that translation of an NBA to an FDFA may involve an exponential blowup. Last, we show that FDFAs are more succinct than deterministic parity automata (DPAs) in the sense that translating a DPA to an FDFA can always be done with only a polynomial increase, yet the other direction involves an inevitable exponential blowup in the worst case.

Cite as

Dana Angluin, Udi Boker, and Dana Fisman. Families of DFAs as Acceptors of omega-Regular Languages. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{angluin_et_al:LIPIcs.MFCS.2016.11,
  author =	{Angluin, Dana and Boker, Udi and Fisman, Dana},
  title =	{{Families of DFAs as Acceptors of omega-Regular Languages}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.11},
  URN =		{urn:nbn:de:0030-drops-64274},
  doi =		{10.4230/LIPIcs.MFCS.2016.11},
  annote =	{Keywords: finite automata, omega regular languages}
}
  • Refine by Author
  • 3 Bannai, Hideo
  • 3 Faliszewski, Piotr
  • 3 Ganian, Robert
  • 3 Inenaga, Shunsuke
  • 3 Takeda, Masayuki
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 7 computational complexity
  • 4 complexity
  • 3 automata
  • 3 circuit complexity
  • 3 lower bounds
  • Show More...

  • Refine by Type
  • 92 document
  • 1 volume

  • Refine by Publication Year
  • 92 2016
  • 1 2017

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