3 Search Results for "Cosnard, Michel"

Document

DOI: 10.4230/LIPIcs.SEA.2024.28

Finding the Minimum Cost Acceptable Element in a Sorted Matrix

Authors: Sebastián Urrutia and Vinicius dos Santos

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract

In this work we introduce the problem of finding a minimum cost acceptable element in an n × n matrix M whose columns and rows are sorted in non-decreasing order. More precisely, given a sorted matrix M and access to a given oracle function f: ℕ × ℕ → {True, False}, one has to find a pair (i, j) of indices such that f(i,j) returns True and the value M[i,j] is as small as possible. Assuming the computation of f(i,j) takes time bounded by a constant, a naive algorithm scanning all the positions of the matrix takes time O(n²). Another natural approach, based on a priority queue, takes time O(z log z) in which z stands for the position of the first pair of indices for which the oracle returns True in a sorted list of all elements of M. In the worst case, when z = n², the naive algorithm is better than the priority queue one. In this work we introduce different algorithms with complexities depending on n and z, such as O(n √z) and O(min(n²,z²)), and compare them, both theoretically and experimentally, in terms of running time and number of calls to the oracle. Among other things, we find that in most cases our algorithms do not make a significantly larger number of calls to the oracle than the priority queue-based algorithm, which achieves the minimum of such call when all elements of the matrix are distinct, while being much faster in large instances.

Cite as

Sebastián Urrutia and Vinicius dos Santos. Finding the Minimum Cost Acceptable Element in a Sorted Matrix. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{urrutia_et_al:LIPIcs.SEA.2024.28,
  author =	{Urrutia, Sebasti\'{a}n and dos Santos, Vinicius},
  title =	{{Finding the Minimum Cost Acceptable Element in a Sorted Matrix}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.28},
  URN =		{urn:nbn:de:0030-drops-203939},
  doi =		{10.4230/LIPIcs.SEA.2024.28},
  annote =	{Keywords: Search, Sorted matrix, Oracle function, Algorithm complexity}
}

Document

DOI: 10.4230/LIPIcs.FUN.2022.12

Grabbing Olives on Linear Pizzas and Pissaladières

Authors: Jean-Claude Bermond, Frédéric Havet, and Michel Cosnard

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract

In this paper we revisit the problem entitled Sharing a Pizza stated by P. Winkler by considering a new puzzle called Sharing a Pissaladiere. The game is played by two polite coatis Alice and Bob who share a pissaladière (a p×q grid) which is divided into rectangular slices. Alice starts in a corner and then the coatis alternate removing a remaining slice adjacent to at most two other slices. On some slices there are precious olives of Nice and the aim of each coati is to grab the maximum number of olives. We first study the particular case of 1×n grid (i.e. a path) where the game is a graph grabbing game known as Sharing a linear pizza. In that case each player can take only an end vertex of the remaining path. These problems are particular cases of a new class of games called d-degenerate games played on a graph with non negative weights assigned to the vertices with the rule that coatis alternatively take a vertex of degree at most d. Our main results are the following. We give optimal strategies for paths (linear pizzas) with no two adjacent weighty vertices. We also give a recurrence formula to compute the gains which depend only on the parity of n and of the respective parities of weighty vertices with a complexity in O(h²) where h denotes the number of parity changes in the weighty vertices. When the weights are only {0,1} we reduce the computation of the average number of olives collected by each player to a word counting problem. We solve Sharing a pissaladière with {0,1} weights, when there is one olive or 2 olives. In that case Alice (resp. Bob) grabs almost all the olives if the number of vertices of the grid n = p×q is odd (resp. even). We prove that for a 2×q grid with a fixed number k of olives Bob grabs at least ⌈(k-1)/3⌉ olives and almost always grabs all the k olives.

Cite as

Jean-Claude Bermond, Frédéric Havet, and Michel Cosnard. Grabbing Olives on Linear Pizzas and Pissaladières. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bermond_et_al:LIPIcs.FUN.2022.12,
  author =	{Bermond, Jean-Claude and Havet, Fr\'{e}d\'{e}ric and Cosnard, Michel},
  title =	{{Grabbing Olives on Linear Pizzas and Pissaladi\`{e}res}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.12},
  URN =		{urn:nbn:de:0030-drops-159826},
  doi =		{10.4230/LIPIcs.FUN.2022.12},
  annote =	{Keywords: Grabbing game, degenerate graph, path, grid}
}

Document

DOI: 10.4230/DagSemProc.04451.1

04451 Abstracts Collection – Future Generation Grids

Authors: Michel Cosnard, Vladimir Getov, Domenico Laforenza, and Alexander Reinefeld

Published in: Dagstuhl Seminar Proceedings, Volume 4451, Future Generation Grids (2005)

Abstract

The Dagstuhl Seminar 04451 "Future Generation Grid" was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl from 1st to 5th November 2004. The focus of the seminar was on open problems and future challenges in the design of next generation Grid systems. A total of 45 participants presented their current projects, research plans, and new ideas in the area of Grid technologies. Several evening sessions with vivid discussions on future trends complemented the talks. This report gives an overview of the background and the findings of the seminar.

Cite as

Michel Cosnard, Vladimir Getov, Domenico Laforenza, and Alexander Reinefeld. 04451 Abstracts Collection – Future Generation Grids. In Future Generation Grids. Dagstuhl Seminar Proceedings, Volume 4451, pp. 1-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{cosnard_et_al:DagSemProc.04451.1,
  author =	{Cosnard, Michel and Getov, Vladimir and Laforenza, Domenico and Reinefeld, Alexander},
  title =	{{04451 Abstracts Collection – Future Generation Grids}},
  booktitle =	{Future Generation Grids},
  pages =	{1--34},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4451},
  editor =	{Michel Cosnard and Vladimir Getov and Domenico Laforenza and Alexander},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04451.1},
  URN =		{urn:nbn:de:0030-drops-264},
  doi =		{10.4230/DagSemProc.04451.1},
  annote =	{Keywords: Grid Architectures , Autonomous Computing , Knowledge Grid , Peer-to-Peer , WSRF , OGSI , SOA}
}

Refine by Author
2 Cosnard, Michel
1 Bermond, Jean-Claude
1 Getov, Vladimir
1 Havet, Frédéric
1 Laforenza, Domenico
Show More...

Refine by Classification
1 Mathematics of computing → Graph algorithms
1 Theory of computation → Design and analysis of algorithms

Refine by Keyword
1 Algorithm complexity
1 Autonomous Computing
1 Grabbing game
1 Grid Architectures
1 Knowledge Grid
Show More...

Refine by Type
3 document

Refine by Publication Year
1 2005
1 2022
1 2024