Streaming and Matching Problems with Submodular Functions
Graph Chatbot
Chat with Graph Search
Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.
DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.
One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines, i.e., job j requires time p ij if processed on machine i. More th ...
One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job j requires time p(ij) if processed on machine i. More t ...
The generation of synthetic populations through simulation methods is an important research topic and has a key application in agent-based modeling of transport and land use. The next step in this research area is the generation of complete synthetic house ...
We study the basic allocation problem of assigning resources to players so as to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a ce ...
The polynomial Hirsch conjecture states that the vertex-edge diameter of a d-dimensional polyhedron with n facets is bounded by a polynomial in d and n. For the special case where the polyhedron is defined as the set of points satisfying a system Ax ≤ b of ...
We report on the solution of a real-time scheduling problem that arises in the design of software-based operation control of aircraft. A set of tasks has to be distributed on a minimum number of machines and offsets of the tasks have to be computed. The ta ...
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010
We present a polynomial time approximation scheme for the real-time scheduling problem with fixed priorities when resource augmentation is allowed. For a fixed ε > 0, our algorithmcomputes an assignment using atmost (1+ε)·OPT +1 processors in polynomial ti ...
On numerous occasions it has been pointed out that the class hierarchy of the Scala standard library is hard to follow. This project aims at addressing the problem by automatically generating interactive class hierarchy diagrams in the scaladoc tool. ...
We study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove ...
We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~3. Then, we draw a connection to Goem ...
