Related Research Articles
The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, splitting a network prefix into multiple subnets, and technology mapping in FPGA semiconductor chip design.
In computational complexity theory, the unique games conjecture is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate value of a certain type of game, known as a unique game, has NP-hard computational complexity. It has broad applications in the theory of hardness of approximation. If the unique games conjecture is true and P ≠ NP, then for many important problems it is not only impossible to get an exact solution in polynomial time, but also impossible to get a good polynomial-time approximation. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines.
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity.
Reichman University is Israel's only private university, located in Herzliya, Tel Aviv District. It was founded in 1994 as the IDC Herzliya private college, before being rebranded in 2021.
Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.
Ilan Sadeh is an Israeli IT theoretician, entrepreneur, and human rights activist. He holds the position of Associate Professor of Computer Sciences and Mathematics at the University for Information Science and Technology "St. Paul The Apostle" in Ohrid, North Macedonia.
Truthful job scheduling is a mechanism design variant of the job shop scheduling problem from operations research.
Julia Chuzhoy is an Israeli mathematician and computer scientist at the Toyota Technological Institute at Chicago, known for her research on approximation algorithms and graph theory.
In graph theory, a sum coloring of a graph is a labeling of its vertices by positive integers, with no two adjacent vertices having equal labels, that minimizes the sum of the labels. The minimum sum that can be achieved is called the chromatic sum of the graph. Chromatic sums and sum coloring were introduced by Supowit in 1987 using non-graph-theoretic terminology, and first studied in graph theoretic terms by Ewa Kubicka in her 1989 doctoral thesis.
Oded Regev is an Israeli-American theoretical computer scientist and mathematician. He is a professor of computer science at the Courant institute at New York University. He is best known for his work in lattice-based cryptography, and in particular for introducing the learning with errors problem.
Envy-free pricing is a kind of fair item allocation. There is a single seller that owns some items, and a set of buyers who are interested in these items. The buyers have different valuations to the items, and they have a quasilinear utility function; this means that the utility an agent gains from a bundle of items equals the agent's value for the bundle minus the total price of items in the bundle. The seller should determine a price for each item, and sell the items to some of the buyers, such that there is no envy. Two kinds of envy are considered:
In economics, a budget-additive valuation is a kind of a utility function. It corresponds to a person that, when given a set of items, evaluates them in the following way:
Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.
Baruch M. Schieber is a Professor of the Department of Computer Science at the New Jersey Institute of Technology (NJIT) and Director of the Institute for Future Technologies.
Ariel Shamir is an Israeli professor of Computer Science.
In computational economics, a single-minded agent is an agent who wants only a very specific combination of items. The valuation function of such an agent assigns a positive value only to a specific set of items, and to all sets that contain it. It assigns a zero value to all other sets. A single-minded agent regards the set of items he wants as purely complementary goods.
Anat Bremler-Barr, is an Israeli computer scientist. She is a professor at Tel Aviv University who is known for her contributions in network security, specifically in Denial of Service attacks and scalable protection of Internet of Things (IoT) devices.
Philip N. Klein is an American computer scientist and professor at Brown University. His research focuses on algorithms for optimization problems in graphs.
Hadas Shachnai is an Israeli computer scientist specializing in combinatorial optimization, including knapsack problems, interval scheduling, and the optimization of submodular set functions. She is a professor of computer science at the Technion – Israel Institute of Technology, and co-editor-in-chief of Discrete Mathematics & Theoretical Computer Science.
Fractional job scheduling is a variant of optimal job scheduling in which it is allowed to break jobs into parts and process each part separately on the same or a different machine. Breaking jobs into parts may allow for improving the overall performance, for example, decreasing the makespan. Moreover, the computational problem of finding an optimal schedule may become easier, as some of the optimization variables become continuous. On the other hand, breaking jobs apart might be costly.
References
- ↑ "Prof. Tami Tamir", Faculty, Reichman University, retrieved 2023-03-22
- 1 2 3 Curriculum vitae , retrieved 2023-03-22
- ↑ Tami Tamir at the Mathematics Genealogy Project
