|
Cristina Bazgan
Cristina Bazgan is a French computer scientist who studies combinatorial optimization and graph theory problems from the points of view of parameterized complexity, fine-grained complexity, approximation algorithms, and regret. Bazgan earned her Ph.D. in 1998 from the University of Paris-Sud. Her dissertation, ''Approximation de problèmes d'optimisation et de fonctions totales de NP'', was supervised by Miklos Santha. She is a professor at Paris Dauphine University, associated with Lamsade, the Laboratory for Analysis and Modeling Systems for Decision Support. Bazgan became a junior member of the Institut Universitaire de France The Institut Universitaire de France (IUF, Academic Institute of France), is a service of the French Ministry of Higher Education that distinguishes each year a small number of university professors for their research excellence, as evidenced by t ... in 2011. References External linksHome page French women computer scientists Theoretical comp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Combinatorial Optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead. Combinatorial optimization is related to operations research, algorithm theory, and computational complexity theory. It has important applications in several fields, including artificial intelligence, machine learning, auction theory, software engineering, VLSI, applied mathematics and theoretical computer science. Some research literature considers discrete o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are connected by '' edges'' (also called ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a set of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Parameterized Complexity
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. The first systematic work on parameterized complexity was done by . Under the assumption that P ≠ NP, there exist many natural problems that require superpolynomial running time when complexity is measured in terms of the input size only, but that are computable in a time that is polynomial in the input size and exponential or worse in a parameter . Hence, if is fixed at a small value and the growth of the function over is relatively small then such p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fine-grained Reduction
In computational complexity theory, a fine-grained reduction is a transformation from one computational problem to another, used to relate the difficulty of improving the time bounds for the two problems. Intuitively, it provides a method for solving one problem efficiently by using the solution to the other problem as a subroutine. If problem A can be solved in time a(n) and problem B can be solved in time b(n), then the existence of an (a,b)-reduction from problem A to problem B implies that any significant speedup for problem B would also lead to a speedup for problem A. Definition Let A and B be computational problems, specified as the desired output for each possible input. Let a and b both be time-constructible functions that take an integer argument n and produce an integer result. Usually, a and b are the time bounds for known or naive algorithms for the two problems, and often they are monomials such as n^2. Then A is said to be (a,b)-reducible to B if, for every real numb ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Approximation Algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Regret (decision Theory)
In decision theory, on making decisions under uncertainty—should information about the best course of action arrive ''after'' taking a fixed decision—the human emotional response of regret is often experienced, and can be measured as the value of difference between a made decision and the optimal decision. The theory of regret aversion or anticipated regret proposes that when facing a decision, individuals might ''anticipate'' regret and thus incorporate in their choice their desire to eliminate or reduce this possibility. Regret is a negative emotion with a powerful social and reputational component, and is central to how humans learn from experience and to the human psychology of risk aversion. Conscious anticipation of regret creates a feedback loop that transcends regret from the emotional realm—often modeled as mere human behavior—into the realm of the rational choice behavior that is modeled in decision theory. Description Regret theory is a model in theoretical eco ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
University Of Paris-Sud
Paris-Sud University (French: ''Université Paris-Sud''), also known as University of Paris — XI (or as Université d'Orsay before 1971), was a French research university distributed among several campuses in the southern suburbs of Paris, including Orsay, Cachan, Châtenay-Malabry, Sceaux, and Kremlin-Bicêtre campuses. The main campus was located in Orsay. Starting from 2020, University Paris Sud has been replaced by the University of Paris-Saclay in The League of European Research Universities (LERU). Paris-Sud was one of the largest and most prestigious universities in France, particularly in science and mathematics. The university was ranked 1st in France, 9th in Europe and 37th worldwide by 2019 Academic Ranking of World Universities (ARWU) in particular it was ranked as 1st in Europe for physics and 2nd in Europe for mathematics. Five Fields Medalists and two Nobel Prize Winners have been affiliated to the university. On 16 January 2019, Alain Sarfati was electe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Paris Dauphine University
Paris Dauphine University - PSL (french: Université Paris-Dauphine, also known as Paris Dauphine - PSL or Dauphine - PSL) is a public research university based in Paris, France. It is one of the 13 universities formed by the division of the ancient University of Paris (metonymically known as the Sorbonne). It is the only French institution of higher education that is both a grande école and a university. Dauphine is also a founding member and constituent college of PSL University. Dauphine is renowned for its teaching in finance, economics, mathematics, law, and business strategy. Dauphine is a selective university with the status of ''grand établissement''; this unique legal status within the French higher education system allows Dauphine to be a selective university. On average, 90 to 95% of accepted students received either high distinctions or the highest distinctions at their French High School National Exam results (Examen National du Baccalauréat). Dauphine is also a f ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Institut Universitaire De France
The Institut Universitaire de France (IUF, Academic Institute of France), is a service of the French Ministry of Higher Education that distinguishes each year a small number of university professors for their research excellence, as evidenced by their international recognition. It was created to become a new "Collège de France", located in French universities. Only 2% of French university professors have been currently distinguished by the Institut Universitaire de France. Organization The Institute was created by decree on 26 of August, 1991. It is an organization without walls, whose members remain in their own universities. At least two thirds of the members of the IUF belong to universities outside Paris. The purpose of the IUF is to give full freedom to its members to pursue and disseminate their research. About 2% of total French faculties are members (active or honorary) of the IUF. Each year a symposium brings together members of the IUF in order to allow exchanges at the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
French Women Computer Scientists
French (french: français(e), link=no) may refer to: * Something of, from, or related to France ** French language, which originated in France, and its various dialects and accents ** French people, a nation and ethnic group identified with France ** French cuisine, cooking traditions and practices Fortnite French places Arts and media * The French (band), a British rock band * French (episode), "French" (episode), a live-action episode of ''The Super Mario Bros. Super Show!'' * Française (film), ''Française'' (film), 2008 * French Stewart (born 1964), American actor Other uses * French (surname), a surname (including a list of people with the name) * French (tunic), a particular type of military jacket or tunic used in the Russian Empire and Soviet Union * French's, an American brand of mustard condiment * French catheter scale, a unit of measurement of diameter * French Defence, a chess opening * French kiss, a type of kiss involving the tongue See also * France (disam ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Scientists
A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may be scientific, belong to a non-scientific discipline, or no discipline at all. Depending on the context, a theory's assertions might, for example, include generalized explanations of how nature works. The word has its roots in ancient Greek, but in modern use it has taken on several related meanings. In modern science, the term "theory" refers to scientific theories, a well-confirmed type of explanation of nature, made in a way consistent with the scientific method, and fulfilling the criteria required by modern science. Such theories are described in such a way that scientific tests should be able to provide empirical support for it, or empirical contradiction ("falsify") of it. Scientific theories are the most reliable, rigorous, and compr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
