8 Search Results for "Fotakis, Dimitris"

Document
DOI: 10.4230/LIPIcs.MFCS.2023.47
Graph Connectivity with Noisy Queries

Authors: Dimitris Fotakis, Evangelia Gergatsouli, Charilaos Pipis, Miltiadis Stouras, and Christos Tzamos

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Graph connectivity is a fundamental combinatorial optimization problem that arises in many practical applications, where usually a spanning subgraph of a network is used for its operation. However, in the real world, links may fail unexpectedly deeming the networks non-operational, while checking whether a link is damaged is costly and possibly erroneous. After an event that has damaged an arbitrary subset of the edges, the network operator must find a spanning tree of the network using non-damaged edges by making as few checks as possible. Motivated by such questions, we study the problem of finding a spanning tree in a network, when we only have access to noisy queries of the form "Does edge e exist?". We design efficient algorithms, even when edges fail adversarially, for all possible error regimes; 2-sided error (where any answer might be erroneous), false positives (where "no" answers are always correct) and false negatives (where "yes" answers are always correct). In the first two regimes we provide efficient algorithms and give matching lower bounds for general graphs. In the False Negative case we design efficient algorithms for large interesting families of graphs (e.g. bounded treewidth, sparse). Using the previous results, we provide tight algorithms for the practically useful family of planar graphs in all error regimes.
Cite as

Dimitris Fotakis, Evangelia Gergatsouli, Charilaos Pipis, Miltiadis Stouras, and Christos Tzamos. Graph Connectivity with Noisy Queries. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fotakis_et_al:LIPIcs.MFCS.2023.47,
  author =	{Fotakis, Dimitris and Gergatsouli, Evangelia and Pipis, Charilaos and Stouras, Miltiadis and Tzamos, Christos},
  title =	{{Graph Connectivity with Noisy Queries}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.47},
  URN =		{urn:nbn:de:0030-drops-185810},
  doi =		{10.4230/LIPIcs.MFCS.2023.47},
  annote =	{Keywords: algorithms under uncertainty, graph connectivity, spanning tree, noisy queries, online algorithms, stochastic optimization}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.65
On the Approximability of Multistage Min-Sum Set Cover

Authors: Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, and Stratis Skoulakis

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We investigate the polynomial-time approximability of the multistage version of Min-Sum Set Cover (Mult-MSSC), a natural and intriguing generalization of the classical List Update problem. In Mult-MSSC, we maintain a sequence of permutations (π⁰, π¹, …, π^T) on n elements, based on a sequence of requests ℛ = (R¹, …, R^T). We aim to minimize the total cost of updating π^{t-1} to π^{t}, quantified by the Kendall tau distance d_{KT}(π^{t-1}, π^t), plus the total cost of covering each request R^t with the current permutation π^t, quantified by the position of the first element of R^t in π^t. Using a reduction from Set Cover, we show that Mult-MSSC does not admit an O(1)-approximation, unless P = NP, and that any o(log n) (resp. o(r)) approximation to Mult-MSSC implies a sublogarithmic (resp. o(r)) approximation to Set Cover (resp. where each element appears at most r times). Our main technical contribution is to show that Mult-MSSC can be approximated in polynomial-time within a factor of O(log² n) in general instances, by randomized rounding, and within a factor of O(r²), if all requests have cardinality at most r, by deterministic rounding.
Cite as

Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, and Stratis Skoulakis. On the Approximability of Multistage Min-Sum Set Cover. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 65:1-65:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fotakis_et_al:LIPIcs.ICALP.2021.65,
  author =	{Fotakis, Dimitris and Kostopanagiotis, Panagiotis and Nakos, Vasileios and Piliouras, Georgios and Skoulakis, Stratis},
  title =	{{On the Approximability of Multistage Min-Sum Set Cover}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{65:1--65:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela 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.ICALP.2021.65},
  URN =		{urn:nbn:de:0030-drops-141341},
  doi =		{10.4230/LIPIcs.ICALP.2021.65},
  annote =	{Keywords: Approximation Algorithms, Multistage Min-Sum Set Cover, Multistage Optimization Problems}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.50
Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games

Authors: Dimitris Fotakis, Vardis Kandiros, Thanasis Lianeas, Nikos Mouzakis, Panagiotis Patsilinakos, and Stratis Skoulakis

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In this work, we seek a more refined understanding of the complexity of local optimum computation for Max-Cut and pure Nash equilibrium (PNE) computation for congestion games with weighted players and linear latency functions. We show that computing a PNE of linear weighted congestion games is PLS-complete either for very restricted strategy spaces, namely when player strategies are paths on a series-parallel network with a single origin and destination, or for very restricted latency functions, namely when the latency on each resource is equal to the congestion. Our results reveal a remarkable gap regarding the complexity of PNE in congestion games with weighted and unweighted players, since in case of unweighted players, a PNE can be easily computed by either a simple greedy algorithm (for series-parallel networks) or any better response dynamics (when the latency is equal to the congestion). For the latter of the results above, we need to show first that computing a local optimum of a natural restriction of Max-Cut, which we call Node-Max-Cut, is PLS-complete. In Node-Max-Cut, the input graph is vertex-weighted and the weight of each edge is equal to the product of the weights of its endpoints. Due to the very restricted nature of Node-Max-Cut, the reduction requires a careful combination of new gadgets with ideas and techniques from previous work. We also show how to compute efficiently a (1+ε)-approximate equilibrium for Node-Max-Cut, if the number of different vertex weights is constant.
Cite as

Dimitris Fotakis, Vardis Kandiros, Thanasis Lianeas, Nikos Mouzakis, Panagiotis Patsilinakos, and Stratis Skoulakis. Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fotakis_et_al:LIPIcs.ICALP.2020.50,
  author =	{Fotakis, Dimitris and Kandiros, Vardis and Lianeas, Thanasis and Mouzakis, Nikos and Patsilinakos, Panagiotis and Skoulakis, Stratis},
  title =	{{Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{50:1--50:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.50},
  URN =		{urn:nbn:de:0030-drops-124573},
  doi =		{10.4230/LIPIcs.ICALP.2020.50},
  annote =	{Keywords: PLS-completeness, Local-Max-Cut, Weighted Congestion Games, Equilibrium Computation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.51
The Online Min-Sum Set Cover Problem

Authors: Dimitris Fotakis, Loukas Kavouras, Grigorios Koumoutsos, Stratis Skoulakis, and Manolis Vardas

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We consider the online Min-Sum Set Cover (MSSC), a natural and intriguing generalization of the classical list update problem. In Online MSSC, the algorithm maintains a permutation on n elements based on subsets S₁, S₂, … arriving online. The algorithm serves each set S_t upon arrival, using its current permutation π_t, incurring an access cost equal to the position of the first element of S_t in π_t. Then, the algorithm may update its permutation to π_{t+1}, incurring a moving cost equal to the Kendall tau distance of π_t to π_{t+1}. The objective is to minimize the total access and moving cost for serving the entire sequence. We consider the r-uniform version, where each S_t has cardinality r. List update is the special case where r = 1. We obtain tight bounds on the competitive ratio of deterministic online algorithms for MSSC against a static adversary, that serves the entire sequence by a single permutation. First, we show a lower bound of (r+1)(1-r/(n+1)) on the competitive ratio. Then, we consider several natural generalizations of successful list update algorithms and show that they fail to achieve any interesting competitive guarantee. On the positive side, we obtain a O(r)-competitive deterministic algorithm using ideas from online learning and the multiplicative weight updates (MWU) algorithm. Furthermore, we consider efficient algorithms. We propose a memoryless online algorithm, called Move-All-Equally, which is inspired by the Double Coverage algorithm for the k-server problem. We show that its competitive ratio is Ω(r²) and 2^{O(√{log n ⋅ log r})}, and conjecture that it is f(r)-competitive. We also compare Move-All-Equally against the dynamic optimal solution and obtain (almost) tight bounds by showing that it is Ω(r √n) and O(r^{3/2} √n)-competitive.
Cite as

Dimitris Fotakis, Loukas Kavouras, Grigorios Koumoutsos, Stratis Skoulakis, and Manolis Vardas. The Online Min-Sum Set Cover Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fotakis_et_al:LIPIcs.ICALP.2020.51,
  author =	{Fotakis, Dimitris and Kavouras, Loukas and Koumoutsos, Grigorios and Skoulakis, Stratis and Vardas, Manolis},
  title =	{{The Online Min-Sum Set Cover Problem}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{51:1--51:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.51},
  URN =		{urn:nbn:de:0030-drops-124582},
  doi =		{10.4230/LIPIcs.ICALP.2020.51},
  annote =	{Keywords: Online Algorithms, Competitive Analysis, Min-Sum Set Cover}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.17
Malleable Scheduling Beyond Identical Machines

Authors: Dimitris Fotakis, Jannik Matuschke, and Orestis Papadigenopoulos

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
In malleable job scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. Jobs are required to be executed non-preemptively and in unison, in the sense that they occupy, during their execution, the same time interval over all the machines of the allocated set. In this work, we study generalizations of malleable job scheduling inspired by standard scheduling on unrelated machines. Specifically, we introduce a general model of malleable job scheduling, where each machine has a (possibly different) speed for each job, and the processing time of a job j on a set of allocated machines S depends on the total speed of S for j. For machines with unrelated speeds, we show that the optimal makespan cannot be approximated within a factor less than e/(e-1), unless P = NP. On the positive side, we present polynomial-time algorithms with approximation ratios 2e/(e-1) for machines with unrelated speeds, 3 for machines with uniform speeds, and 7/3 for restricted assignments on identical machines. Our algorithms are based on deterministic LP rounding and result in sparse schedules, in the sense that each machine shares at most one job with other machines. We also prove lower bounds on the integrality gap of 1+phi for unrelated speeds (phi is the golden ratio) and 2 for uniform speeds and restricted assignments. To indicate the generality of our approach, we show that it also yields constant factor approximation algorithms (i) for minimizing the sum of weighted completion times; and (ii) a variant where we determine the effective speed of a set of allocated machines based on the L_p norm of their speeds.
Cite as

Dimitris Fotakis, Jannik Matuschke, and Orestis Papadigenopoulos. Malleable Scheduling Beyond Identical Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fotakis_et_al:LIPIcs.APPROX-RANDOM.2019.17,
  author =	{Fotakis, Dimitris and Matuschke, Jannik and Papadigenopoulos, Orestis},
  title =	{{Malleable Scheduling Beyond Identical Machines}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.17},
  URN =		{urn:nbn:de:0030-drops-112324},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.17},
  annote =	{Keywords: malleable, jobs, moldable, machines, unrelated, uniform, parallel, speeds, approximation, scheduling}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.73
Covering Clients with Types and Budgets

Authors: Dimitris Fotakis, Laurent Gourvès, Claire Mathieu, and Abhinav Srivastav

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

Abstract
In this paper, we consider a variant of the facility location problem. Imagine the scenario where facilities are categorized into multiple types such as schools, hospitals, post offices, etc. and the cost of connecting a client to a facility is realized by the distance between them. Each client has a total budget on the distance she/he is willing to travel. The goal is to open the minimum number of facilities such that the aggregate distance of each client to multiple types is within her/his budget. This problem closely resembles to the set cover and r-domination problems. Here, we study this problem in different settings. Specifically, we present some positive and negative results in the general setting, where no assumption is made on the distance values. Then we show that better results can be achieved when clients and facilities lie in a metric space.
Cite as

Dimitris Fotakis, Laurent Gourvès, Claire Mathieu, and Abhinav Srivastav. Covering Clients with Types and Budgets. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 73:1-73:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fotakis_et_al:LIPIcs.ISAAC.2018.73,
  author =	{Fotakis, Dimitris and Gourv\`{e}s, Laurent and Mathieu, Claire and Srivastav, Abhinav},
  title =	{{Covering Clients with Types and Budgets}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{73:1--73:12},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.73},
  URN =		{urn:nbn:de:0030-drops-100213},
  doi =		{10.4230/LIPIcs.ISAAC.2018.73},
  annote =	{Keywords: Facility Location, Geometric Set Cover, Local Search}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.149
On the Size and the Approximability of Minimum Temporally Connected Subgraphs

Authors: Kyriakos Axiotis and Dimitris Fotakis

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We consider temporal graphs with discrete time labels and investigate the size and the approximability of minimum temporally connected spanning subgraphs. We present a family of minimally connected temporal graphs with n vertices and Omega(n^2) edges, thus resolving an open question of (Kempe, Kleinberg, Kumar, JCSS 64, 2002) about the existence of sparse temporal connectivity certificates. Next, we consider the problem of computing a minimum weight subset of temporal edges that preserve connectivity of a given temporal graph either from a given vertex r (r-MTC problem) or among all vertex pairs (MTC problem). We show that the approximability of r-MTC is closely related to the approximability of Directed Steiner Tree and that r-MTC can be solved in polynomial time if the underlying graph has bounded treewidth. We also show that the best approximation ratio for MTC is at least O(2^{log^{1-epsilon}(n)} and at most O(min{n^{1+epsilon},(Delta*M)^{2/3+epsilon}), for any constant epsilon > 0, where M is the number of temporal edges and Delta is the maximum degree of the underlying graph. Furthermore, we prove that the unweighted version of MTC is APX-hard and that MTC is efficiently solvable in trees and 2-approximable in cycles.
Cite as

Kyriakos Axiotis and Dimitris Fotakis. On the Size and the Approximability of Minimum Temporally Connected Subgraphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 149:1-149:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{axiotis_et_al:LIPIcs.ICALP.2016.149,
  author =	{Axiotis, Kyriakos and Fotakis, Dimitris},
  title =	{{On the Size and the Approximability of Minimum Temporally Connected Subgraphs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{149:1--149:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.149},
  URN =		{urn:nbn:de:0030-drops-62936},
  doi =		{10.4230/LIPIcs.ICALP.2016.149},
  annote =	{Keywords: Temporal Graphs, Temporal Connectivity, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.37
Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse

Authors: Dimitris Fotakis, Michael Lampis, and Vangelis Th. Paschos

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
It has long been known, since the classical work of (Arora, Karger, Karpinski, JCSS'99), that MAX-CUT admits a PTAS on dense graphs, and more generally, MAX-k-CSP admits a PTAS on "dense" instances with Omega(n^k) constraints. In this paper we extend and generalize their exhaustive sampling approach, presenting a framework for (1-epsilon)-approximating any MAX-k-CSP problem in sub-exponential time while significantly relaxing the denseness requirement on the input instance. Specifically, we prove that for any constants delta in (0, 1] and epsilon > 0, we can approximate MAX-k-CSP problems with Omega(n^{k-1+delta}) constraints within a factor of (1-epsilon) in time 2^{O(n^{1-delta}*ln(n) / epsilon^3)}. The framework is quite general and includes classical optimization problems, such as MAX-CUT, MAX-DICUT, MAX-k-SAT, and (with a slight extension) k-DENSEST SUBGRAPH, as special cases. For MAX-CUT in particular (where k=2), it gives an approximation scheme that runs in time sub-exponential in n even for "almost-sparse" instances (graphs with n^{1+delta} edges). We prove that our results are essentially best possible, assuming the ETH. First, the density requirement cannot be relaxed further: there exists a constant r < 1 such that for all delta > 0, MAX-k-SAT instances with O(n^{k-1}) clauses cannot be approximated within a ratio better than r in time 2^{O(n^{1-delta})}. Second, the running time of our algorithm is almost tight for all densities. Even for MAX-CUT there exists r<1 such that for all delta' > delta >0, MAX-CUT instances with n^{1+delta} edges cannot be approximated within a ratio better than r in time 2^{n^{1-delta'}}.
Cite as

Dimitris Fotakis, Michael Lampis, and Vangelis Th. Paschos. Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fotakis_et_al:LIPIcs.STACS.2016.37,
  author =	{Fotakis, Dimitris and Lampis, Michael and Paschos, Vangelis Th.},
  title =	{{Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.37},
  URN =		{urn:nbn:de:0030-drops-57388},
  doi =		{10.4230/LIPIcs.STACS.2016.37},
  annote =	{Keywords: polynomial and subexponential approximation, sampling, randomized rounding}
}
  • Refine by Author
  • 8 Fotakis, Dimitris
  • 3 Skoulakis, Stratis
  • 1 Axiotis, Kyriakos
  • 1 Gergatsouli, Evangelia
  • 1 Gourvès, Laurent
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Exact and approximate computation of equilibria
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → Online algorithms
  • Show More...

  • Refine by Keyword
  • 2 Approximation Algorithms
  • 1 Competitive Analysis
  • 1 Equilibrium Computation
  • 1 Facility Location
  • 1 Geometric Set Cover
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 2016
  • 2 2020
  • 1 2018
  • 1 2019
  • 1 2021
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact